8.3 Определение сравнений хеша

Вы можете определять новые методы поиска ключей с помощью define-hash-table-test. Чтобы использовать эту функцию, вам необходимо понять, как работают хеш-таблицы, и что означает хеш-код.

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

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

Функция: define-hash-table-test name test-fn hash-fn ¶

Эта функция определяет новый тест для хеш-таблицы с именем name.

После определения name таким образом вы можете использовать его в качестве аргумента test в make-hash-table. Когда вы это делаете, хеш-таблица будет использовать test-fn для сравнения значений ключей и hash-fn для вычисления хеш-кода из значения ключа.

Функция test-fn должна принимать два аргумента, два ключа, и возвращать не-nil, если они считаются одинаковыми.

Функция hash-fn должна принимать один аргумент, ключ, и возвращать целое число, которое является хеш-кодом этого ключа. Для хороших результатов функция должна использовать весь диапазон фиксированных чисел для хеш-кодов, включая отрицательные фиксированные числа.

Указанные функции сохраняются в списке свойств name под свойством hash-table-test; форма значения свойства — (test-fn hash-fn).

Функция: sxhash-equal obj ¶

Эта функция возвращает хеш-код для объекта Lisp obj. Это целое число, отражающее содержимое obj и другие объекты Lisp, на которые он указывает.

Если два объекта obj1 и obj2 равны equal, то (sxhash-equal obj1) и (sxhash-equal obj2) будут одинаковыми целыми числами.

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

Примечание для Common Lisp: В Common Lisp аналогичная функция называется sxhash. Emacs предоставляет это имя как совместимый псевдоним для sxhash-equal.

Функция: sxhash-eq obj ¶

Эта функция возвращает хеш-код для объекта Lisp obj. Ее результат отражает идентичность obj, но не его содержимое.

Если два объекта obj1 и obj2 равны eq, то (sxhash-eq obj1) и (sxhash-eq obj2) будут одинаковыми целыми числами.

Функция: sxhash-eql obj ¶

Эта функция возвращает хеш-код для объекта Lisp obj, подходящий для сравнения eql. Другими словами, он отражает идентичность obj, за исключением случая, когда объект является большим числом или числом с плавающей запятой, в котором генерируется хеш-код для значения.

Если два объекта obj1 и obj2 равны eql, то (sxhash-eql obj1) и (sxhash-eql obj2) будут одинаковыми целыми числами.

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

(defun string-hash-ignore-case (a)
  (sxhash-equal (upcase a)))

(define-hash-table-test 'ignore-case
  'string-equal-ignore-case 'string-hash-ignore-case)

(make-hash-table :test 'ignore-case)

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

(define-hash-table-test 'contents-hash 'equal 'sxhash-equal)

(make-hash-table :test 'contents-hash)

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