[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

__Function:__**hash-table-p***object*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.

__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),`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.

__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`

,`equal`

,`equalp`

, or some`name`parameter given to`define-hash-table-test`

.

__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`

.

[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

__Function:__**puthash***key value hash-table*This function hashes

`key`to`value`in`hash-table`.

__Function:__**gethash***key hash-table &optional default*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`

).

__Function:__**remhash***key hash-table*This function removes the entry for

`key`from`hash-table`. Does nothing if there is no entry for`key`in`hash-table`.

__Function:__**clrhash***hash-table*This function removes all entries from

`hash-table`, leaving it empty.

__Function:__**maphash***function hash-table*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`.

__Function:__**define-hash-table-test***name test-function hash-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*.