Defining a Hash Function for a Custom Hash Table in SBCL

user_7016092 0
Viewed 110

The SBCL manual says one could use the following macro to define the test for a custom hash table:

(sb-ext:define-hash-table-test ht-equality-fn ht-hash-fn)

where ht-equality-fn determines whether two keys are the same, and ht-hash-fn determines the hash value for a key.

In this particular case the keys are themselves structures (defined with defstruct) with a slot containing a hash table with fixnum keys and T values (representing sets of fixnums).

If I'm understanding the SBCL requirements correctly, the straightforward way to write the ht-equality-fn would seem to be:

(defun ht-equality-fn (key1 key2)
  (equalp (ht-accessor key1) (ht-accessor key2))

But I don't know how to write the hash function to get a non-negative fixnum hash code:

(defun ht-hash-fn (ht)
  ???)

At first I thought to use sxhash, but the hyperspec says this will only work for equal keys (not equalp, as is required for hash table equality tests). Thanks for any assistance.

sbcl hashcode common-lisp
1 Answers

A quick-and-dirty hash function code is to simply sum the fixnum keys in the input ht, since the sum is the same for any arrangement of fixnums. For this problem, as it turns out, the ht fixnums are all significantly less than most-positive-fixnum, so the sum should not exceed the maximum. The worst-case hashing performance however may be deficient, given many different fixnum sets can sum to the same value.

(defun ht-hash-fn (ht)
  (declare (hash-table ht))
  (let ((sum 0))
    (declare (fixnum sum))
    (maphash (lambda (key value)
               (declare (fixnum key) (ignore value))
               (incf sum key))
      ht)
    sum))
user_70160920
Related