Книга: Программирование на языке Ruby

8.2.15. Реализация хэша с повторяющимися ключами

8.2.15. Реализация хэша с повторяющимися ключами

Приверженцы математической строгости скажут, что хэш с повторяющимися ключами — вообще не хэш. Не станем спорить. Называйте как хотите, но на практике бывают случаи, когда нужна структура данных, обладающая гибкостью и удобством хэша и в то же время содержащая ключи-дубликаты.

В листинге 8.1 предложено частичное решение. Оно неполно по двум причинам. Во-первых, мы не стали реализовывать всю желательную функциональность, ограничившись лишь некоторым достаточно представительным подмножеством. Во-вторых, внутреннее устройство Ruby таково, что литеральный хэш всегда является экземпляром класса Hash, и, хотя мы наследуем классу Hash, литерал все равно не сможет содержать повторяющихся ключей (мы подумаем об этом позже).

class HashDup
 def initialize(*all)
  raise IndexError if all.size % 2 != 0
  @store = {}
  if all[0] # не nil
   keyval = all.dup
   while !keyval.empty?
    key = keyval.shift
    if @store.has_key?(key)
     @store[key] += [keyval.shift]
    else
     @store[key] = [keyval.shift]
    end
   end
  end
 end
 def store(k,v)
  if @store.has_key?(k)
   @store[k] += [v]
  else
   @store[k] = [v]
  end
 end
 def [](key)
  @store[key]
 end
 def []=(key,value)
  self.store(key,value)
 end
 def to_s
  @store.to_s
 end
 def to_a
  @store.to_a
 end
 def inspect
  @store.inspect
 end
 def keys
  result=[]
  @store.each do |k,v|
   result += ([k]*v.size)
  end
  result
 end
 def values
  @store.values.flatten
 end
 def each
  @store.each {|k,v| v.each {|y| yield k,y}}
 end
 alias each_pair each
 def each_key
  self.keys.each {|k| yield k}
 end
 def each_value
  self.values.each {|v| yield v}
 end
 def has_key? k
  self.keys.include? k
 end
 def has_value? v
  self.values.include? v
 end
 def length
  self.values.size
 end
 alias size length
 def delete k
  val = @store[k]
  @store.delete k
  val
 end
 def delete k,v
  @store[k] -= [v] if @store[k]
  v
 end
 # Остальные методы опущены...
end
# He будет работать... для повторяющихся ключей
# актуально только последнее значение.
h = {1=>1, 2=>4, 3=>9, 4=>16, 2=>0}
# А так будет...
h = HashDup.new(1,1, 2,4, 3,9, 4,16, 2,0)
k = h.keys   # [4, 1, 2, 2, 3]
v = h.values # [16, 1, 4, 0, 9]
n = h.size   # 5
h.each {|k,v| puts "#{k} => #{v}"}
# Печатается:
# 4 => 16
# 1 => 1
# 2 => 4
# 2 => 0
# 3 => 9

Но если не пользоваться литеральными хэшами, то задача решаема. В листинге 8.1 реализован класс, содержащий атрибут @store, который является обычным хэшем; каждое значение этого хэша представляет собой массив. Доступ к хэшу организован так, что при необходимости добавить ключ, который уже существует, мы на самом деле добавляем новое значение в массив, ассоциированный с этим ключом.

Что должен возвращать метод size? Очевидно, «истинное» число пар ключ-значение, включая и дубликаты. Аналогично метод keys возвращает массив, который может содержать дубликаты. Итераторы ведут себя естественно; как и в случае обычного хэша, порядок обхода непредсказуем.

Помимо стандартного метода delete мы реализовали метод delete_pair. Первый удаляет все значения, ассоциированные с данным ключом, второй — только конкретную пару ключ-значение. (Отметим, что было бы затруднительно реализовать единственный метод вида delete(k, v=nil), так как nil — допустимое значение в любом хэше.)

Для краткости мы не стали реализовывать весь класс целиком и, честно говоря, для некоторых методов, например invert, пришлось бы принимать небанальные решения по поводу желательного поведения. Интересующийся читатель может восполнить пробелы.

Оглавление книги