comparison - 哈希表的相等谓词

Question

由于 this通过调查，我们知道使用特殊函数(针对某些类型的数据进行优化)是一个好主意。我想创建一个哈希表，但是 this source说:

Syntax:

make-hash-table &key test size rehash-size rehash-threshold => hash-table

Arguments and Values:

test - a designator for one of the functions eq, eql, equal, or equalp. The default is eql.

好吧好吧。如果我想在使用字符串并使用 string-equal 时加快我的程序怎么办？其他高阶函数的相等谓词没有限制，但对于 make-hash-table 是。这是什么原因？

额外的“history-of-lisp”问题:为什么函数 gethash 如此命名？为什么不 get-hash？

Answer 1

什么是哈希表

散列表的工作原理是计算对象的散列并将对象存储在由散列索引的表中。测试函数必须满足所有对象 x 和 y 的基本条件:

(FUNCALL test-function x y) ⇒
(= (FUNCALL hash-function x) (FUNCALL hash-function y))

ANSI CL 标准指定了 4 个标准测试函数，并且在底层，实现具有相应的哈希函数。

定义你自己的测试/哈希

一些 CL 实现允许您定义自己的测试函数/哈希函数对，例如，

• Macro ext:define-hash-table-test
• Macro sb-ext:define-hash-table-test

您的具体问题

当表格以字符串为键时，我发现使用符号非常有利可图。

我会创建一个特殊的 package和 intern我的弦在那里。

然后我会assign相应符号的值:而不是

(defparameter *mytable* (make-hash-table :test 'equal))
(setf (gethash "foo" *mytable*) <whatever>)

我愿意

(make-package "MY-PACKAGE")
(setf (symbol-value (intern "foo" "MY-PACKAGE")) <whatever>)

这在字符串为 read 时特别方便因为 CL 阅读器为您实习。

当然有一些注意事项(例如，包必须明确为 deleted ，否则它们不会被 GC 处理)，所以这可能不是胆小的人。