Как найти хеш массивы

Что нужно знать об устройстве коллекций, основанных на хешировании

Всем привет. На связи Владислав Родин. В настоящее время я являюсь руководителем курса «Архитектор высоких нагрузок» в OTUS, а также преподаю на курсах, посвященных архитектуре ПО.

Введение

Хеш-таблицы (HashMap) наравне с динамическими массивами являются самыми популярными структурами данных, применяемыми в production’е. Очень часто можно услышать вопросы на собеседованиях касаемо их предназначения, особенностей их внутреннего устройства, а также связанных с ними алгоритмов. Данная структура данных является классической и встречается не только в Java, но и во многих других языках программирования.

Постановка задачи

Давайте зададимся целью создать структуру данных, которая позволяет:

• contains(Element element) проверять, находится в ней некоторый элемент или нет, за О(1)
• add(Element element) добавлять элемент за О(1)
• delete(Element element) удалять элемент за О(1)

Массив

Попробуем сделать эти операции поверх массива, который является самой простой структурой данных. Договоримся, что будем считать ячейку пустой, если в ней содержится null.

Проверка наличия

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

Добавление

Если нам надо добавить элемент абы куда, то вначале мы должны найти пустую ячейку, а затем записать в нее элемент. Таким образом, мы опять осуществим линейный поиск и получим асимптотику O(n).

Удаление

Чтобы удалить элемент, его нужно сначала найти, а затем в найденную ячейку записать null. Опять линейный поиск приводит нас к O(n).

Простейшее хеш-множество

Обратите внимание, что при каждой операции, мы сначала искали индекс нужной ячейки, а затем осуществляли операцию, и именно поиск портит нам асимптотику! Если бы мы научились получать данный индекс за O(1), то исходная задача была бы решена.

Давайте теперь заменим линейный поиск на следующий алгоритм: будем вычислять значение некоторой фунции — хеш-функции, ставящей в соответствие объекту класса некоторое целое число. После этого будем сопоставлять полученное целое число индексу ячейки массива (это достаточно легко сделать, например, взяв остаток от деления этого числа на размер массива). Если хеш-функция написана так, что она считается за O(1) (а она так обычно и написана), то мы получили самую простейшую реализацию хеш-множества. Ячейка массива в терминах хеш-множества может называться bucket‘ом.

Проблемы простейшей реализации хеш-множества

Как бы ни была написана хеш-функция, число ячеек массива всегда ограничено, тогда как множество элементов, которые мы хотим хранить в структуре данных, неограничено. Ведь мы бы не стали заморачиваться со структурой данных, если бы была потребность в сохранении всего лишь десяти заранее известных элементов, верно? Такое положение дел приводит к неизбежным коллизиям. Под коллизией понимается ситуация, когда при добавлении разных объектов мы попадаем в одну и ту же ячейку массива.

Для разрешения коллизий придумано 2 метода: метод цепочек и метод открытой адресации.

Метод цепочек

Метод цепочек является наиболее простым методом разрешения коллизий. В ячейке массива мы будем хранить не элементы, а связанный список данных элементов. Потому как добавление в начало списка (а нам все равно в какую часть списка добавлять элемент) обладает асимптотикой О(1), мы не испортим общую асимптотику, и она останется равной О(1).

У данной реализации есть проблема: если списки будут очень сильно вырастать (в качестве крайнего случая можно рассмотреть хеш-функцию, которая возвращает константу для любого объекта), то мы получим асимптотику O(m), где m — число элементов во множестве, если размер массива фиксирован. Для избежания таких неприятностей вводится понятие коэффициент заполнения (он может быть равен, например, 1.5). Если при добавлении элемента оказывается, что доля числа элементов, находящихся в структуре данных по отношению к размеру массива, превосходит коэффициент заполнения, то происходит следующее: выделяется новый массив, размер которого превосходит размер старого массива (например в 2 раза), и структура данных перестраивается на новом массиве.

Данный метод разрешения коллизий и применяется в Java, а структура данных называется HashSet.

Метод открытой адресации

В данном методе в ячейках хранятся сами элементы, а в случае коллизии происходит последовательность проб, то есть мы начинаем по некоторому алгоритму перебирать ячейки в надежде найти свободную. Это можно делать разными алгоритмами (линейная / квадратичная последовательности проб, двойное хеширование), каждый из которых обладает своими проблемами (например, возникновение первичных или вторичных кластеров).

От хеш-множества к хеш-таблице (HashMap)

Давайте создадим структуру данных, которая позволяет так же быстро, как и хеш-множество (то есть за O(1)), добавлять, удалять, искать элементы, но уже по некоторому ключу.

Воспользуемся той же структурой данных, что у хеш-множества, но хранить будем не элементы, а пары элементов.

Таким образом, вставка (put(Key key, Value value)) будет осуществляться так: мы посчитаем ячейку массива по объекту типа Key, получим номер bucket’а. Пройдемся по списку в bucket’е, сравнивая ключ с ключом в хранимых парах. Если нашли такой же ключ — просто вытесняем старое значение, если не нашли — добавляем пару.

Как осуществляется получение элемента по ключу? Да по похожему принципу: получаем bucket по ключу, проходимся по парам и возвращаем значение в паре, ключ в которой равен ключу в запросе, если такая пара есть, и null в противном случае.

Данная структура данных и называется хеш-таблицей.

Типичные вопросы на собеседовании

