53. Hash Tables

Function: hash-table-p object

This function returns t if object is a hash table, else nil.

53.1 Introduction to Hash Tables

A hash table is a data structure that provides mappings from arbitrary Lisp objects called keys to other arbitrary Lisp objects called values. A key/value pair is sometimes called an entry in the hash table. There are many ways other than hash tables of implementing the same sort of mapping, e.g. association lists (see section 11.8 Association Lists) and property lists (see section 11.9 Property Lists), but hash tables provide much faster lookup when there are many entries in the mapping. Hash tables are an implementation of the abstract data type dictionary, also known as associative array.

Internally, hash tables are hashed using the linear probing hash table implementation method. This method hashes each key to a particular spot in the hash table, and then scans forward sequentially until a blank entry is found. To look up a key, hash to the appropriate spot, then search forward for the key until either a key is found or a blank entry stops the search. This method is used in preference to double hashing because of changes in recent hardware. The penalty for non-sequential access to memory has been increasing, and this compensates for the problem of clustering that linear probing entails.

When hash tables are created, the user may (but is not required to) specify initial properties that influence performance.

Use the :size parameter to specify the number of entries that are likely to be stored in the hash table, to avoid the overhead of resizing the table. But if the pre-allocated space for the entries is never used, it is simply wasted and makes XEmacs slower. Excess unused hash table entries exact a small continuous performance penalty, since they must be scanned at every garbage collection. If the number of entries in the hash table is unknown, simply avoid using the :size keyword.

Use the :rehash-size and :rehash-threshold keywords to adjust the algorithm for deciding when to rehash the hash table. For temporary hash tables that are going to be very heavily used, use a small rehash threshold, for example, 0.4 and a large rehash size, for example 2.0. For permanent hash tables that will be infrequently used, specify a large rehash threshold, for example 0.8.

Hash tables can also be created by the lisp reader using structure syntax, for example:

#s(hash-table :size 20 :data (foo 1 bar 2))

The structure syntax accepts the same keywords as make-hash-table, as well as the additional keyword data, which specifies the initial hash table contents. Older versions of XEmacs required that the keywords not have the initial ":" in the structure syntax, and this version of XEmacs still supports that syntax, but you cannot mix the two styles within one structure.

Function: make-hash-table &key test size rehash-size rehash-threshold weakness

This function returns a new empty hash table object.

Keyword :test can be eq, eql (default), equal, or equalp. Comparison between keys is done using this function. If speed is important, consider using eq. When storing strings in the hash table, you will likely need to use equal, or equalp for case-insensitivity.

Keyword :size specifies the number of keys likely to be inserted. This number of entries can be inserted without enlarging the hash table.

Keyword :rehash-size must be a float greater than 1.0, and specifies the factor by which to increase the size of the hash table when enlarging.

Keyword :rehash-threshold must be a float between 0.0 and 1.0, and specifies the load factor of the hash table which triggers enlarging.

Non-standard keyword :weakness can be nil (default), t, key-and-value, key, value or key-or-value. t is an alias for key-and-value.

A key-and-value-weak hash table, also known as a fully-weak or simply as a weak hash table, is one whose pointers do not count as GC referents: for any key-value pair in the hash table, if the only remaining pointer to either the key or the value is in a weak hash table, then the pair will be removed from the hash table, and the key and value collected. A non-weak hash table (or any other pointer) would prevent the object from being collected.

A key-weak hash table is similar to a fully-weak hash table except that a key-value pair will be removed only if the key remains unmarked outside of weak hash tables. The pair will remain in the hash table if the key is pointed to by something other than a weak hash table, even if the value is not.

A value-weak hash table is similar to a fully-weak hash table except that a key-value pair will be removed only if the value remains unmarked outside of weak hash tables. The pair will remain in the hash table if the value is pointed to by something other than a weak hash table, even if the key is not.

