哈希表（Hash Table）

优质

小牛编辑

135浏览

2023-12-01

散列表数据结构表示基于密钥的散列码组织的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

Where −

key参数提供了关键。
:test参数确定如何比较键 - 它应该具有三个值中的一个＃'eq，＃'eql或＃'相等，或者三个符号之一eq，eql或者相等。如果未指定，则假定为eql。
:size参数设置哈希表的初始大小。这应该是大于零的整数。
:rehash-size参数指定在哈希表变满时增加哈希表的大小。这可以是大于零的整数，即要添加的条目数，也可以是大于1的浮点数，即新大小与旧大小的比率。此参数的默认值取决于实现。
:rehash-threshold参数指定哈希表在必须增长之前可以获得多长。这可以是大于零且小于:rehash-size的整数（在这种情况下，它将在表生成时进行缩放），或者它可以是0到1之间的浮点数。此默认值参数依赖于实现。

您也可以在没有参数的情况下调用make-hash-table函数。

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

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

它具有以下语法 -

gethash key hash-table &optional default

Where −

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

gethash函数实际上返回两个值，第二个是谓词值，如果找到条目则为true，如果没有找到条目则为false。

要将项添加到哈希表，可以使用setf函数和gethash函数。

例子 (Example)

创建一个名为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函数删除散列表中特定键的任何条目。这是一个谓词，如果有条目则为true，如果没有则为false。

这个函数的语法是 -

remhash key hash-table

例子 (Example)

创建一个名为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函数允许您在哈希表上的每个键值对上应用指定的函数。

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

例子 (Example)

创建一个名为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)