# HG changeset patch # User Richard M. Stallman # Date 937013146 0 # Node ID 0d3bc0a437c4195fd75c627852e0cf4043e51ab2 # Parent ddf2e1fef00bf7bebf7368edda388e81bf2d018c Initial revision diff -r ddf2e1fef00b -r 0d3bc0a437c4 lispref/hash.texi --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lispref/hash.texi Sat Sep 11 01:25:46 1999 +0000 @@ -0,0 +1,304 @@ +@c -*-texinfo-*- +@c This is part of the GNU Emacs Lisp Reference Manual. +@c Copyright (C) 1999 Free Software Foundation, Inc. +@c See the file elisp.texi for copying conditions. +@setfilename ../info/hash +@node Hash Tables, Symbols, Sequences Arrays Vectors, Top +@chapter Hash Tables +@cindex hash tables + + A hash table is a very fast kind of lookup table, somewhat like +an alist in that it maps keys to corresponding values. It differs +from an alist in these ways: + +@itemize @bullet +@item +Lookup in a hash table is extremely fast---in fact, the time required +is essentially @emph{independent} of how many elements are stored +in the table. + +@item +The correspondences in a hash table are in no particular order. + +@item +There is no way to share structure between two hash tables, +the way two alists can share a common tail. +@end itemize + + Emacs Lisp (starting with Emacs 21) provides a general-purpose hash +table data type, along with a series of functions for operating on them. +Hash tables have no read syntax, and print in hash notation, like this: + +@example +(make-hash-table) + @result{} # +@end example + + Obarrays are also a kind of hash table, but they are a different type +of object and are used only for recording interned symbols +(@pxref{Creating Symbols}). + +@menu +* Creating Hash:: +* Hash Access:: +* Defining Hash:: +* Other Hash:: +@end menu + +@node Creating Hash +@section Creating Hash Tables + + The principal function for creating a hash table is +@code{make-hash-table}. + +@tindex make-hash-table +@defun make-hash-table &rest keyword-args +This function creates a new hash table according to the specified +arguments. The arguments should consist of alternating keywords +(particular symbols recognized specially) and values corresponding to +them. + +Several keywords make sense in @code{make-hash-table}, but the only two +that you really need to know about are @code{:test} and @code{:weak}. + +@table @code +@item :test @var{test} +This specifies the method of key lookup for this hash table. The +default is @code{eql}; @code{eq} and @code{equal} are other +alternatives: + +@table @code +@item eql +Keys which are numbers are ``the same'' if they are equal in value; +otherwise, two distinct objects are never ``the same''. + +@item eq +Any two distinct Lisp objects are ``different'' as keys. + +@item equal +Two Lisp objects are ``the same'', as keys, if they are equal +according to @code{equal}. +@end table + +You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to +define additional possibilities for @var{test}. + +@item :weakness @var{weak} +The weakness of a hash table specifies whether the presence of a key or +value in the hash table preserves it from garbage collection. + +The value, @var{weak}, must be one of @code{nil}, @code{key}, +@code{value} or @code{t}. If @var{weak} is @code{key} or @code{t}, then +the hash table does not prevent its keys from being collected as garbage +(if they are not referenced anywhere else); if a particular key does get +collected, the corresponding association is removed from the hash table. + +Likewise, if @var{weak} is @code{value} or @code{t}, then the hash table +does not prevent values from being collected as garbage (if they are not +referenced anywhere else); if a particular value does get collected, the +corresponding association is removed from the hash table. + +The default for @var{weak} is @code{nil}, so that all keys and values +referenced in the hash table are preserved from garbage collection. + +@item :size @var{size} +This specifies a hint for how many associations you plan to store in the +hash table. If you know the approximate number, you can make things a +little more efficient by specifying it this way. If you specify to +small a size, the hash table will grow automatically when necessary, but +doing that takes some extra time, + +The default size is 65. + +@item :rehash-size @var{rehash-size} +When you add an association to a hash table and the table is ``full,'' +it grows automatically. This value specifies how to make the hash table +larger, at that time. + +If @var{rehash-size} is an integer, it had better be positive, and the +hash table grows by adding that much to the size. If @var{rehash-size} +is a floating point number, it had better be greater than 1, and the +hash table grows by multiplying the old size by that number. + +The default value is 1.5. + +@item :rehash-threshold @var{threshold} +This specifies the criterion for when the hash table is ``full.'' The +value, @var{threshold}, should be a positive floating point number, no +greater than 1. The hash table is ``full'' whenever the actual number of +entries exceeds this fraction of the nominal size. The default for +@var{threshold} is 0.8. +@end table +@end defun + +@tindex makehash +@defun makehash &optional test +This is equivalent to @code{make-hash-table}, but with a different style +argument list. The argument @var{test} specifies the method +of key lookup. + +If you want to specify other parameters, you should use +@code{make-hash-table}. +@end defun + +@node Hash Access +@section Hash Table Access + + This section describes the functions for accessing and storing +associations in a hash table. + +@tindex gethash +@defun gethash key table &optional default +This function looks up @var{key} in @var{table}, and returns its +associated @var{value}---or @var{default}, if @var{key} has no +association in @var{table}. +@end defun + +@tindex puthash +@defun puthash key value table +This function enters an association for @var{key} in @var{table}, with +value @var{value}. If @var{key} already has an association in +@var{table}, @var{value} replaces the old associated value. +@end defun + +@tindex remhash +@defun remhash key table +This function removes the association for @var{key} from @var{table}, if +there is one. If @var{key} has no association, @code{remhash} does +nothing. +@end defun + +@tindex clrhash +@defun clrhash table +This function removes all the associations from hash table @var{table}, +so that it becomes empty. This is also called @dfn{clearing} the hash +table. +@end defun + +@tindex maphash +@defun maphash function table +This function calls @var{function} once for each of the associations in +@var{table}. The function @var{function} should accept two +arguments---a @var{key} listed in @var{table}, and its associated +@var{value}. +@end defun + +@node Defining Hash +@section Defining Hash Comparisons +@cindex hash code + + You can define new methods of key lookup by means of +@code{define-hash-table-test}. In order to use this feature, you need +to understand how hash tables work, and what a @dfn{hash code} means. + + You can think of a hash table conceptually as a large array of many +slots, each capable of holding one association. To look up a key, +@code{gethash} first computes an integer, the hash code, from the key. +It reduces this integer modulo the length of the array, to produce an +index in the array. Then it looks in that slot, and if necessary in +other nearby slots, to see if it has found the key being sought. + + Thus, to define a new method of key lookup, you need to specify both a +function to compute the hash code from a key, and a function to compare +two keys directly. + +@tindex define-hash-table-test +@defun define-hash-table-test name test-fn hash-fn +This function defines a new hash table test, named @var{name}. + +After defining @var{name} in this way, you can use it as the @var{test} +argument in @code{make-hash-table}. When you do that, the hash table +will use @var{test-fn} to compare key values, and @var{hash-fn} to compute +a ``hash code'' from a key value. + +The function @var{test-fn} should accept two arguments, two keys, and +return non-@code{nil} if they are considered ``the same.'' + +The function @var{hash-fn} should accept one argument, a key, and return +an integer that is the ``hash code'' of that key. For good results, the +function should use the whole range of integer values for hash codes, +including negative integers. + +The specified functions are stored in the property list of @var{name} +under the property @code{hash-table-test}; the property value's form is +@code{(@var{test-fn} @var{hash-fn})}. + +This example creates a hash table whose keys are strings that are +compared case-insensitively. + +@example +(defun case-fold-string= (a b) + (compare-strings a nil nil b nil nil t)) + +(defun case-fold-string-hash (a) + (sxhash (upcase a))) + +(define-hash-table-test 'case-fold 'case-fold-string= + 'case-fold-string-hash)) + +(make-hash-table :test 'case-fold) +@end example +@end defun + +@tindex sxhash +@defun sxhash obj +This function returns a hash code for Lisp object @var{obj}. +This is an integer which reflects the contents of @var{obj} +and the other Lisp objects it points to. + +If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash +@var{obj1})} and @code{(sxhash @var{obj2})} are the same integer. + +If the two objects are not equal, the values returned by @code{sxhash} +are usually different, but not always; but once in a rare while, by +luck, you will encounter two distinct-looking objects that give the same +result from @code{sxhash}. +@end defun + +@node Other Hash +@section Other Hash Table Functions + + Here are some other functions for working with hash tables. + +@tindex hash-table-p +@defun hash-table-p table +This returns non-@code{nil} if @var{table} is a hash table object. +@end defun + +@tindex copy-hash-table +@defun copy-hash-table table +This function creates and returns a copy of @var{table}. Only the table +itself is copied---the keys and values are shared. +@end defun + +@tindex hash-table-count +@defun hash-table-count table +This function returns the actual number of entries in @var{table}. +@end defun + +@tindex hash-table-rehash-test +@defun hash-table-rehash-test table +This returns the test @var{table} uses to hash and compare keys---see +@code{make-hash-table} (@pxref{Creating Hash}). +@end defun + +@tindex hash-table-weakness +@defun hash-table-weakness table +This function returns the @var{weak} value that was specified for hash +table @var{table}. +@end defun + +@tindex hash-table-rehash-size +@defun hash-table-rehash-size table +This returns the rehash size of @var{table}. +@end defun + +@tindex hash-table-rehash-threshold +@defun hash-table-rehash-threshold table +This returns the rehash threshold of @var{table}. +@end defun + +@tindex hash-table-rehash-size +@defun hash-table-rehash-size table +This returns the current nominal size of @var{table}. +@end defun