哈希的随机访问 table

Question

我有一个 SBCL 散列 table，其中散列键是符号。如果散列 table 是用 eq 生成的，调用 gethash 会随机访问元素吗？我知道这些细节是特定于实现的，但到目前为止我还没有能够在文档中找到明确的答案。

Answer 1

哈希表的设计使其元素的访问和更新时间复杂度为 O(1)。它不是特定于实现的。

由于哈希的工作方式不同于比较标准 CL 中的哈希表，因此仅限于 eq、eql（默认）、equal 和 equalp。实际上，这仅意味着其中之一认为为真的两个值的哈希值将具有相同的哈希值。 SBCL 允许您定义散列函数，但它不可移植。

Answer 2

我假设（同样来自评论中的讨论）“提供随机访问”意味着 hash-table 中元素的分布将是随机的，因此它将具有 O(1) 访问权限表现。答案是肯定的，会的。当分布变得倾斜时，有一些像这个 (Why does `sxhash` return a constant for all structs?) 这样的降级情况，但绝对不是这样。对于 eq 比较，实现将使用对象的地址进行散列。对于 SBCL，实际代码如下：

(defun eq-hash (key)
  (declare (values hash (member t nil)))
  ;; I think it would be ok to pick off SYMBOL here and use its hash slot
  ;; as far as semantics are concerned, but EQ-hash is supposed to be
  ;; the lightest-weight in terms of speed, so I'm letting everything use
  ;; address-based hashing, unlike the other standard hash-table hash functions
  ;; which try use the hash slot of certain objects.
  (values (pointer-hash key)
          (sb-vm:is-lisp-pointer (get-lisp-obj-address key))))

但是，您也可以选择使用 eql hash-table（我建议：使用 eq 应该只为那些知道自己在做什么的人保留：））。对于这种情况，SBCL 有一个特殊的函数来散列符号：symbol-hash。我假设，其他实现也做类似的事情，因为符号可能是最常见的 hash-table 键类型。

哈希的随机访问 table

Random access for hash table

lisp

sbcl

common-lisp