Q: Как устроены HashSet и HashMap? Как осуществляются основные операциии в данных коллекциях? Как применяются методы equals() и hashCode()?
A: Ответы на данные вопросы можно найти выше.

Q: Каков контракт на equals() и hashCode()? Чем он обусловлен?
A: Если объекты равны, то у них должны быть равны hashCode. Таким образом, hashCode должен определяться по подможноству полей, учавствующих в equals. Нарушение данного контракта может приводить к весьма интересным эффектам. Если объекты равны, но hashCode у них разный, то вы можете не достать значение, соответствующее ключу, по которому вы только что добавили объект в HashSet или в HashMap.

Вывод

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

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

Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары «ключ-значение». В разных языках ему соответствуют разные типы данных. В Python — это Dictionary, в других языках:

• Ruby — Hash
• Lua — Table
• JavaScript — Object
• Elixir/Java — Map

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

В обычном индексированном массиве значения расположены по индексам, а значит его можно положить в память «как есть». С ассоциативными массивами все работает по-другому. У них нет индексов, которые бы могли определить порядок — значит, и нет простого способа добраться до значений.

Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу.

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

В этом уроке мы подробнее поговорим о хеш-таблицах и узнаем, как ассоциативные массивы устроены внутри. Вы поймете, сколько разных процессов происходит в программе, когда мы выполняем подобный простой код:

data = {}
data['key'] = 'value'

Что такое хеширование

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

• Найти хеш, то есть хешировать ключ
• Привести ключ к индексу — например, через остаток от деления

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

Наиболее известны CRC32, MD5, SHA и много других типов хеширования:

# В Python есть библиотека zlib, содержащая алгоритм хеширования crc32
# Этот алгоритм удобен для наглядности
import zlib

# Любые данные, которые мы хотим хешировать, представляются в виде байтовой строки
data = b'Hello, world!'
hash = zlib.crc32(data)

# Хеш всегда одинаковый для одних и тех же данных
print(hash) # => 3957769958

С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 — это хеш, полученный в результате хеширования данных коммита.

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

# Это делается для того, чтобы индексы не были слишком большими
# Чем больше размер массива, тем больше памяти он занимает
index = abs(hash) % 1000 # по модулю
print(index) # => 958

Как хеширование работает изнутри

Рассмотрим, как работает добавление нового значения в ассоциативный массив. Напомним, в Python он представлен типом данных Dictionary. Напишем такой код:

data = {}
data['key'] = 'value'

Такой простой код запускает целый сложный процесс. Для простоты рассмотрим его на Python, хотя в реальности все это происходит на более низком уровне.
Опишем процесс хеширования без деталей и с упрощениями.

1. Мы создаем ассоциативный массив. Внутри интерпретатора происходит инициализация индексированного массива:

   internal = []
   

2. Далее мы присваиваем значение:

   data['key'] = 'value'
   

3. Затем интерпретатор хеширует ключ. Результатом хеширования становится число:

   hash = zlib.crc32(b'key')
   

4. Далее интерпретатор берет число из предыдущего шага и преобразует его в индекс массива:

   index = abs(hash) % 1000
   

5. В конце интерпретатор ищет по индексу значение внутреннего индексированного массива и записывает его в еще один массив. Первым элементом нового массива становится ключ 'key', а вторым — значение 'value':

   internal[index] = ['key', 'value']
   

Теперь посмотрим, как работает чтение данных:

data = {}
data['key'] = 'value'
print(data['key']) # => "value"

Разберем, как этот код работает изнутри.

1. Интерпретатор хеширует ключ. Результатом хеширования становится число:

   hash = zlib.crc32(b'key')
   

2. Число, полученное на предыдущем шаге, преобразуется в индекс массива:

   index = abs(hash % 1000)
   

3. Если индекс существует, то интерпретатор извлекает массив и возвращает его наружу:

   return internal[index] # ['key', 'value']
   

Коллизии

Ключом в ассоциативном массиве может быть абсолютно любая строка, любой длины и содержания. Но здесь есть одно противоречие:

• Все возможные ключи — это бесконечное множество
• В качестве результата хеш-функция выдает строку фиксированной длины, то есть все выходные значения — это конечное множество

Из этого факта следует, что не для всех входных данных найдется уникальный хеш. На каком-то этапе могут появиться дубли: под одним хешем будут лежать несколько разных значений.

Такую ситуацию принято называть коллизией. Есть несколько способов разрешения коллизий. Каждому способу соответствует свой тип хеш-таблицы:

# Пример коллизии
# Хеш-функция возвращает одинаковый хеш для разных строчных данных
zlib.crc32(b'aaaaa0.462031558722291') # 1938556049
zlib.crc32(b'aaaaa0.0585754039730588') # 1938556049

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

Введение

Предположим, что есть набор, состоящий из n компонентов $а_1, а_2, а_3, . . ., а_n$, каждый из которых имеет некоторый ключ. Необходимо данный набор представить в форме определённой информационной структуры с обеспечением возможности многократных поисковых операций компонентов с определённым ключом. Такую задачу можно решить разными способами:

1. Когда набор компонентов не подвергался упорядочению, то поиск может быть выполнен путём прямого сравнения каждого компонента массива или списка. При этом трудоёмкость операции будет O(n).
2. Когда компоненты прошли процесс упорядочения в массиве или дереве поиска, то более эффективным будет поиск в двоичном формате при трудоёмкости О(log 2 n).

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

