16.1 Функции для хеш-таблиц

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

[Функция] make-hash-table &key :test :size :rehash-size :rehash-threshold

Эта функция создаёт и возвращает новую хеш-таблицу. Аргумент :test определяет как будут сравниваться ключи. Он может быть одним из трёх значений #’eq, #’eql или #’equal, или одним из трёх символов eq, eql или equal. По-умолчанию используется eql.

X3J13 voted in January 1989 to add a fourth type of hash table: the value of #’equalp and the symbol equalp are to be additional valid possibilities for the :test argument.

Note that one consequence of the vote to change the rules of floating-point contagion (described in section 12.1) is to require =, and therefore also equalp, to compare the values of numbers exactly and not approximately, making equalp a true equivalence relation on numbers.

Another valuable use of equalp hash tables is case-insensitive comparison of keys that are strings.

Аргумент :size устанавливает первоначальный размер хеш-таблицы в парах. (Указанный размер может быть округлён до «хорошего» размера, например, до первого следующего простого числа.) Вы можете не сохранять в таблице столько пар, сколько указали. Этот аргумент служит подсказкой для реализации о том, какое примерно число элементов вы будете хранить в хеш-таблице.

X3J13 voted in January 1989 to clarify that the :size argument must be a non-negative integer.

X3J13 voted in June 1989 to regard the preceding description of the :size argument as definitive: it is approximately the number of entries that can be inserted without having to enlarge the hash table.

Аргумент :rehash-size указывает, на сколько увеличить размер хеш-таблицы, когда она по размерам достигнет пределов. Если это целое число, оно должно быть больше нуля, и будет означать абсолютное приращение. Если это число с плавающей точкой, оно должно быть больше 1, и будет означать относительное приращение к предыдущему размеру. Значение по-умолчанию зависит от реализации.

Аргумент :rehash-threshold указывает, насколько должна наполниться хеш-таблица, прежде чем она будет увеличена. Он должен быть числом типа real между 0 и 1, включительно. Он показывает максимальный уровень заполнения хеш-таблицы. Значение по-умолчанию зависит от реализации.

Пример использования make-hash-table:

(make-hash-table :rehash-size 1.5
                 :size (* number-of-widgets 43))

[Функция] hash-table-p object

hash-table-p возвращает истину, если аргумент является хеш-таблицей. Иначе возвращает ложь.

(hash-table-p x) ≡ (typep x ’hash-table)

[Функция] gethash key hash-table &optional default

gethash ищет элемент в хеш-hash-table, чей ключ равен key и возвращает связанное значение. Если элемент не был найден, то возвращается значение аргумента default, который по-умолчанию равен nil.

gethash возвращает два значение. Второе значение является предикатом, и истинно, если значение было найдено, и ложно если нет.

setf может использоваться вместе с gethash для создания в хеш-таблице новых элементов. Если элемент с заданным ключом key уже существует, он будет удалён перед добавлением. В этом контексте может использоваться аргумент default, он игнорируется setf, но может быть полезным в таких макросах как incf, которые связаны с setf:

(incf (gethash a-key table 0))

обозначает то же, что и

(setf (gethash a-key table 0)
      (+ (gethash a-key table 0) 1))

что можно преобразовать в

(setf (gethash a-key table)
      (+ (gethash a-key table 0) 1))

[Функция] remhash key hash-table

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

[Функция] maphash function hash-table

Для каждого элемента в хеш-таблице hash-table, maphash вызывает функцию function с двумя аргументами: ключ элемента и значение элемента. maphash возвращает nil. Если во время выполнения maphash в хеш-таблице добавлялись или удалялись ключи, то результат непредсказуем, но есть исключение: если функция function вызывает remhash для удаления элемента, который в эту функцию и был передан, или устанавливает новое значение с помощью setf этому элементу, то эти операции будут выполнены правильно. Например:

;;; Изменение каждого элемента в MY-HASH-TABLE, с заменой на
;;; квадратный корень. Элементы с отрицательными значения удаляются.
(maphash #’(lambda (key val)
             (if (minusp val)
                 (remhash key my-hash-table)
                 (setf (gethash key my-hash-table) (sqrt val))))
         my-hash-table)

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9

[Функция] clrhash hash-table

Функция удаляет все элемент из хеш-таблицы hash-table и возвращает эту хеш-таблицу.

[Функция] hash-table-count hash-table

Функция возвращает количество элементов в хеш-таблице hash-table. Когда хеш-таблица только были сделана, или только что очищена, то количество элементов равно нулю.

[Макрос] with-hash-table-iterator (mname hash-table) {form}*

X3J13 voted in January 1989 to add the macro with-hash-table-iterator.

The name mname is bound and defined as if by macrolet, with the body forms as its lexical scope, to be a “generator macro” such that successive invocations (mname) will return entries, one by one, from the hash table that is the value of the expression hash-table (which is evaluated exactly once).

At each invocation of the generator macro, there are two possibilities. If there is yet another unprocessed entry in the hash table, then three values are returned: t, the key of the hash table entry, and the associated value of the hash table entry. On the other hand, if there are no more unprocessed entries in the hash table, then one value is returned: nil.

The implicit interior state of the iteration over the hash table entries has dynamic extent. While the name mname has lexical scope, it is an error to invoke the generator macro once the with-hash-table-iterator form has been exited.

Invocations of with-hash-table-iterator and related macros may be nested, and the generator macro of an outer invocation may be called from within an inner invocation (assuming that its name is visible or otherwise made available).

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

__________________________________________________________________________

Обоснование: This facility is a bit more flexible than maphash. It makes possible a portable and efficient implementation of loop clauses for iterating over hash tables (see chapter 26).

__________________________________________________________________________

(setq turtles (make-hash-table :size 9 :test ’eq))
(setf (gethash ’howard-kaylan turtles) ’(musician lead-singer))
(setf (gethash ’john-barbata turtles) ’(musician drummer))
(setf (gethash ’leonardo turtles) ’(ninja leader blue))
(setf (gethash ’donatello turtles) ’(ninja machines purple))
(setf (gethash ’al-nichol turtles) ’(musician guitarist))
(setf (gethash ’mark-volman turtles) ’(musician great-hair))
(setf (gethash ’raphael turtles) ’(ninja cool rude red))
(setf (gethash ’michaelangelo turtles) ’(ninja party-dude orange))
(setf (gethash ’jim-pons turtles) ’(musician bassist))

(with-hash-table-iterator (get-turtle turtles)
  (labels ((try (got-one &optional key value)
             (when got-one ;Remember, keys may show up in any order
               (when (eq (first value) ’ninja)
                 (format t "~%~:(~A~): ~{~A~̂, ~}"
                         key (rest value)))
               (multiple-value-call #’try (get-turtle)))))
    (multiple-value-call #’try (get-turtle))))     ;Prints 4 lines
Michaelangelo: PARTY-DUDE, ORANGE
Leonardo: LEADER, BLUE
Raphael: COOL, RUDE, RED
Donatello: MACHINES, PURPLE
   ⇒ nil

[Функция] hash-table-rehash-size hash-table
[Функция] hash-table-rehash-threshold hash-table
[Функция] hash-table-size hash-table
[Функция] hash-table-test hash-table

Добавлены функции, которые возвращают значения используемые при вызове make-hash-table.

hash-table-rehash-size возвращает размер приращения хеш-таблицы.

hash-table-rehash-threshold возвращает текущий уровень заполнения.

hash-table-size возвращает рекомендуемый размер хеш-таблицы.

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

(hash-table-test (make-hash-table :test #’equal)) ⇒ equal

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