Регистрация | Войти
Lisp — программируемый язык программирования

Хэш-таблицы

Введение

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

Создание таблицы

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

Взятие значения из таблицы

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

Добавление элемента в таблицу

Вы можете задать значение ключа с помощью setf:

> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
> (setf (gethash 'one-entry *my-hash*) "one")
"one"
> (setf (gethash 'another-entry *my-hash*) 2/4)
1/2
> (gethash 'one-entry *my-hash*)
"one"
T
> (gethash 'another-entry *my-hash*)
1/2
T

Проверка наличия ключа в таблице

Для проверки наличия ключа в таблице вы могли бы воспользоваться первым значением, возвращаемым gethash:

> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
> (setf (gethash 'one-entry *my-hash*) "one")
"one"
> (if (gethash 'one-entry *my-hash*)
    "Key exists"
    "Key does not exist"
)

"Key exists"
> (if (gethash 'another-entry *my-hash*)
    "Key exists"
    "Key does not exist"
)

"Key does not exist"

Однако, это не сработает,если nil является значением одного из ключей:

* (defparameter *my-hash* (make-hash-table))
*MY-HASH*
* (setf (gethash 'one-entry *my-hash*) "one")
"one"
* (if (gethash 'one-entry *my-hash*)
    "Key exists"
    "Key does not exist"
)

"Key exists"
> (if (gethash 'another-entry *my-hash*)
    "Key exists"
    "Key does not exist"
)

"Key does not exist"

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

;;; продолжение
> (if (nth-value 1 (gethash 'another-entry *my-hash*))
    "Key exists"
    "Key does not exist"
)

"Key exists"
> (if (nth-value 1 (gethash 'no-entry *my-hash*))
    "Key exists"
    "Key does not exist"
)

"Key does not exist"

Удаление из таблицы

Для удаления ключа и его значения используйте remhash. remhash вернет t, если запрашиваемый к удалению ключ был найден, и nil в противном случае.

> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
> (setf (gethash 'first-key *my-hash*) 'one)
ONE
> (gethash 'first-key *my-hash*)
ONE
T
> (remhash 'first-key *my-hash*)
T
> (gethash 'first-key *my-hash*)
NIL
NIL
> (gethash 'no-entry *my-hash*)
NIL
NIL
> (remhash 'no-entry *my-hash*)
NIL
> (gethash 'no-entry *my-hash*)
NIL
NIL

Как пройтись по всей таблице

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

> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
> (setf (gethash 'first-key *my-hash*) 'one)
ONE
> (setf (gethash 'second-key *my-hash*) 'two)
TWO
> (setf (gethash 'third-key *my-hash*) nil)
NIL
> (setf (gethash nil *my-hash*) 'nil-value)
NIL-VALUE
> (defun print-hash-entry (key value)
    (format t "The value associated with the key ~S is ~S~%" key value)
)

PRINT-HASH-ENTRY
> (maphash #'print-hash-entry *my-hash*)
The value associated with the key FIRST-KEY is ONE
The value associated with the key SECOND-KEY is TWO
The value associated with the key THIRD-KEY is NIL
The value associated with the key NIL is NIL-VALUE

Также вы можете воспользоваться with-hash-table-iterator, макрос, с помощью macrolet превращающий свой первый аргумент в итератор, на каждом вхожднении возвращающий три аргумента: t/nil, ключ и соответствующее ему значение:

;;; все та же хэш-таблица
> (with-hash-table-iterator (my-iterator *my-hash*)
    (loop
      (multiple-value-bind (entry-p key value)
          (my-iterator)
        (if entry-p
            (print-hash-entry key value)
            (return)
)
)
)
)

The value associated with the key FIRST-KEY is ONE
The value associated with the key SECOND-KEY is TWO
The value associated with the key THIRD-KEY is NIL
The value associated with the key NIL is NIL-VALUE
NIL

И конечно же, loop всегда у вашим услугам:

;;; все та же таблица
> (loop for key being the hash-keys of *my-hash*
        do (print key)
)

FIRST-KEY
SECOND-KEY
THIRD-KEY
NIL
NIL
> (loop for key being the hash-keys of *my-hash*
        using (hash-value value)
        do (format t "The value associated with the key ~S is ~S~%" key value)
)

The value associated with the key FIRST-KEY is ONE
The value associated with the key SECOND-KEY is TWO
The value associated with the key THIRD-KEY is NIL
The value associated with the key NIL is NIL-VALUE
NIL
> (loop for value being the hash-values of *my-hash*
        do (print value)
)

ONE
TWO
NIL
NIL-VALUE
NIL
> (loop for value being the hash-values of *my-hash*
        using (hash-key key)
        do (format t "~&~A -> ~A" key value)
)

FIRST-KEY -> ONE
SECOND-KEY -> TWO
THIRD-KEY -> NIL
NIL -> NIL-VALUE
NIL

Подсчет элементов таблицы

Дайте своим пальцам отдохнуть - в Коммон Лиспе для этого есть встроенная функция: hash-tabel-count

> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
> (hash-table-count *my-hash*)
0
> (setf (gethash 'first *my-hash*) 1)
1
> (setf (gethash 'second *my-hash*) 2)
2
> (setf (gethash 'third *my-hash*) 3)
3
> (hash-table-count *my-hash*)
3
> (setf (gethash 'second *my-hash*) 'two)
TWO
> (hash-table-count *my-hash*)
3
> (clrhash *my-hash*)
#
> (hash-table-count *my-hash*)
0

Пара слов о производительности: размер хэш-таблиц

Функция make-hash-table умеет ряд опционных параметров, определяющих исходный размер таблицы и скорость ее роста, когда это будет необходимо. Для эффективной работы с большими таблицами эти параметры имеют большое значение. Ниже приведен пример (на sbcl 1.0.35):

* (defparameter *my-hash* (make-hash-table))
*MY-HASH*
* (hash-table-size *my-hash*)
16
* (hash-table-rehash-size *my-hash*)
1.5
* (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
(time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
Evaluation took:
 0.090 seconds of real time
 0.085987 seconds of total run time (0.079988 user, 0.005999 system)
 [ Run times consist of 0.054 seconds GC time, and 0.032 seconds non-GC time. ]
 95.56% CPU
 168,867,440 processor cycles
 5,236,016 bytes consed
NIL
CL-USER> (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
Evaluation took:
 0.025 seconds of real time
 0.013998 seconds of total run time (0.011998 user, 0.002000 system)
 56.00% CPU
 46,513,488 processor cycles
 0 bytes consed
NIL

Значения hash-table-size и hash-table-rehash-size зависят от реализации. Изначальная емкость хэш-таблицы в sbcl 16, при достижении предела емкости она увеличивается на 50%. Давайте посмотрим, как часто нам приходится изменять размер таблицы:

> (log (/ 100000 16) 1.5)
21.556
> (let ((size 16)) (dotimes (n 23) (print (list n size)) (setq size (* 1.5 size))))
(0 16)
(1 24.0)
(2 36.0)
(3 54.0)
(4 81.0)
(5 121.5)
(6 182.25)
(7 273.375)
(8 410.0625)
(9 615.09375)
(10 922.6406)
(11 1383.9609)
(12 2075.9414)
(13 3113.912)
(14 4670.868)
(15 7006.3022)
(16 10509.453)
(17 15764.18)
(18 23646.27)
(19 35469.406)
(20 53204.11)
(21 79806.164)
(22 119709.25)
NIL

Получается, что при заполнении таблицы размером 100000 из предыдущего примера, необходимо изменять ее размер 21 раз, что увеличивает затраты времени и памяти. Также это объясняет, почему повторный запуск, добавивший еще 100000 элементов в таблицу, потребовал существенно меньших затрат. Теперь давайте зададим исходную емкость таблицы достаточно большой:

* (defparameter *my-hash* (make-hash-table :size 100000))
*MY-HASH*
* (hash-table-size *my-hash*)
100000
* (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
100000
Evaluation took:
 0.024 seconds of real time
 0.014997 seconds of total run time (0.014997 user, 0.000000 system)
 62.50% CPU
 44,354,982 processor cycles
 0 bytes consed
NIL

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

@2009-2013 lisper.ru