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

其中 -

  • 关键参数提供了关键。

  • :test参数决定如何比较键 - 它应该具有三个值 #'eq、#'eql 或 #'equal 之一，或者三个符号 eq、eql 或 equal 之一。如果未指定，则假定为 eql。

  • :size参数设置哈希表的初始大小。这应该是一个大于零的整数。

  • :rehash-size参数指定当哈希表变满时要增加多少大小。这可以是大于零的整数，即要添加的条目数，也可以是大于 1 的浮点数，即新大小与旧大小的比率。该参数的默认值取决于实现。

  • :rehash-threshold参数指定哈希表在必须增长之前可以达到多满。这可以是大于零且小于 :rehash-size 的整数（在这种情况下，每当表增长时它将进行缩放），也可以是 0 到 1 之间的浮点数。此值的默认值参数取决于实现。

您还可以调用不带参数的 make-hash-table 函数。

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

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

它具有以下语法 -

gethash key hash-table &optional default

其中 -

  • key：是关联的键

  • hash-table: 是要搜索的哈希表

  • default：如果未找到条目，则返回值，如果未指定，则返回 nil。

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

要将项目添加到哈希表中，可以使用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函数删除哈希表中特定键的任何条目。这是一个谓词，如果有条目则为 true，如果没有条目则为 false。

该函数的语法是 -

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

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

例子

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