Поиск хешированием

Способ хеш-поиска состоит в следующем. Начальные компоненты $а_1, а_2, а_3, . . ., а_n$ располагаются особым образом в ячейках массива. Предполагаем, что количество ячеек в массиве $m > n$. Оптимальным случаем поисковой операции считается такая операция, когда при поступлении на вход какого-либо ключа можно сразу определить индекс ячейки, обладающей этим ключом, без анализа других ячеек. Чтобы вычислить индекс ячейки по ключу на входе, применяется специальная функция, именуемая хеш-функцией. По этой функции можно поставить в соответствие всем ключам индексы ячеек массива, где расположен компонент, имеющий этот ключ:

h (аi ) = j, j = (1, m);

Массив, который наполнен компонентами начального набора в очерёдности, определяемой хеш-функцией, является хеш-таблицей. Следовательно, разрешение поисковой задачи этим способом имеет существенную зависимость от применяемой хеш-функции. Известно достаточно много разных хеш-функций. Наиболее простой, но не наилучшей хеш-функцией считается функция, являющаяся остатком от деления ключа на m:

h (аi ) = (аi mod m) + 1;

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

1. Выражение функции должно быть не сложным с точки зрения необходимых вычислений.
2. Ключи, распределённые хеш-функцией, должны быть расположены в хеш-таблице по возможности в равномерном порядке.

Применение этой методики состоит из двух этапов:

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

Приведём конкретные примеры. Имеется набор из восьми ключей, заданных целыми числами:

35, 19, 07, 14, 26, 40, 51,72.

Необходимо выполнить распределение этих ключей в массиве из десяти ячеек при посредстве самой простой хеш-функции. То есть надо разделить все ключи нацело на десять и применить остатки как индексы расположения ключей в массиве:

35 mod 10 = 5, индекс местоположения ключа 35 равняется шести

19 mod 10 = 9, индекс местоположения ключа 19 равняется десяти

07 mod 10 = 7, индекс местоположения ключа 07 равняется восьми

14 mod 10 = 4, индекс местоположения ключа 14 равняется пяти

26 mod 10 = 6, индекс размещения ключа 26 равняется семи

40 mod 10 = 0, индекс местоположения ключа 40 равняется единице

51 mod 10 = 1, индекс местоположения ключа 51 равняется двум

72 mod 10 = 2, индекс местоположения ключа 72 равняется трём

В итоге будет получена следующая хеш-таблица:

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

Рассмотрим ещё один пример. Предположим, что ключи имеют строковый формат. Следовательно, сначала необходимо выполнить преобразование ключа в текстовом формате в цифровой формат. К примеру, можно выполнить сложение ASCII-кодов всех символьных знаков, которые входят в данный ключ. Предположим, что строковым ключом является слово END, тогда его эквивалентное числовое отображение будет равно сумме кодов этих трёх букв:

ord(E) + ord(N) + ord(D) = 69 + 78 + 68 = 215

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

h (END) = (215 mod 10) + 1 = 6

h (VAR) = (233 mod 10) + 1 = 4

h (AND) = (211 mod 10) + 1 = 2

h (NIL) = (227 mod 10) + 1 = 8

В итоге для данных строковых ключей сформирована следующая хеш-таблица:

Выполнить поисковую операцию в данной таблице совсем не сложно. Нужно найти целочисленный аналог строкового ключа, затем вычислить величину хеш-функции и сравнить содержимое найденной ячейки с исходным ключом. К примеру, h (VAR) = 4, выполняем сравнение содержимого ячейки четыре с ключом VAR, отмечаем наличие совпадения. Поиск завершён.

Подробнее об ассоциативных массивах[править]

Различают два типа массивов: индексные, у которых в качестве индекса только целое число, и ассоциативные, где индексом может быть любой объект.

Индексные массивы чаще всего называют просто «массивами», а ассоциативные массивы — «хешами» или «словарями».

Хеши можно представить как массив пар: ключ=>значение. Но в отличие от массива, хеш неупорядочен: нельзя заранее сказать, какая пара будет первой, а какая последней. Правда, удобство использования массива это не умаляет. Более того, поскольку в Ruby переменные не типизированы и методам с похожей функциональностью дают похожие имена, то использование хеша чаще всего равносильно использованию массива.

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

Давайте создадим хеш, где в качестве ключа будем использовать целое число:

hash = {5=>3, 1=>6, 3=>2}
hash[5]                      #=> 3
hash[2]                      #=> nil  это значит, что объект отсутствует
hash[3]                      #=> 2

А вот так будет выглядеть та же самая программа, если мы будем использовать массив:

array = [nil, 6, nil, 2, nil, 3]
array[5]                            #=> 3
array[2]                            #=> nil
array[3]                            #=> 2

Первый случай применимости хеша: если в массиве намечаются обширные незаполненные (то есть заполненные nil) области, то целесообразнее использовать хеш с целочисленным индексом.

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

Продолжим поиски случаев применимости хеша и на этот раз подсчитаем, сколько раз каждое число повторяется в данном целочисленном массиве. Решение массивом:

array = [1, 2, 1, 2, 3, 2, 1, 2, 4, 5]
array.uniq.map{ |i| [i, array.find_all{ |j| j == i }.size] }    #=> [[1, 3], [2, 4], [3, 1], [4, 1], [5, 1]]

