GNU Info

(elisp)Defining Hash

---

Next: Other Hash Prev: Hash Access Up: Hash Tables

---

Enter node , (file) or (file)node

Defining Hash Comparisons
=========================

   You can define new methods of key lookup by means of
`define-hash-table-test'.  In order to use this feature, you need to
understand how hash tables work, and what a "hash code" means.

   You can think of a hash table conceptually as a large array of many
slots, each capable of holding one association.  To look up a key,
`gethash' first computes an integer, the hash code, from the key.  It
reduces this integer modulo the length of the array, to produce an
index in the array.  Then it looks in that slot, and if necessary in
other nearby slots, to see if it has found the key being sought.

   Thus, to define a new method of key lookup, you need to specify both
a function to compute the hash code from a key, and a function to
compare two keys directly.

 - Function: define-hash-table-test name test-fn hash-fn
     This function defines a new hash table test, named NAME.

     After defining NAME in this way, you can use it as the TEST
     argument in `make-hash-table'.  When you do that, the hash table
     will use TEST-FN to compare key values, and HASH-FN to compute a
     "hash code" from a key value.

     The function TEST-FN should accept two arguments, two keys, and
     return non-`nil' if they are considered "the same."

     The function HASH-FN should accept one argument, a key, and return
     an integer that is the "hash code" of that key.  For good results,
     the function should use the whole range of integer values for hash
     codes, including negative integers.

     The specified functions are stored in the property list of NAME
     under the property `hash-table-test'; the property value's form is
     `(TEST-FN HASH-FN)'.

 - Function: sxhash obj
     This function returns a hash code for Lisp object OBJ.  This is an
     integer which reflects the contents of OBJ and the other Lisp
     objects it points to.

     If two objects OBJ1 and OBJ2 are equal, then `(sxhash OBJ1)' and
     `(sxhash OBJ2)' are the same integer.

     If the two objects are not equal, the values returned by `sxhash'
     are usually different, but not always; but once in a rare while, by
     luck, you will encounter two distinct-looking objects that give
     the same result from `sxhash'.

   This example creates a hash table whose keys are strings that are
compared case-insensitively.

     (defun case-fold-string= (a b)
       (compare-strings a nil nil b nil nil t))
     
     (defun case-fold-string-hash (a)
       (sxhash (upcase a)))
     
     (define-hash-table-test 'case-fold 'case-fold-string=
                             'case-fold-string-hash))
     
     (make-hash-table :test 'case-fold)

   Here is how you could define a hash table test equivalent to the
predefined test value `equal'.  The keys can be any Lisp object, and
equal-looking objects are considered the same key.

     (define-hash-table-test 'contents-hash 'equal 'sxhash)
     
     (make-hash-table :test 'contents-hash)