LISP - хеш-таблица

Структура данных хэш-таблицы представляет собой набор key-and-valueпары, организованные на основе хэш-кода ключа. Он использует ключ для доступа к элементам в коллекции.

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

Создание хеш-таблицы в LISP

В Common LISP хеш-таблица - это коллекция общего назначения. Вы можете использовать произвольные объекты в качестве ключа или индексов.

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

В LISP хеш-таблицы можно разделить на три типа в зависимости от способа сравнения ключей - eq, eql или равные. Если хеш-таблица объектов LISP хешируется, ключи сравниваются с eq или eql. Если хеш-таблица имеет хеш-структуру древовидной структуры, то она будет сравниваться с использованием равенства.

В make-hash-tableфункция используется для создания хеш-таблицы. Синтаксис этой функции -

make-hash-table &key :test :size :rehash-size :rehash-threshold

Где -

• В key Аргумент предоставляет ключ.

• В :testАргумент определяет, как сравниваются ключи - он должен иметь одно из трех значений # 'eq, #' eql или # 'равное или один из трех символов eq, eql или равный. Если не указано, предполагается eql.

• В :sizeАргумент устанавливает начальный размер хеш-таблицы. Это должно быть целое число больше нуля.

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

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

Вы также можете вызвать функцию make-hash-table без аргументов.

Получение элементов из и добавление элементов в хэш-таблицу

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

Он имеет следующий синтаксис -

gethash key hash-table &optional default

где -

• ключ: это связанный ключ

• hash-table: это хеш-таблица для поиска

• по умолчанию: значение, которое должно быть возвращено, если запись не найдена, равное нулю, если не указано.

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

Для добавления элемента в хеш-таблицу вы можете использовать setf функции вместе с gethash функция.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList))

Когда вы выполняете код, он возвращает следующий результат -

(CHARLIE BROWN)
(FREDDIE SEAL)

Удаление записи

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

Синтаксис этой функции -

remhash key hash-table

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList)) 
(terpri)
(write (gethash '003 empList))  
(remhash '003 empList)
(terpri)
(write (gethash '003 empList))

Когда вы выполняете код, он возвращает следующий результат -

(CHARLIE BROWN)
(FREDDIE SEAL)
(MARK MONGOOSE)
NIL

Функция maphash

В maphash функция позволяет применять указанную функцию к каждой паре ключ-значение в хеш-таблице.

Он принимает два аргумента - функцию и хеш-таблицу и вызывает функцию один раз для каждой пары ключ / значение в хеш-таблице.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)

Когда вы выполняете код, он возвращает следующий результат -

3 => (MARK MONGOOSE)
2 => (FREDDIE SEAL)
1 => (CHARLIE BROWN)