Алгоритм получается ужасным. Не буду утомлять излишними терминами, а замечу, что по одному и тому же массиву итераторы (в количестве двух штук) пробегают много раз. А ведь достаточно одной «пробежки». Понятное дело, что такая программа не сделает вам чести. В качестве упражнения, предлагаю вам решить эту задачу другим, более оптимальным, способом.

Теперь рассмотрим решение этой же задачи, но с применением хеша:

array = [1, 2, 1, 2, 3, 2, 1, 2, 4, 5]
array.inject(Hash.new{ 0 }){ |result, i|
    result[i] += 1
    result
}                                         #=> {5=>1, 1=>3, 2=>4, 3=>1, 4=>1}

Удалось избавиться от лишних методов и обойтись лишь одной «пробежкой» итератора по массиву.

Начальный хеш был создан хитроумной комбинацией Hash.new{0}, что в переводе на русский означает примерно следующее: «создадим пустой хеш, в котором любому несуществующему ключу будет соответствовать 0». Это нужно, чтобы суммирование (метод +) не выдавало ошибку вида: «не могу сложить nil и число типа Fixnum». В качестве упражнения, предлагаю вам заменить комбинацию Hash.new{ 0 } на {} и посмотреть, чем это чревато.

Зачем нужно дописывать result? Дело в том, что комбинация result[i] += 1 имеет в качестве результата целое число (учитывая, что массив целочисленный), а не хеш. Следовательно, параметру result автоматически будет присвоено целое число (см. описание итератора .inject). На следующей итерации мы будем обращаться к result, как к хешу, хотя там уже будет храниться число. Хорошо, если программа выдаст ошибку, а если нет? Проверьте это самостоятельно.

В качестве упражнения, предлагаю вам переписать программу без вышеописанных двух особенностей (используйте метод .update). Решение будет опубликовано ниже.

Второй случай применимости хеша: если требуется подсчитать число элементов массива, то целессобразнее применять хеш. Кстати, вместо подсчета количества, можно использовать конкатенацию массивов или строк. Но это уже более сложные задачи, которые будут рассмотрены позже.

Теперь представим, что мы работаем системными администраторами. У нас есть список DNS-имён и IP-адреса. Каждому DNS-имени соответствует только один IP-адрес. Как нам это соответствие записать в виде программы? Попробуем это сделать при помощи массива:

array = [["comp1.mydomen.ru", "192.168.0.3"], 
         ["comp2.mydomen.ru", "192.168.0.1"],
         ["comp3.mydomen.ru", "192.168.0.2"]]

Всё бы ничего, но чтобы найти IP-адрес по DNS имени, придётся перелопатить весь массив в поиске нужного DNS:

dns_name = "comp1.mydomen.ru"
array.find_all{ |key, value| key == dns_name }[0][-1]    #=> "192.168.0.3"

В данном примере было использовано два интересных приёма:

• Если в двумерном массиве заранее известное количество столбцов (в нашем случае — два), то каждому из столбцов (в рамках любого итератора) можно дать своё имя (в нашем случае: key и value). Если бы мы такого имени не давали, то вышеописанное решение выглядело бы так:

array.find_all{ |array| array[0] == dns_name }[0][-1]    #=> "192.168.0.3"

Без именования столбцов, внутри итератора вы будете работать с массивом (в двумерном массиве каждый элемент — массив, а любой итератор «пробегает» массив поэлементно). Это высказывание действительно, когда «пробежка» осуществляется по двумерному массиву.

• Метод .find_all возвращает двумерный массив примерно следующего вида: [["comp1.mydomen.ru", "192.168.0.3"]], чтобы получить строку "192.168.0.3" необходимо избавиться от двумерности. Делается это при помощи метода [], который вызывается два раза (понижает размерность c двух до нуля). Метод [0] возвращает в результате — ["comp1.mydomen.ru", "192.168.0.3"], а метод [-1] — "192.168.0.3". Как раз это нам и было нужно.

Теперь ту же самую задачу решим, используя хеш:

hash = {"comp1.mydomen.ru"=>"192.168.0.3", 
        "comp2.mydomen.ru"=>"192.168.0.1",
        "comp3.mydomen.ru"=>"192.168.0.2"}
hash["comp1.mydomen.ru"]                        #=> "192.168.0.3"

Нет ни одного итератора и, следовательно, не сделано ни одной «пробежки» по массиву.

Третий случай применимости хеша: когда требуется сопоставить один набор данных с другим, то целесообразнее использовать хеш.

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

В заключении, как и было обещано, приводится решение задачи с использованием метода .update:

array = [1, 2, 1, 2, 3, 2, 1, 2, 4, 5]
array.inject({}){ |result, i| result.update({ i=>1 }){ |key, old, new| old+new }}
    #=> {5=>1, 1=>3, 2=>4, 3=>1, 4=>1}

Описание метода .update будет дано ниже. На данном этапе попытайтесь угадать принцип работы метода .update.

Что используется в качестве ключей?[править]

В качестве ключей ассоциативного массива можно использовать любые типы. Например, другие ассоциативные массивы, строки, числа, символы или просто объекты любых классов.

Если состояние объектов-ключей изменилось, то хешу необходимо вызвать метод .rehash.

array1 = ["а", "б"]
array2 = ["в", "г"]
hash = {array1=>100, array2=>300}
hash[array1]                         #=> 100
array1[0] = "я"
hash[array1]                         #=> nil
hash.rehash                          #=> {["я", "б"]=>100, ["в", "г"]=>300}
hash[array1]                         #=> 100

