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

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

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

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

Листинг 8.1. Хэш с повторяющимися ключами

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, пришлось бы принимать небанальные решения по поводу желательного поведения. Интересующийся читатель может восполнить пробелы.