Lisp - 哈希表

哈希表数据结构表示基于键的哈希码组织的键值对集合。它使用键来访问集合中的元素。

当您需要使用键访问元素，并且可以识别有用的键值时，可以使用哈希表。哈希表中的每个项目都具有键值对。键用于访问集合中的项目。

在LISP中创建哈希表

在 Common LISP 中，哈希表是一种通用的集合。您可以使用任意对象作为键或索引。

当您将值存储在哈希表中时，您会创建一个键值对，并将其存储在该键下。稍后，您可以使用相同的键从哈希表中检索该值。每个键只映射到一个值，尽管您可以将新值存储在同一个键下。

在 LISP 中，哈希表可以根据键的比较方式分为三种类型：eq、eql 或 equal。如果哈希表对 LISP 对象进行哈希，则键将使用 eq 或 eql 进行比较。如果哈希表对树结构进行哈希，则将使用 equal 进行比较。

make-hash-table 函数用于创建哈希表。此函数的语法如下：

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

其中：

key 参数提供键。
:test 参数确定如何比较键 - 它应该具有三个值之一：#'eq、#'eql 或 #'equal，或三个符号 eq、eql 或 equal 之一。如果未指定，则假定为 eql。
:size 参数设置哈希表的初始大小。这应该是一个大于零的整数。
:rehash-size 参数指定当哈希表变满时增加哈希表大小的幅度。这可以是一个大于零的整数（要添加的条目数），也可以是一个大于 1 的浮点数（新大小与旧大小的比率）。此参数的默认值取决于实现。
:rehash-threshold 参数指定哈希表在必须增长之前可以达到多满。这可以是一个大于零且小于 :rehash-size 的整数（在这种情况下，每当表增长时都会对其进行缩放），也可以是一个介于零和 1 之间的浮点数。此参数的默认值取决于实现。

您也可以不带任何参数调用 make-hash-table 函数。

从哈希表中检索项目和向哈希表中添加项目

gethash 函数通过搜索其键来从哈希表中检索项目。如果找不到键，则返回 nil。

它的语法如下：

gethash key hash-table &optional default

其中：

key：是关联的键
hash-table：是要搜索的哈希表
default：如果未找到条目，则返回的值为 nil，如果未指定则为 nil。

gethash 函数实际上返回两个值，第二个值是一个谓词值，如果找到条目则为真，如果未找到条目则为假。

要向哈希表添加项目，您可以使用setf 函数以及gethash 函数。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

main.lisp

; create a hashtable
(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
; print the value for 001 from hashtable
(write (gethash '001 empList))
; terminate printing 
(terpri)
; print the value for 002 from hashtable
(write (gethash '002 empList))

输出

执行代码时，它返回以下结果：

(CHARLIE BROWN)
(FREDDIE SEAL)

删除条目

remhash 函数删除哈希表中特定键的任何条目。这是一个谓词，如果存在条目则为真，如果不存在条目则为假。

此函数的语法如下：

remhash key hash-table

示例

更新名为 main.lisp 的源代码文件，并在其中键入以下代码。

main.lisp

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

; print the hash for 001 from hashtable
(write (gethash '001 empList))
; terminate printing  
(terpri)
; print the hash for 002 from hashtable
(write (gethash '002 empList))
; terminate printing 
(terpri)
; print the hash for 003 from hashtable
(write (gethash '003 empList))
; remove hash value
(remhash '003 empList)
; terminate printing 
(terpri)
; print the hash for 001 from hashtable
(write (gethash '003 empList))

输出

执行代码时，它返回以下结果：

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

maphash 函数

maphash 函数允许您将指定函数应用于哈希表上的每个键值对。

它接受两个参数 - 函数和哈希表，并为哈希表中的每个键值对调用一次函数。

示例

更新名为 main.lisp 的源代码文件，并在其中键入以下代码。

main.lisp

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

; map hash on hashtable
(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)

输出

执行代码时，它返回以下结果：

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

打印页面