哈希表的随机访问

我假设(也来自注释中的讨论)你所说的“给予随机访问”意味着哈希表中元素的分布是随机的,因此它将具有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 情商 symbol-hash

哈希表,按设计,给O(1)访问和更新它们的元素。它不是特定于实现的。

eq , eql (默认), equal ,和 equalp . 实际上,这只意味着其中一个值为真的两个值的哈希值将具有相同的哈希值。SBCL允许您定义散列函数,但这是不可移植的。