[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This function returns t
if object is a hash table, else nil
.
53.1 Introduction to Hash Tables | Hash tables are fast data structures for implementing simple tables (i.e. finite mappings from keys to values). | |
53.2 Working With Hash Tables | Hash table functions. | |
53.3 Weak Hash Tables | Hash tables with special garbage-collection behavior. |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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 section Association Lists) and property lists (see section 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
, as well as the additional keyword data
,
which specifies the initial hash table contents. Older versions of
XEmacs required that the keywords not have the initial “:” in the
structure syntax, and this version of XEmacs still supports that syntax,
but you cannot mix the two styles within one structure.
test
size
rehash-size
rehash-threshold
weakness
This function returns a new empty hash table object.
Keyword :test
can be eq
, eql
(default),
equal
, or equalp
.
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
, or equalp
for case-insensitivity.
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.
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.
This function returns the number of entries in hash-table.
This function returns the test function of hash-table.
This can be one of eq
, eql
, equal
, equalp
,
or some name parameter given to define-hash-table-test
.
This function returns the current number of slots in hash-table, whether occupied or not.
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.
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.
This function returns the weakness of hash-table.
This can be one of nil
, t
, key
or value
.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This function hashes key to value in hash-table.
This function finds the hash value for key in hash-table.
If there is no entry for key in hash-table, default is
returned (which in turn defaults to nil
).
This function removes the entry for key from hash-table. Does nothing if there is no entry for key in hash-table.
This function removes all entries from hash-table, leaving it empty.
This function maps function over entries in hash-table, calling it with two args, each key and value in the hash table.
function may not modify hash-table, with the one exception that function may remhash or puthash the entry currently being processed by function.
Creates a new hash table test function, beyond the four specified by
Common Lisp. name is a symbol, and define-hash-table-test
will error if there exists a hash table test with that name already.
(If you want to repeatedly define hash tables, use a symbol generated
with gensym
for name).
test-function must accept two arguments and return non-nil if both arguments are the same.
hash-function must accept one argument and return an integer hash code for its argument. hash-function should use the entire range of the underlying C long type, typically represented with two more value bits than the Lisp fixnum type.
Returns t on success, an incompatibility with GNU Emacs, which returns a list comprising test-function and hash-function.
Weak hash tables are created by specifying the :weakness
keyword to
make-hash-table
.
[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated by Aidan Kehoe on December 27, 2016 using texi2html 1.82.