Хэш-таблицы
Хэш-таблицы (hash tables) – одно из величайших изобретений информатики. Сочетание массивов и списков с небольшой добавкой математики позволило создать эффективную структуру для хранения и* получения динамических данных. Типичное применение хэш-таблиц – символьная таблица, которая ассоциирует некоторое значение (данные) с каждым членом динамического набора строк (ключей).
Ваш любимый компилятор практически наверняка использует хэш-таблицу для управления информацией о переменных в вашей программе. Ваш web-браузер наверняка использует хэш-таблицу для хранения адресов страниц, которые вы недавно посещали, а при соединении вашего компьютера с Интернетом, вероятно, она применяется для оперативного хранения (cache – кэширования) недавно использованных доменных имен и их IP-адресов.
Идея состоит в том, чтобы пропустить ключ через хэш-функцию (hash function) для получения хэш-значения (hash value), которое было бы равномерно распределено по диапазону целых чисел приемлемого размера. Это хэш-значение используется как индекс в таблице, где хранится информация. Java предоставляет стандартный интерфейс к хэш-таб-лицам. В С и C++ обычно с каждым хэш-значением (или "bucket" – "корзиной") ассоциируется список элементов, которые обладают этим значением, как показано на следующем рисунке:
На практике хэш-функция предопределена, а массив соответствующего размера выделяется нередко даже во время компиляции. Каждый элемент массива – это список, который сцепляет вместе элементы, имеющие общее хэш-значение. Другими словами, хэш-таблица из п элементов – это массив списков, средняя длина которых равна n/'(размер_массива). Получение элемента является константной (О(1)) операцией, если мы взяли хорошую хэш-функцию и списки не становятся слишком большими.
Поскольку хэш-таблица – массив списков, то тип элементов для нее такой же, как и для списка:
Способы работы со списками из раздела 2.7 можно использовать для управления отдельными хэш-цепочками. Как только у вас есть хорошая хэш-функция, все становится легко: получаете цепочку и дальше спокойно проходите вдоль списка, ища подходящий элемент. Приведем текст процедуры поиска/вставки в хэш-таблицу. Если элемент найден, то он возвращается. Если элемент не найден и задан флаг создания create, то lookup добавляет элемент в таблицу. Копия имени символа не создается – считается, что вызывающая сторона сама сделала себе надежную копию.
