CODEWITHSUNDEEP
lispcommon-lispsbcl
myselfesteem
myselfesteem

Reputation: 755

Random access for hash table

I have an SBCL hash table where the hash keys are symbols. If the hash table was made with eq, will calling gethash give random access to the elements? I know these details are implementation specific, but so far I haven't been able to find a clear answer in the documentation.

Upvotes: 0

Views: 263

Answers (2)

Vsevolod Dyomkin
Vsevolod Dyomkin

Reputation: 9451

I assume (also from the discussion in the comments) that by "give random access" you mean that the distribution of elements in the hash-table will be random and hence it will have O(1) access performance. The answer is yes, it will be. There are some degraded cases like this one (Why does `sxhash` return a constant for all structs?) when the distribution becomes skewed, but this is definitely not it. For eq comparisons the implementations will use the address of an object for hashing. In the case of SBCL, here's the actual code:

(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))))

However, you can also opt to use an eql hash-table (which I'd recommend: using eq should be reserved only for those who know what they are doing :) ). For this case, SBCL has a special function to hash symbols: symbol-hash. I assume, other implementation also do something similar, for symbol is, probably, the most frequent type of hash-table keys.

Upvotes: 2

Sylwester
Sylwester

Reputation: 48735

Hash tables, by design, give O(1) access and update of their elements. It's not implementation specific.

Since hashing works differently than comparing hash tables in standard CL is limited to eq, eql (default), equal, and equalp. In reality this only means the hash value for two values considered by one of these to be true will have the same hash value. SBCL lets you define hash functions but that is not portable.

Upvotes: 0

Related Questions