Глава 16
Хеш-таблицы

 16.1 Функции для хеш-таблиц
 16.2 Функция хеширования

Хеш-таблица является Lisp’овыми объектом, который может быстро отображать заданный Lisp’овый объект в другой Lisp’овый объект. Wikipedia более понятно излагает: это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Каждая хеш-таблица содержит множество элементов, каждый из которых содержит значение ассоциированное с ключом. Базовые функции взаимодействия с хеш-таблицей могут создавать элементы (пары ключ-значение), удалять элементы и искать значения по заданному ключу. Поиск значения очень быстрый, даже при наличии большого количества элементов, потому что используется хеширование. Это самое важное преимущество хеш-таблиц перед списками свойств.

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

Хеш-таблицы существуют в трёх видах, различие между ними в том, как сравниваются ключи, с помощью eq, eql или equal. Другими словами, существуют хеш таблицы с ключами, которые используют Lisp’овые объекты (eq или eql) и которые используют древовидные структуры (equal). FIXME

Хеш-таблицы создаются функцией make-hash-table, которая принимает различные параметры, включая тип хеш-таблицы (по-умолчанию тип eql). Для поиска значения по ключу используйте gethash. Новые элементы могут быть добавлены с помощью gethash внутри setf. Для удаления элементов используйте remhash. Вот простой пример.

(setq a (make-hash-table))
(setf (gethash ’color a) ’brown)
(setf (gethash ’name a) ’fred)
(gethash ’color a)  brown
(gethash ’name a)  fred
(gethash ’pointy a)  nil

В этом примере, символы color и name используются в качестве ключей, а символы brown и fred в качестве ассоциированных значений. Хеш-таблица содержит две пары, в одной ключ color связан с brown, а в другой name с fred.

Ключи необязательно должны быть символами. Они могут быть любыми Lisp’овыми объектами. Значения также могут быть любыми Lisp’овыми объектами.

There is a discrepancy between the preceding description of the size of a hash table and the description of the :size argument in the specification below of make-hash-table.

X3J13 voted in June 1989 to regard the latter description as definitive: the :size argument is approximately the number of entries that can be inserted without having to enlarge the hash table. This definition is certainly more convenient for the user.