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

Вы можете определить новые методы поиска ключей с помощью 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.

Примечание 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 case-fold-string= (a b)
  (eq t (compare-strings a nil nil b nil nil t)))
(defun case-fold-string-hash (a)
  (sxhash-equal (upcase a)))

(define-hash-table-test 'case-fold
  'case-fold-string= 'case-fold-string-hash)

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

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

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

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

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