Common Lisp the Language
A hash table is a Lisp object that can efficiently map a given Lisp object to another Lisp object. Each hash table has a set of entries each of which associates a particular key with a particular value. The basic functions that deal with hash tables can create entries delete entries and find the value that is associated with a given key. Finding the value is very fast even if there are many entries because hashing is used; this is an important advantage of hash tables over property lists.
A given hash table can associate only one value with a given key; if you try to add a second value it will replace the first. Also adding a value to a hash table is a destructive operation; the hash table is modified. By contrast association lists can be augmented non-destructively.
Hash tables come in three kinds the difference being whether the keys are compared with eq eql or equal. In other words there are hash tables that hash on Lisp objects (using eq or eql) and there are hash tables that hash on tree structure (using equal).
Hash tables are created with the function make-hash-table which takes various options including which kind of hash table to make (the default being the eql kind). To look up a key and find the associated value use gethash. New entries are added to hash tables using setf with gethash. To remove an entry use remhash. Here is a simple example.
(setq a (make-hash-table)) (setf (gethash 'color a) 'brown) (setf (gethash 'name a) 'fred) (gethash 'color a) => brown (gethash 'name a) => fred (gethash 'pointy a) => nil
In this example the symbols color and name are being used as keys and the symbols brown and fred are being used as the associated values. The hash table has two items in it one of which associates from color to brown and the other of which associates from name to fred.
Keys do not have to be symbols; they can be any Lisp object. Similarly values can be any Lisp object.
When a hash table is first created it has a size which is the maximum number of entries it can hold. Usually the actual capacity of the table is somewhat less since the hashing is not perfectly collision-free. With the maximum possible bad luck the capacity could be very much less but this rarely happens. If so many entries are added that the capacity is exceeded the hash table will automatically grow and the entries will be rehashed (new hash values will be recomputed and everything will be rearranged so that the fast hash lookup still works). This is transparent to the caller; it all happens automatically.
There is a discrepancy between the preceding description of the size of a hash table and the description of the :size argument in the specification below of make-hash-table.
X3J13 voted in June 1989 (HASH-TABLE-SIZE) to regard the
latter description as definitive: the :size argument
is approximately the number of entries that can be inserted
without having to enlarge the hash table. This definition is certainly
more convenient for the user.