LISP — Хеш-таблица

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

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

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

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

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

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

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

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

Где —

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

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

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

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

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

Ключевой аргумент предоставляет ключ.

Аргумент : 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

где —

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

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

• default: возвращаемое значение, если запись не найдена, которая равна nil, если не указана.

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

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

default: возвращаемое значение, если запись не найдена, которая равна nil, если не указана.

Функция gethash на самом деле возвращает два значения, второе — это значение предиката, которое имеет значение true, если запись была найдена, и false, если запись не была найдена.

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

пример

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

Live Demo

(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 key hash-table

(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

(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)