A key-or-value-weak hash table is similar to a fully-weak hash table except that a key-value pair will be removed only if the value and the key remain unmarked outside of weak hash tables. The pair will remain in the hash table if the value or key are pointed to by something other than a weak hash table, even if the other is not.

Function: copy-hash-table hash-table

This function returns a new hash table which contains the same keys and values as hash-table. The keys and values will not themselves be copied.

Function: hash-table-count hash-table

This function returns the number of entries in hash-table.

Function: hash-table-test hash-table

This function returns the test function of hash-table. This can be one of eq, eql, equal, equalp, or some name parameter given to define-hash-table-test.

Function: hash-table-size hash-table

This function returns the current number of slots in hash-table, whether occupied or not.

Function: hash-table-rehash-size hash-table

This function returns the current rehash size of hash-table. This is a float greater than 1.0; the factor by which hash-table is enlarged when the rehash threshold is exceeded.

Function: hash-table-rehash-threshold hash-table

This function returns the current rehash threshold of hash-table. This is a float between 0.0 and 1.0; the maximum load factor of hash-table, beyond which the hash-table is enlarged by rehashing.

Function: hash-table-weakness hash-table

This function returns the weakness of hash-table. This can be one of nil, t, key or value.

53.2 Working With Hash Tables

Function: puthash key value hash-table

This function hashes key to value in hash-table.

Function: gethash key hash-table &optional default

This function finds the hash value for key in hash-table. If there is no entry for key in hash-table, default is returned (which in turn defaults to nil).

Function: remhash key hash-table

This function removes the entry for key from hash-table. Does nothing if there is no entry for key in hash-table.

Function: clrhash hash-table

This function removes all entries from hash-table, leaving it empty.

Function: maphash function hash-table

This function maps function over entries in hash-table, calling it with two args, each key and value in the hash table.

function may not modify hash-table, with the one exception that function may remhash or puthash the entry currently being processed by function.

Function: define-hash-table-test name test-function hash-function

Creates a new hash table test function, beyond the four specified by Common Lisp. name is a symbol, and define-hash-table-test will error if there exists a hash table test with that name already. (If you want to repeatedly define hash tables, use a symbol generated with gensym for name).

test-function must accept two arguments and return non-nil if both arguments are the same.

hash-function must accept one argument and return an integer hash code for its argument. hash-function should use the entire range of the underlying C long type, typically represented with two more value bits than the Lisp fixnum type.

Returns t on success, an incompatibility with GNU Emacs, which returns a list comprising test-function and hash-function.

53.3 Weak Hash Tables

A weak hash table is a special variety of hash table whose elements do not count as GC referents. For any key-value pair in such a hash table, if either the key or value (or in some cases, if one particular one of the two) has no references to it outside of weak hash tables (and similar structures such as weak lists), the pair will be removed from the table, and the key and value collected. A non-weak hash table (or any other pointer) would prevent the objects from being collected.

Weak hash tables are useful for keeping track of information in a non-obtrusive way, for example to implement caching. If the cache contains objects such as buffers, markers, image instances, etc. that will eventually disappear and get garbage-collected, using a weak hash table ensures that these objects are collected normally rather than remaining around forever, long past their actual period of use. (Otherwise, you'd have to explicitly map over the hash table every so often and remove unnecessary elements.)

There are four types of weak hash tables:

key-and-value-weak hash tables

In these hash tables, also known as fully weak or simply as weak hash tables, a pair disappears if either the key or the value is unreferenced outside of the table.

key-weak hash tables

In these hash tables, a pair disappears if the key is unreferenced outside of the table, regardless of how the value is referenced.

value-weak hash tables

In these hash tables, a pair disappears if the value is unreferenced outside of the table, regardless of how the key is referenced.

key-or-value-weak hash tables

In these hash tables, a pair disappears if both the key and the value are unreferenced outside of the table.

Also see 11.10 Weak Lists.

Weak hash tables are created by specifying the :weakness keyword to make-hash-table.