Hash Tables
***********

 -- Function: hashtablep object
     This function returns non-nil if OBJECT is a hash table.

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).  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 you create a hash table, you specify a size, which indicates the expected number of elements that the table will hold.  You are not bound by this size, however; hash tables automatically resize themselves if the number of elements becomes too large.

(Internally, hash tables are hashed using a modification of the linear probing hash table 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.  The modification actually used is called double hashing and involves moving forward by a fixed increment, whose value is computed from the original hash value, rather than always moving forward by one.  This eliminates problems with clustering that can arise from the simple linear probing method.  For more information, see Algorithms (second edition) by Robert Sedgewick, pp. 236-241.)

 -- Function: make-hashtable size &optional test-fun
     This function makes a hash table of initial size SIZE.  Comparison between keys is normally done with eql; i.e. two keys must be the same object to be considered equivalent.  However, you can explicitly specify the comparison function using TEST-FUN, which must be one of eq, eql, or equal.

     Note that currently, eq and eql are the same.  This will change when bignums are implemented.

 -- Function: copy-hashtable old-table
     This function makes a new hash table which contains the same keys and values as the given table.  The keys and values will not themselves be copied.

 -- Function: hashtable-fullness table
     This function returns number of entries in TABLE.

Working With Hash Tables
========================

 -- Function: puthash key val table
     This function hashes KEY to VAL in TABLE.

 -- Function: gethash key table &optional default
     This function finds the hash value for KEY in TABLE.  If there is no corresponding value, DEFAULT is returned (defaults to nil).

 -- Function: remhash key table
     This function removes the hash value for KEY in TABLE.

 -- Function: clrhash table
     This function flushes TABLE.  Afterwards, the hash table will contain no entries.

 -- Function: maphash function table
     This function maps FUNCTION over entries in TABLE, calling it with two args, each key and value in the table.

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 three types of weak hash tables:

fully weak hash tables
     In these 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.

Also see Weak Lists.

 -- Function: make-weak-hashtable size &optional test-fun
     This function makes a fully weak hash table of initial size SIZE. TEST-FUN is as in make-hashtable.

 -- Function: make-key-weak-hashtable size &optional test-fun
     This function makes a key-weak hash table of initial size SIZE. TEST-FUN is as in make-hashtable.

 -- Function: make-value-weak-hashtable size &optional test-fun
     This function makes a value-weak hash table of initial size SIZE. TEST-FUN is as in make-hashtable.