Хэл Фултон - Программирование на языке Ruby

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

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

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.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— допустимое значение в любом хэше.)