X-Git-Url: http://git.chise.org/gitweb/?a=blobdiff_plain;f=man%2Flispref%2Fhash-tables.texi;h=570207230114d0e63c16aaf52d82226249f0206a;hb=92df8fbd6762631be0dd5e4acc215d36a074df98;hp=eccf794507237b99b7747f464028cc5b98d0e3fd;hpb=6883ee56ec887c2c48abe5b06b5e66aa74031910;p=chise%2Fxemacs-chise.git- diff --git a/man/lispref/hash-tables.texi b/man/lispref/hash-tables.texi index eccf794..5702072 100644 --- a/man/lispref/hash-tables.texi +++ b/man/lispref/hash-tables.texi @@ -7,8 +7,8 @@ @chapter Hash Tables @cindex hash table -@defun hashtablep object -This function returns non-@code{nil} if @var{object} is a hash table. +@defun hash-table-p object +This function returns @code{t} if @var{object} is a hash table, else @code{nil}. @end defun @menu @@ -23,79 +23,172 @@ This function returns non-@code{nil} if @var{object} is a hash table. @node Introduction to Hash Tables @section Introduction to Hash Tables -A hash table is a data structure that provides mappings from -arbitrary Lisp objects (called @dfn{keys}) to other arbitrary Lisp -objects (called @dfn{values}). There are many ways other than -hash tables of implementing the same sort of mapping, e.g. -association lists (@pxref{Association Lists}) and property lists -(@pxref{Property Lists}), but hash tables provide much faster lookup. - -When you create a hash table, you specify a size, which indicates the -expected number of elements that the table will hold. You are not -bound by this size, however; hash tables automatically resize themselves -if the number of elements becomes too large. - -(Internally, hash tables are hashed using a modification of the -@dfn{linear probing} hash table 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. The modification -actually used is called @dfn{double hashing} and involves moving forward -by a fixed increment, whose value is computed from the original hash -value, rather than always moving forward by one. This eliminates -problems with clustering that can arise from the simple linear probing -method. For more information, see @cite{Algorithms} (second edition) -by Robert Sedgewick, pp. 236-241.) - -@defun make-hashtable size &optional test-fun -This function makes a hash table of initial size @var{size}. Comparison -between keys is normally done with @code{eql}; i.e. two keys must be the -same object to be considered equivalent. However, you can explicitly -specify the comparison function using @var{test-fun}, which must be -one of @code{eq}, @code{eql}, or @code{equal}. - -Note that currently, @code{eq} and @code{eql} are the same. This will -change when bignums are implemented. +A @dfn{hash table} is a data structure that provides mappings from +arbitrary Lisp objects called @dfn{keys} to other arbitrary Lisp objects +called @dfn{values}. A key/value pair is sometimes called an +@dfn{entry} in the hash table. There are many ways other than hash +tables of implementing the same sort of mapping, e.g. association lists +(@pxref{Association Lists}) and property lists (@pxref{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 @dfn{dictionary}, also known as @dfn{associative array}. + +Internally, hash tables are hashed using the @dfn{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 @code{: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 @code{:size} +keyword. + +Use the @code{:rehash-size} and @code{: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: +@example +#s(hash-table size 20 data (foo 1 bar 2)) +@end example + +The structure syntax accepts the same keywords as @code{make-hash-table} +(without the @code{:} character), as well as the additional keyword +@code{data}, which specifies the initial hash table contents. + +@defun make-hash-table &key @code{test} @code{size} @code{rehash-size} @code{rehash-threshold} @code{weakness} +This function returns a new empty hash table object. + +Keyword @code{:test} can be @code{eq}, @code{eql} (default) or @code{equal}. +Comparison between keys is done using this function. +If speed is important, consider using @code{eq}. +When storing strings in the hash table, you will likely need to use @code{equal}. + +Keyword @code{:size} specifies the number of keys likely to be inserted. +This number of entries can be inserted without enlarging the hash table. + +Keyword @code{: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 @code{: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 @code{:weakness} can be @code{nil} (default), +@code{t}, @code{key-and-value}, @code{key}, @code{value} or +@code{key-or-value}. @code{t} is an alias for @code{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. @end defun -@defun copy-hashtable old-table -This function makes a new hash table which contains the same keys and -values as the given table. The keys and values will not themselves be +@defun copy-hash-table hash-table +This function returns a new hash table which contains the same keys and +values as @var{hash-table}. The keys and values will not themselves be copied. @end defun -@defun hashtable-fullness table -This function returns number of entries in @var{table}. +@defun hash-table-count hash-table +This function returns the number of entries in @var{hash-table}. +@end defun + +@defun hash-table-test hash-table +This function returns the test function of @var{hash-table}. +This can be one of @code{eq}, @code{eql} or @code{equal}. +@end defun + +@defun hash-table-size hash-table +This function returns the current number of slots in @var{hash-table}, +whether occupied or not. +@end defun + +@defun hash-table-rehash-size hash-table +This function returns the current rehash size of @var{hash-table}. +This is a float greater than 1.0; the factor by which @var{hash-table} +is enlarged when the rehash threshold is exceeded. +@end defun + +@defun hash-table-rehash-threshold hash-table +This function returns the current rehash threshold of @var{hash-table}. +This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of +@var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing. +@end defun + +@defun hash-table-weakness hash-table +This function returns the weakness of @var{hash-table}. +This can be one of @code{nil}, @code{t}, @code{key} or @code{value}. @end defun @node Working With Hash Tables @section Working With Hash Tables -@defun puthash key val table -This function hashes @var{key} to @var{val} in @var{table}. +@defun puthash key value hash-table +This function hashes @var{key} to @var{value} in @var{hash-table}. @end defun -@defun gethash key table &optional default -This function finds the hash value for @var{key} in @var{table}. If -there is no corresponding value, @var{default} is returned (defaults to -@code{nil}). +@defun gethash key hash-table &optional default +This function finds the hash value for @var{key} in @var{hash-table}. +If there is no entry for @var{key} in @var{hash-table}, @var{default} is +returned (which in turn defaults to @code{nil}). @end defun -@defun remhash key table -This function removes the hash value for @var{key} in @var{table}. +@defun remhash key hash-table +This function removes the entry for @var{key} from @var{hash-table}. +Does nothing if there is no entry for @var{key} in @var{hash-table}. @end defun -@defun clrhash table -This function flushes @var{table}. Afterwards, the hash table will -contain no entries. +@defun clrhash hash-table +This function removes all entries from @var{hash-table}, leaving it empty. @end defun -@defun maphash function table -This function maps @var{function} over entries in @var{table}, calling -it with two args, each key and value in the table. +@defun maphash function hash-table +This function maps @var{function} over entries in @var{hash-table}, +calling it with two args, each key and value in the hash table. + +@var{function} may not modify @var{hash-table}, with the one exception +that @var{function} may remhash or puthash the entry currently being +processed by @var{function}. @end defun + @node Weak Hash Tables @section Weak Hash Tables @cindex hash table, weak @@ -119,33 +212,25 @@ remaining around forever, long past their actual period of use. (Otherwise, you'd have to explicitly map over the hash table every so often and remove unnecessary elements.) -There are three types of weak hash tables: +There are four types of weak hash tables: @table @asis -@item fully weak hash tables -In these hash tables, a pair disappears if either the key or the value -is unreferenced outside of the table. +@item key-and-value-weak hash tables +In these hash tables, also known as fully weak or simply as weak hash +tables, a pair disappears if either the key or the value is unreferenced +outside of the table. @item key-weak hash tables In these hash tables, a pair disappears if the key is unreferenced outside of the table, regardless of how the value is referenced. @item value-weak hash tables In these hash tables, a pair disappears if the value is unreferenced outside of the table, regardless of how the key is referenced. +@item key-or-value-weak hash tables +In these hash tables, a pair disappears if both the key and the value +are unreferenced outside of the table. @end table Also see @ref{Weak Lists}. -@defun make-weak-hashtable size &optional test-fun -This function makes a fully weak hash table of initial size @var{size}. -@var{test-fun} is as in @code{make-hashtable}. -@end defun - -@defun make-key-weak-hashtable size &optional test-fun -This function makes a key-weak hash table of initial size @var{size}. -@var{test-fun} is as in @code{make-hashtable}. -@end defun - -@defun make-value-weak-hashtable size &optional test-fun -This function makes a value-weak hash table of initial size @var{size}. -@var{test-fun} is as in @code{make-hashtable}. -@end defun +Weak hash tables are created by specifying the @code{:weakness} keyword to +@code{make-hash-table}.