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

Вы можете определять новые методы поиска ключей с помощью 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, поскольку реализация хеш-функций использует некоторые особенности хранения объектов, которые могут меняться между сеансами и на разных архитектурах.