Хеш-таблицы: быстрый словарь Common Lisp

Хеш-таблицы Common Lisp: создание, тесты сравнения, gethash с setf, обход, и почему выбор :test определяет, какие ключи «равны».

Хеш-таблица — изменяемая структура, отображающая ключи в значения с амортизированным доступом за O(1); в Common Lisp способ сравнения ключей задаётся параметром :test при создании.

Зачем это: быстрый словарь для серьёзных объёмов

Когда отображение перестаёт быть «маленьким и редким», alist/plist с их линейным поиском уступают место хеш-таблицам. Хеш-таблица хранит ключи так, что доступ, вставка и удаление выполняются в среднем за константное время независимо от размера. Это рабочая лошадка любых индексов, кешей, подсчётов, множеств. В Common Lisp хеш-таблица — встроенный тип с продуманным API, и ключевая особенность, отличающая её от «словарей» многих языков, — явный выбор предиката равенства ключей при создании. Понимание этого выбора критично: от него зависит, какие ключи таблица считает одинаковыми.

Почему вообще доступ за «амортизированный O(1)» — это так ценно, стоит прочувствовать на примере масштаба. Линейный поиск в alist из 10 000 элементов в среднем перебирает 5 000 пар на каждый запрос; в цикле из 10 000 запросов это 50 миллионов сравнений — заметная задержка. Хеш-таблица на тех же данных делает по сути одно обращение на запрос, то есть 10 000 операций вместо 50 миллионов — разница в тысячи раз. Именно поэтому индексы баз данных, кеши, таблицы символов компиляторов, подсчёт частот в текстах — всё это строится на хешировании. Освоить хеш-таблицы — значит получить инструмент, превращающий квадратичные по времени решения в линейные, а это часто граница между «работает за секунды» и «висит минутами». Эта тема — не про синтаксис, а про алгоритмическую эффективность вашего кода.

Создание и четыре теста

Таблицу создаёт make-hash-table. Самый важный аргумент — :test, задающий, как сравниваются ключи. Допустимы ровно четыре стандартных предиката, по возрастанию «мягкости»:

По умолчанию :test — eql. Это значит: если вы хотите ключи-строки, обязательно укажите :test 'equal (или equalp для регистронезависимости), иначе две одинаковые на вид строки будут разными ключами (они не eql). Это самая частая ошибка с хеш-таблицами в CL.