В данном примере ключами хеша (hash) являются два массива (array1 и array2). Одному из них (array1) мы изменили нулевой элемент (с "а" на "я"). После этого доступ к значению был потерян. После выполнения метода .rehash всё встало на свои места.

Как Ruby отслеживает изменение ключа в ассоциативном массиве? Очень просто: с помощью метода .hash, который генерирует «контрольную сумму» объекта в виде целого числа. Например:

Способы создания ассоциативного массива[править]

При создании ассоциативного массива важно ответить на несколько вопросов:

• Какие данные имеются?
• Какого типа эти данные?
• Что будет ключом, а что — значением?

Ответы определят способ создания хеша.

Из одномерного массива[править]

Положим, что у нас в наличии индексный массив, где ключ и значение записаны последовательно. Тогда мы можем использовать связку методов * и Hash[]:

array = [1, 4, 5, 3, 2, 2]
Hash[*array]                  #=> {1=>4, 5=>3, 2=>2}

Элементы, стоящие на нечётной позиции (в данном случае: 1, 5 и 2) стали ключами, а элементы, стоящие на чётной позиции (то есть: 4, 3 и 2), стали значениями.

Из двумерного массива[править]

Если повезло меньше и нам достался двумерный массив с элементами вида [["ключ_1", "значение_1"], ["ключ_2", "значение_2"], ["ключ_3", "значение_3"], …], то его надо сплющить (.flatten) и тем задача будет сведена к предыдущей:

array = [[1, 4], [5, 3], [2, 2]]
Hash[*array.flatten]                #=> {1=>4, 5=>3, 2=>2}

Каждый нулевой элемент подмассива станет ключом, а каждый первый — значением.

Но может случиться так, что двумерный массив будет состоять из двух подмассивов: подмассива ключей и подмассива значений:

[["ключ_1", "ключ_2", "ключ_3", …], ["значение_1", "значение_2", "значение_3", …]]

Вспоминаем методы работы с массивами. Там был метод .transpose (транспонирование массива), вызов которого сведёт задачу к предыдущей.

array = [[1, 5, 2], [4, 3, 2]]
Hash[*array.transpose.flatten]    #=> {1=>4, 5=>3, 2=>2}

Нет данных[править]

Если нет данных, то лучше записать хеш как пару фигурных скобок:

hash = {}
hash[1] = 4
hash[5] = 3
hash[2] = 2
hash           #=> {1=>4, 5=>3, 2=>2}

И уже по ходу дела разобраться, что к чему.

Известен только тип значений[править]

Сведения о типе значений использовать следует так: создать хеш, в котором будет определён элемент по умолчанию. Элементом по умолчанию должен быть нулевой элемент соответствующего типа, то есть для строки это будет пустая строка (""), для массива — пустой массив ([]), а для числа — нуль (0 или 0.0). Это делается, чтобы к пустому элементу можно было что-то добавить и при этом не получить ошибку.

hash = Hash.new("")
hash["песенка про зайцев"] += "В тёмно-синем лесу, "
hash["песенка про зайцев"] += "где трепещут осины"
hash    #=> {"песенка про зайцев"=>"В темно-синем лесу, где трепещут осины"}

Или ещё пример:

hash = Hash.new(0)
hash["зарплата"] += 60
hash["зарплата"] *= 21
hash      #=> {"зарплата"=>1260}

Но, как известно, из любого правила есть исключение: использовать нулевой элемент, когда значение будет записываться умножением, нежелательно. Потому как, даже не будучи пророком, можно предсказать результат. Он будет равен нулю.

Всё известно и дано[править]

Если вам изначально известны все ключи и значения, то и записывайте их сразу в виде хеша, одним из способов:

{"март"=>400, "январь"=>350, "февраль"=>200}  #=> на выходе такой же текст
{fox: 1, wolf: 2, dragon: 3}                  #=> {:fox=>1, :wolf=>2, :dragon=>3} обратите внимание на знак ':', он говорит что fox - это не строка, 
                                              #   а чтото вроде перечисления (Enum), как в языке Си.

Не изобретайте велосипед и поступайте как можно проще.

Методы работы с ассоциативными массивами[править]

Когда речь пойдёт о методах, которые присутствуют в ассоциативных массивах, то частенько будет возникать чувство дежавю. Во всяком случае, учить заново итераторы вам не придётся. Вполне естественно, что появятся новички, но их будет немного. Тем не менее, прилежный преподаватель первым делом представляет новичков группе. Поэтому и мы начнем с тех методов, которые будут необходимы нам при работе с ассоциативными массивами, но отсутствуют у индексных.

Получение массива значений и массива ключей[править]

Для получения отдельно массива ключей или значений существуют методы .keys и .values.

{1=>4, 5=>3, 2=>2}.keys      #=> [1, 2, 5]
{1=>4, 5=>3, 2=>2}.values    #=> [4, 3, 2]

Ассоциативные массивы в Ruby неупорядоченны: массивы могут иметь любой порядок элементов.

Замена ключей на значения[править]

Чтобы поменять местами ключи и значения ассоциативного массива, следует применять метод .invert. Этот метод возвращает ассоциативный массив с ключами, заменёнными значениями, и значениями, заменёнными ключами.

