Hash Tables

Hash-table is a class to search for the value associated with a key, as accomplished by assoc. For a relatively large problem, hash-table performs better than assoc, since time required for searching remains constant even the number of key-value pairs increases. Roughly speaking, hash-table should be used in search spaces with more than 100 elements, and assoc in smaller spaces.

Hash-tables automatically expands if the number of elements in the table exceeds rehash-size. By default, expansion occurs when a half of the table is filled. sxhash function returns a hash value which is independent of memory address of an object, and hash values for equal objects are always the same. So, hash tables can be re-loadable since they use sxhash as their default hashing functions. While sxhash is robust and safe, it is relatively slow because it scans all the elements in a sequence or a tree. For faster hashing, you may choose another hash function appropriate for your application. To change the hash function, send :hash-function message to the hash-table. In simple cases, it is useful to change hash function from #'sxhash to #'sys:address. This is possible because the addresses of any objects never change in a EusLisp process.

  sxhash obj [function]

• calculates the hash value for obj. Two objects which are equal are guaranteed to yield the same hash value. For a symbol, hash value for its pname is returned. For numbers, their integer representations are returned. For a list, sum of hash values for all its elements is returned. For a string, shifted sum of each character code is returned. For any other objects, sxhash is recursively called to calculate the hash value of each slot, and the sum of them is returned.

  make-hash-table &key (size 30) (test #'eq) (rehash-size 2.0) [function]

• creates a hash table and returns it.

  gethash key htab [function]

• gets the value that corresponds to key in htab. Gethash is also used to set a value to key by combining with setf. When a new entry is entered in a hash table, and the number of filled slots in the table exceeds 1/rehash-size, then the hash table is automatically expanded to twice larger size.

  remhash key htab [function]

• removes a hash entry designated by key in htab.

  maphash function htab [function]

• maps function to all the elements of htab.

  hash-table-p x [function]

• T if x is an instance of class hash-table.

  hash-table [class]

 :super B<>object

:slots 		 (key value count

		 hash-function test-function

		 rehash-size empty deleted)

• defines hash table. Key and value are simple-vectors of the same size. Count is the number of filled slots in key and value. Hash-function is defaulted to sxhash and test-function to eq. Empty and deleted are uninterned symbols to indicate slots are empty or deleted in the key vector.

  :hash-function newhash [method]

• changes the hash function of this hash table to newhash. Newhash must be a function with one argument and returns an integer. One of candidates for newhash is system:address.