;; для строковых ключей — :test 'equal
(defparameter *colors* (make-hash-table :test 'equal))

(setf (gethash "red" *colors*) "#FF0000")
(setf (gethash "green" *colors*) "#00FF00")

(gethash "red" *colors*)       ; => "#FF0000", T
(gethash "blue" *colors*)      ; => NIL, NIL  (нет ключа)

gethash, setf и два значения

Чтение — (gethash key table). Тонкость: gethash возвращает два значения — само значение и булев флаг «ключ присутствовал». Это позволяет отличить «ключ есть, но его значение nil» от «ключа нет вовсе». Записывают через setf места (gethash key table) — это идиоматичный способ вставки/обновления.

;; третий аргумент gethash — значение по умолчанию, если ключа нет
(gethash "blue" *colors* "неизвестно")   ; => "неизвестно", NIL

;; различить «нет ключа» и «значение nil» по второму значению:
(multiple-value-bind (val present-p) (gethash "red" *colors*)
  (if present-p
      (format t "есть: ~a~%" val)
      (format t "ключ отсутствует~%")))

;; идиома подсчёта: увеличить счётчик, начиная с 0
(defparameter *counts* (make-hash-table :test 'equal))
(dolist (w '("a" "b" "a" "a" "b"))
  (incf (gethash w *counts* 0)))          ; default 0 для нового ключа
(gethash "a" *counts*)                     ; => 3

Паттерн (incf (gethash key table 0)) — канонический подсчёт частот: третий аргумент 0 даёт стартовое значение для отсутствующего ключа, а incf через setf кладёт обновлённое. Удаление ключа — (remhash key table), проверка наличия — по второму значению gethash, размер — (hash-table-count table).

Этот паттенр заслуживает разбора, потому что в нём элегантно сходятся несколько механизмов Lisp. (gethash key table 0) возвращает текущий счётчик или 0, если ключа ещё нет. incf — это макрос, который работает с «обобщёнными местами» (generalized places): он умеет увеличивать не только переменные, но и любое setf-устанавливаемое место, включая (gethash ...). Под капотом (incf (gethash key table 0)) разворачивается примерно в «прочитать значение по ключу (или 0), прибавить 1, записать обратно по ключу». То есть одна короткая строка выражает «увеличь счётчик, создав его при первом появлении» — задачу, которая в языках без обобщённых мест требует явной проверки наличия и ветвления. Это демонстрирует, как setf-места и значения по умолчанию складываются в идиому, которую достаточно увидеть один раз, чтобы использовать всюду: подсчёт слов, голосов, вхождений, гистограммы — всё это один и тот же приём.

Обход хеш-таблицы

Хеш-таблица не упорядочена, но её можно обойти. Два способа: функция высшего порядка maphash (вызывает вашу функцию для каждой пары) и макрос-цикл loop с being the hash-keys/hash-values.

;; maphash: функция от (ключ значение) для каждой пары
(maphash (lambda (k v)
           (format t "~a => ~a~%" k v))
         *counts*)

;; через loop (подробнее о loop — в продвинутом разделе):
(loop for k being the hash-keys of *counts*
        using (hash-value v)
      collect (cons k v))         ; => alist из всех пар

;; собрать все ключи / значения:
(loop for k being the hash-keys of *counts* collect k)
(loop for v being the hash-values of *counts* collect v)

Важно: порядок обхода не определён и может меняться. Если нужен порядок, соберите пары и отсортируйте отдельно. Внутри maphash разрешено удалять текущий ключ (remhash), но не добавлять новые — это неопределённое поведение.

Хеш-таблицы как множества и индексы

Помимо «ключ → значение», хеш-таблица — естественное множество: храните ключи со значением t, и проверка принадлежности — это gethash. Это даёт быстрый «видели ли мы уже X», дедупликацию, пересечения. Также таблицы — основа индексов: «по полю → список записей». Эти применения делают хеш-таблицу, пожалуй, самой используемой изменяемой структурой в практическом коде.

Стоит отдельно отметить идиому хеш-таблица как индекс «один-ко-многим», потому что она встречается постоянно и красиво сочетается с уже изученным. Часто нужно сгруппировать записи по какому-то полю: студентов по группе, заказы по клиенту, слова по первой букве. Решение — таблица, где значение каждого ключа — это список (или вектор) записей, и вы дописываете в него через push. Стартовое значение для нового ключа — пустой список, поэтому (push item (gethash key table '())) работает «из коробки»: третий аргумент '() даёт пустой список для ещё не встреченного ключа, а push через setf кладёт обновлённый. Получается группировка за один проход и в линейное время — типичная задача, которая на alist была бы мучительно медленной. Этот приём — комбинация всего, что мы прошли: хеш-таблица для скорости, список как значение, push и setf-место. Он показывает, как структуры данных Lisp складываются в выразительные решения.

;; множество увиденных элементов (дедупликация)
(defun unique (lst)
  (let ((seen (make-hash-table :test 'equal))
        (result '()))
    (dolist (x lst (nreverse result))
      (unless (gethash x seen)
        (setf (gethash x seen) t)         ; пометить как увиденный
        (push x result)))))

(unique '("a" "b" "a" "c" "b"))   ; => ("a" "b" "c")

Контраст со Scheme

В стандартном R7RS-small хеш-таблиц нет в ядре — это сознательный минимализм; их предоставляют SRFI-69 или библиотеки реализации (а R7RS-large включает hash-table-библиотеку). API похож по сути: создание с предикатом и хеш-функцией, hash-table-ref/hash-table-set!. Racket же имеет богатые встроенные make-hash/make-hasheq/make-hashequal — заметьте, выбор сравнения там зашит в имя конструктора, тогда как в Common Lisp он передаётся параметром :test. Это снова отражает стилевое различие: CL параметризует одну сущность, Scheme/Racket дают набор именованных вариантов.

Как работает под капотом

Хеш-таблица хранит ключи в массиве «корзин» (buckets). Для ключа вычисляется хеш-код — число, определяющее корзину; внутри корзины ключи сравниваются выбранным :test. Хорошая хеш-функция «размазывает» ключи равномерно, поэтому корзины короткие и доступ — почти O(1). Когда таблица заполняется (коэффициент загрузки превышен), происходит рехеширование: создаётся больший массив и ключи перераспределяются — отсюда «амортизированный» O(1) (редкая дорогая операция размазана по многим дешёвым). Связь :test и хеша строгая: хеш-функция обязана согласоваться с предикатом — равные по :test ключи должны давать одинаковый хеш. Поэтому допустимы лишь четыре стандартных :test (под каждый есть корректная встроенная хеш-функция); произвольный предикат без согласованной хеш-функции использовать нельзя (для этого есть нестандартные расширения вроде :hash-function в SBCL). Это требование согласованности — не каприз, а математическая необходимость: если два «равных» ключа получат разные хеши, они попадут в разные корзины, и таблица «потеряет» совпадение. Именно поэтому нельзя просто передать любую свою функцию сравнения — нужна пара «предикат + хеш», которые согласованы между собой, а стандарт гарантирует это лишь для четырёх встроенных вариантов.

Частые ошибки

• Строковые ключи с дефолтным :test. По умолчанию eql — строки так не совпадают. Для строк нужен :test 'equal (или equalp).
• Игнорировать второе значение gethash. Чтобы отличить «ключа нет» от «значение nil», смотрите второе возвращаемое значение (present-p).
• Полагаться на порядок обхода. Хеш-таблица не упорядочена; порядок maphash/loop не определён. Нужен порядок — сортируйте собранные пары.
• Добавлять ключи во время maphash. Удалять текущий можно, добавлять новые — неопределённое поведение.
• Брать хеш-таблицу для крошечных отображений. На 3–5 элементах alist/plist проще и часто быстрее; хеш-таблица оправдана объёмом или частотой доступа.

Итоги

• make-hash-table создаёт таблицу; :test (eq/eql/equal/equalp) задаёт, какие ключи равны; по умолчанию eql.
• Для строковых ключей нужен :test 'equal — иначе одинаковые строки будут разными ключами.
• Чтение — gethash (возвращает значение и флаг наличия; есть значение по умолчанию); запись — (setf (gethash ...)).
• Идиома подсчёта — (incf (gethash key table 0)); множество — ключи со значением t.
• Обход — maphash или loop ... being the hash-keys/values; порядок не определён.
• Под капотом — корзины + хеш-функция, согласованная с :test; рехеширование даёт амортизированный O(1).

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