Lists Top Structures
A hash table is a data structure that maps ``keys'' onto ``values.'' Keys and values can be arbitrary Lisp data objects. Hash tables have the property that the time to search for a given key is roughly constant; simpler data structures like association lists take time proportional to the number of entries in the list.
&key :test :size
eqlby default), and which is allocated to fit about
:sizeargument is purely advisory; the table will stretch automatically if you store more elements in it. If
:sizeis omitted, a reasonable default is used.
Common Lisp allows only
equalp as legal values for the
In this package, any reasonable predicate function will work,
though if you use something else you should check the details of
the hashing function described below to make sure it is suitable
for your predicate.
Some versions of Emacs (like Lucid Emacs 19) include a built-in
hash table type; in these versions,
a test of
eq will use these built-in hash tables. In all
other cases, it will return a hash-table object which takes the
form of a list with an identifying ``tag'' symbol at the front.
All of the hash table functions in this package can operate on
both types of hash table; normally you will never know which
type is being used.
This function accepts the additional Common Lisp keywords
:rehash-threshold, but it ignores
nil) is returned.
To store new data in the hash table, use
setf on a call to
gethash. If key already exists in the table, the
corresponding value is changed to the stored value. If key
does not already exist, a new entry is added to the table and the
table is reallocated to a larger size if necessary. The default
argument is allowed but ignored in this case. The situation is
exactly analogous to that of
get*; see Property Lists.
t. If key does not appear in the table, it does nothing and returns
nil. See Loop Facility, for an alternate way of iterating over hash tables.
remhashremoves an entry. Therefore, the return value of this function is not dependable if you have used
remhashon the table and the table's test is
eq. A slower, but reliable, way to count the entries is
(loop for x being the hash-keys of table count t).
tif object is a hash table,
nilotherwise. It recognizes both types of hash tables (both Lucid Emacs built-in tables and tables implemented with special lists.)
Sometimes when dealing with hash tables it is useful to know the
exact ``hash function'' that is used. This package implements
hash tables using Emacs Lisp ``obarrays,'' which are the same
data structure that Emacs Lisp uses to keep track of symbols.
Each hash table includes an embedded obarray. Key values given
gethash are converted by various means into strings,
which are then looked up in the obarray using
intern-soft. The symbol, or ``bucket,'' corresponding to
a given key string includes as its
symbol-value an association
list of all key-value pairs which hash to that string. Depending
on the test function, it is possible for many entries to hash to
the same bucket. For example, if the test is
eql, then the
foo and two separately built strings
create three entries in the same bucket. Search time is linear
within buckets, so hash tables will be most effective if you arrange
not to store too many things that hash the same.
The following algorithm is used to convert Lisp objects to hash strings:
equalp, strings are
cars; nonempty vectors are hashed according to their first element.
Thus, for example, searching among many buffer objects in a hash table will devolve to a (still fairly fast) linear-time search through a single bucket, whereas searching for different symbols will be very fast since each symbol will, in general, hash into its own bucket.
The size of the obarray in a hash table is automatically adjusted as the number of elements increases.
As a special case,
make-hash-table with a
of 0 or 1 will create a hash-table object that uses a single association
list rather than an obarray of many lists. For very small tables this
structure will be more efficient since lookup does not require
converting the key to a string or looking it up in an obarray.
However, such tables are guaranteed to take time proportional to
their size to do a search.