-\1f
-File: lispref.info, Node: Introduction to Hash Tables, Next: Working With Hash Tables, Up: Hash Tables
-
-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 (*note
-Association Lists::) and property lists (*note 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'
-(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.
-
- Keyword `:weakness' can be `nil' (default), `t', `key' or `value'.
-
- 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.
-
- - 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'.