hash = {"первый ключ"=>4, "второй ключ"=>5}
hash.invert                                    #=> {4=>"первый ключ", 5=>"второй ключ"}

Поскольку ключи в ассоциативных массивах уникальны, то ключи с одинаковыми значениями будут отброшены:

hash = {"первый ключ"=>10, "второй ключ"=>10}
hash.invert                                      #=> {10=>"второй ключ"}

Небольшая хитрость: hash.invert.invert возвратит нам хеш с уникальными значениями.

Обновление пары[править]

Что вы делаете, если хотите обновить какую-то программу или игру? Правильно, устанавливаете апдейт. Вы не поверите, но для обновления значения в ассоциативном массиве используется метод .update. Странно, да? Пример использования этого метода в «боевых» условиях мы уже приводили в начале раздела. Если вы помните, то мы считали, сколько раз повторяется каждое число. Наверняка, вы немного подзабыли его решение (у программистов есть привычка не помнить константы). Позволю себе его вам напомнить:

array = [1, 2, 1, 2, 3, 2, 1, 2, 4, 5]
array.inject({}){ |result, i| result.update({i=>1}){ |key, old, new| old + new } }
    #=> {5=>1, 1=>3, 2=>4, 3=>1, 4=>1}

Страшноватая запись. Поэтому будем разбирать её по частям.

result.update({i=>1}){ |key, old, new| old + new }

Сразу после названия метода (в нашем случае .update) идёт передача параметра. Страшная запись {i=>1} — это не что иное, как ещё один хеш. Ключ его хранится в переменной i (счётчик итератора .inject), а в качестве значения выбрана единица. Зачем? Расскажу чуть позже.

Не обязательно писать именно {i=>1}. Можно «сократить» фигурные скобки и записать i=>1.

Счётчик итератора — это переменная в которую итератор записывает текущий элемент последовательности.

Здесь вроде бы все понятно. Запись стала менее страшной, но всё равно вызывает дрожь. Будем это исправлять!

… { |key, old, new| … } …

Раньше мы не встречались с такой записью. Но ничего страшного в ней нет. Это что-то вроде по́ля боя. Нам выдали вооружение и необходимо провести некий манёвр. В нашем случае, арсенал у нас внушительный: key, old и new. Бой начинается при некоторых условиях. Наш бой начнется, когда при добавлении очередной пары (переданной в предыдущей части страшной записи) обнаружится, что такой ключ уже есть в хеше. Нам предлагается описать наши действия именно в таком случае. Что же это за действия?

Всего лишь сложение old и new. Ничего не говорит? Тогда расскажу, что значат переменные key, old и new. В переменную key передаётся текущий ключ, в old — старое значение по ключу (англ. old — старый), а в переменную new — добавляемое значение по ключу (англ. new — новый).

Теперь переведём запись old + new на русский: в случае обнаружения ключа в хеше, нам необходимо сложить старое значение с новым. Если помните, то новое значение равняется единице, то есть в случае когда ключ, хранимый в i уже есть в хеше result, то к старому значению просто добавляется единица. Вот и всё… а вы боялись.

Рекомендуется перечитать данную главу ещё раз, так как вы её немного не поняли.

Интересно, сколько читателей сможет прочитать эту строку и не зациклиться на предыдущей?

Слияние двух массивов[править]

Для слияния двух массивов можно использовать тот же метод .update или его алиас .merge или .merge!:

hash1 = {3 => "a", 4 => "c"}
hash2 = {5 => "r", 7 => "t"}
hash1.merge!(hash2)                   #=> {5=>"r", 7=>"t", 3=>"a", 4=>"c"}

Если во втором массиве ключ будет совпадать с каким-либо ключем из первого массива, значение будет заменено на значение из второго массива.

Размер ассоциативного массива[править]

Ну вот, с новичками мы познакомились, теперь можно переходить к старым знакомым. Помните, как мы находили размер массива? Вот и с хешами точно также:

hash = {5=>1, 1=>3, 2=>4, 3=>1, 4=>1}
hash.size                                #=> 5

Стоит уточнить, что если в индексных массивах под размером понимается количество элементов, то в ассоциативном массиве это количество пар вида ключ=>значение. В остальном же это наш старый добрый .size.

Удаление пары по ключу[править]

О том, как добавлять элементы в массив мы знаем, а вот про удаление — нет. Необходимо это исправить. Чем мы сейчас и займёмся.

hash = {5=>1, 1=>3, 2=>4, 3=>1, 4=>1}
hash.delete(5)                           #=> 1
hash                                     #=> {1=>3, 2=>4, 3=>1, 4=>1}
hash.delete(5)                           #=> nil

Как вы, наверно, уже догадались, удалением пары по ключу занимается метод .delete. Ему передаётся ключ от пары, которую следует удалить.

Метод .delete возвращает значение, которое соответствовало ключу в удаляемой паре. Если в хеше отсутствует пара с передаваемым ключом, то метод .delete возвращает nil. Напоминаем, что nil — это символ пустоты.

Удаление произвольной пары[править]

Многие программисты удивляются, когда узнаю́т, что ассоциативные массивы имеют метод .shift. Связано это удивление с тем, что у индексных массивов он удаляет первый элемент, возвращая его во время удаления. А вот как понять, какая пара является первой? И что такое первый в неупорядоченной последовательности пар?

