Хеш-таблицы

Хеш-таблица — это очень быстрый тип таблицы поиска, чем-то похожая на список ассоциаций (см. Ассоциативные списки) в том, что она сопоставляет ключи соответствующим значениям. Она отличается от списка ассоциаций следующим:

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

Emacs Lisp предоставляет универсальный тип данных хеш-таблицы, а также ряд функций для работы с ними. Хеш-таблицы имеют специальное представление в формате вывода, которое состоит из ‘#s’ и списка, определяющего свойства и содержимое хеш-таблицы. См. Создание хеш-таблицы. (Нотация хеш, начальный символ ‘#’, используемый в формате вывода объектов без представления для чтения, не имеет ничего общего с хеш-таблицами. См. Представление в формате вывода.)

Объекты-массивы (obarrays) также являются типом хеш-таблицы, но они представляют собой другой тип объектов и используются только для записи интернированных символов (см. Создание символов).