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

8.2.13. Вычисление разности и пересечения хэшей

Ключи хэша можно скопировать в отдельный массив, а к получившимся из разных хэшей массивам применить методы & и – класса Array. Результатом являются пересечение и разность множеств ключей. Соответствующие им значения можно получить с помощью метода each, примененного к хэшу, содержащему все образованные таким способом ключи.

 а = {"а"=>1,"b"=>2,"z"=>3}
 b = {"x"=>99,"у"=>88,"z"=>77}
 intersection = a.keys & b.keys
 difference = a.keys - b.keys
 с = a.dup.update(b)
 inter = {}
 intersection.each {|k| inter[k]=c[k] }
# inter равно {"z"=>77}
 diff={}
 difference.each {|k| diff[k]=c[k] }
 # diff равно {"а"=>1, "b"=>2}

8.2.14. Хэш как разреженная матрица

Часто в массиве или матрице заполнена лишь небольшая часть элементов. Можно хранить их как обычно, но такое расходование памяти неэкономно. Хэш позволяет хранить только реально существующие значения.

В следующем примере предполагается, что несуществующие значения по умолчанию равны нулю:

 values = Hash.new(0)
 values[1001] = 5
 values[2010] = 7
 values[9237] = 9
 x = values[9237] # 9
 y = values[5005] # 0

Ясно, что обычный массив в таком случае содержал бы более 9000 неиспользуемых элементов, что не всегда приемлемо.

А если нужно реализовать разреженную матрицу размерности два или более? В этом случае можно было бы использовать массивы в качестве ключей:

 cube = Hash.new(0)
 cube[[2000,2000,2000]] = 2
 z = cube[[36,24,36]] # 0

Здесь обычная матрица содержала бы миллиарды элементов.

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]