Ответ кроется в отсутствии метода-напарника .pop, так как если нельзя удалить последний элемент, то под .shift понимается удаление произвольной пары. Вот такое вот нехитрое доказательство.

Давайте посмотрим его в действии:

hash = {5=>3, 1=>6, 3=>2}
hash.shift                   #=> [5, 3]
hash                         #=> {1=>6, 3=>2}

Обратите внимание, что метод .shift возвращает удаляемую пару в виде индексного массива [ключ, значение].

Не стоит обольщаться по поводу того, что метод .shift возвращает первую пару. Помните, что ассоциативные массивы неупорядоченны.

Преобразовать в индексный массив[править]

Чуть ранее уже говорилось, что в большинстве случаев индексные массивы удобней ассоциативных.

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

Чтобы преобразовать ассоциативный массив в индексный, надо использовать метод to_a. Его используют все, кто не может запомнить методов работы с хешами.

hash = {"гаечный ключ"=>10, "разводной ключ"=>22}
hash.to_a    #=> [["гаечный ключ", 10], ["разводной ключ", 22]]

Способ преобразования таков. Сперва пары (ключ=>значение) преобразуются в массив:

{["гаечный ключ"=>10], ["разводной ключ"=>22]}

Затем «стрелку» заменяем на запятую:

{["гаечный ключ", 10], ["разводной ключ", 22]}

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

[["гаечный ключ", 10], ["разводной ключ", 22]]

Упорядочение хеша[править]

Да, множество пар в хеше неупорядоченно. Но это можно исправить, разве что результат потом будет не хешем, а двумерным массивом.

hash = {"гаечный ключ"=>4, "разводной ключ"=>10}
hash.sort    #=> [["гаечный ключ", 4], ["разводной ключ", 10]]

В методе .sort_by передаются два значения:

hash = {"гаечный ключ"=>4, "разводной ключ"=>10}
hash.sort_by{ |key, value| value } #=> [["гаечный ключ", 4], ["разводной ключ", 10]]

Здесь мы упорядочили хеш по значению.

Сначала хеш упорядочивается по ключам, а потом, в случаях равнозначных ключей при использовании sort_by, — по значениям.

Поиск максимальной/минимальной пары[править]

Максимальная пара в хеше ищется точно также, как и максимальный элемент в массиве

hash = {"гаечный ключ"=>10, "разводной ключ"=>22}
hash.max    #=> ["разводной ключ", 22]
hash.min    #=> ["гаечный ключ"  , 10]

но с небольшими особенностями:

• результат поиска — массив из двух элементов вида [ключ, значение],
• сначала поиск происходит по ключу, а в случае равноправных ключей при использовании max_by и min_by — по значению.

Несколько больше возможностей приобрели методы max_by и min_by:

hash = {"гаечный ключ"=>10, "разводной ключ"=>22}
hash.max_by{ |key, value| value }                    #=> ["разводной ключ", 22]
hash.min_by{ |array| array[0] }                      #=> ["гаечный ключ"  , 10]

Также, как и в методе sort_by есть возможность по разному получать текущую пару: в виде массива или двух переменных.

Логические методы[править]

Работа логических методов похожа на допрос с пристрастием. Помните, как в детективах во время теста на детекторе лжи, главный герой восклицал: «Отвечать только „да“ или „нет“!» Если перевести это на язык Ruby, то это будет звучать примерно так: «Отвечать только true или false!»

В детективах набор вопросов стандартен:

• Знали ли вы мистера X?
• Вы были на месте преступления?
• Убивали ли мистера X?
• …

На Ruby примерно тоже самое:

• Ты пустой?
• Есть ли такой элемент?
• Ты массив?
• Уверен, что не строка?

Но давайте рассмотрим их подробней.

Хеш пустой?[править]

Зададим вопрос «Хеш пустой?», но используя известный нам лексикон. Для начала спросим «Пустой хеш тебе не брат-близнец?»

empty_hash  = {}
filled_hash = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}

empty_hash  == {}    #=> true
filled_hash == {}    #=> false

Можно спросить по другому: «Размер у тебя не нулевой?»

empty_hash  = {}
filled_hash = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}

empty_hash .size.zero?    #=> true
filled_hash.size.zero?    #=> false

Но давайте будем задавать правильные вопросы

empty_hash  = {}
filled_hash = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}

empty_hash .empty?    #=> true
filled_hash.empty?    #=> false

а то ещё примут нас за приезжих…

Обратите внимание, что метод .empty? полностью повторяет такой же метод у индексных массивов.

Есть такой ключ?[править]

Если вам нужно узнать у хеша ответ на вопрос «есть у тебя такой ключ?», но вы не знаете как это правильно спросить, то скорее всего вы зададите вопрос в два этапа: «какие ключи у тебя есть?» и «есть среди них такой ключ?»

pocket = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}
pocket.keys.include?("гаечный")    #=> true

В данном примере у нас в pocket нашёлся "гаечный" ключ.

Но лучше задавать вопрос напрямую, это покажет ваше прекрасное знание языка.

pocket = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}
pocket.key?("гаечный")    #=> true

или в стиле индексных массивов

pocket = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}
pocket.include?("гаечный")    #=> true

Это несколько сократит первоначальное предложение, но тогда можно перепутать хеш с массивом.

Этот же вопрос можно задать методами: .member? и .has_key?.

Есть такое значение?[править]

