54.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 Association Lists) and property lists (see 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 SXEmacs 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 (without the : character), as well as the additional keyword data, which specifies the initial hash table contents.

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) or equal. 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.

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 or equal.

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.