Давайте подумаем, как задать вопрос «есть такое значение?» хешу. Скорее всего, мы опять зададим вопрос в два этапа: «какие значения есть?» и «есть ли среди них нужное нам?»

pocket = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}
pocket.values.include?("гаечный")       #=> false — ой, забыл сменить
pocket.values.include?("английский")    #=> true

Но аборигены говорят иначе и задают вопрос напрямую:

pocket = {"гаечный"=>20, "замочный"=>"английский", "разводной"=>34}
pocket.value?("английский")    #=> true

Задать вопрос «Есть такое значение?» можно не только при помощи метода .value?, но и при помощи более длинного .has_value?.

Итераторы[править]

У ассоциативных массивов есть следующие итераторы:

• .find_all — поиск всех элементов, которые удовлетворяют логическому условию;
• .map — изменение всех элементов по некоторому алгоритму;
• .inject — сложение, перемножение и агрегация элементов массива.

Набор итераторов точно такой же, как и у индексных массивов — сказывается их родство. Вот только ведут себя они несколько иначе:

• Результатом является двумерный массив (как после метода .to_a).
• В качестве счётчика (переменной в фотографии) передаётся массив вида [ключ, значение].
• Можно развернуть массив вида [ключ, значение] в две переменные.
• В итераторе .inject развернуть массив можно используя запись .inject{|result, (key, value)| }.

Рассматривать заново работу каждого итератора в отдельности скучно. Поэтому мы будем рассматривать работу всех итераторов сразу.

hash = {"гаечный ключ"=>4, "разводной ключ"=>10}

hash.find_all{ |array| array[1] < 5 }
    #=> [["гаечный ключ", 4]]

hash.map { |array| "#{array[0]} на #{array[1]}" }
    #=> ["гаечный ключ на 4", "разводной ключ на 10"]

hash.inject(0){ |result, array| result + array[1] }
    #=> 14

Обратите внимание на то, что в качестве счётчика передаётся массив из двух элементов. В наших примерах счётчик итератора мы назвали array. В своих программах вы вольны называть его как угодно.

Есть подозрение, что перед работой любого из итераторов вызывается метод .to_a. Уж больно работа итераторов в хешах напоминает работу с двумерным массивом.

Теперь посмотрим, как можно развернуть array в две переменные. Делается это простой заменой array на key, value:

hash = {"гаечный ключ"=>4, "разводной ключ"=>10}

hash.find_all{ |key, value| value < 5 }
    #=> [["гаечный ключ", 4]]

hash.map{ |key, value| "#{key} на #{value}" }
    #=> ["гаечный ключ на 4", "разводной ключ на 10"]

hash.inject(0){ |result, key, value| result + value }
    #=> Ошибка в методе "+": невозможно сложить nil и число типа Fixnum

Обратите внимание, что развёртка массива прошла успешно только в первых двух итераторах. В третьем возникла ошибка. Давайте выясним, откуда там взялся nil. Дело в том, что развернуть массив не удалось, и теперь он стал называться не array, а key. Переменная value осталась «не у дел», и ей присвоилось значение nil. Чтобы это исправить, достаточно поставить круглые скобки:

hash.inject(0){ |result, (key, value)| result + value }
    #=> 14

Ассоциативный массив, как и индексный массив, имеет метод .map, который передаёт замыканию ключ и соответствующее ему значение. При этом в замыкание на самом деле передаётся массив с ключом и значением, но Ruby «разворачивает» их в две переменные при передаче замыканию.

Итератор .map, в свою очередь, возвращает индексный массив с результатами замыкания — по элементу массива на каждый ключ:

hash = {"гаечный ключ"=>4, "разводной ключ"=>10}
hash.map { | key, value | "#{key} на #{value}" }    #=> ["гаечный ключ на 4", "разводной ключ на 10"]
hash.map                                            #=> [["гаечный ключ", 4], ["разводной ключ", 10]]

Итератор .map, вызванный без аргументов, аналогичен методу .to_a: просто раскладывает хеш в двумерный массив.

Хитрости[править]

Одному программисту надоело писать hash["key"] и он захотел сделать так, чтобы можно было написать hash.key.

class Hash
    def method_missing(id)
        self[id.id2name]
    end
end

hash = {"hello"=>"привет", "bye"=>"пока"}
hash.hello    #=> "привет"
hash.bye      #=> "пока"

Естественно, что ключи в таком хеше могут содержать только латиницу, символ подчёркивания и цифры (везде, кроме первого символа). Иначе говоря, удовлетворять всем требованиям, которые мы предъявляем к именам методов и именам переменных.

Задачи[править]

1. Дан массив слов. Необходимо подсчитать, сколько раз встречается каждое слово в массиве.

const int k = 31, mod = 1e9+7;

string s = "abacabadaba";
long long h = 0, m = 1;
for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h + m * x) % mod;
    m = (m * k) % mod;
}

long long h = 0;
for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h * k + x) % mod;
}

const int maxn = 1e5+5;

int p[maxn];
p[0] = 1;

for (int i = 1; i < maxn; i++)
    p[i] = (p[i-1] * k) % mod;

int h[maxn];
h[0] = 0; // h[k] -- хэш префикса длины k

// будем считать, что s это уже последовательность int-ов

for (int i = 0; i < n; i++) 
    h[i+1] = (h[i] + p[i] * s[i]) % mod;

int hash_substring (int l, int r) {
    return (h[r+1] - h[l]) * p[n-l] % mod;
}