@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1999 Free Software Foundation, Inc.
+@c Copyright (C) 1999, 2002, 2003, 2004, 2005,
+@c 2006 Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../info/hash
@node Hash Tables, Symbols, Sequences Arrays Vectors, Top
@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.
+Lookup in a hash table is extremely fast for large tables---in fact, the
+time required is essentially @emph{independent} of how many elements are
+stored in the table. For smaller tables (a few tens of elements)
+alists may still be faster because hash tables have a more-or-less
+constant overhead.
@item
The correspondences in a hash table are in no particular order.
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:
+ Emacs Lisp 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{} #<hash-table 'eql nil 0/65 0x83af980>
@end example
+@noindent
+(The term ``hash notation'' refers to the initial @samp{#}
+character---@pxref{Printed Representation}---and has nothing to do with
+the term ``hash table.'')
+
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::
+* Creating Hash:: Functions to create hash tables.
+* Hash Access:: Reading and writing the hash table contents.
+* Defining Hash:: Defining new comparison methods
+* Other Hash:: Miscellaneous.
@end menu
@node Creating Hash
@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''.
+Keys which are numbers are ``the same'' if they are @code{equal}, that
+is, if they are equal in value and either both are integers or both
+are floating point numbers; otherwise, two distinct objects are never
+``the same''.
@item eq
Any two distinct Lisp objects are ``different'' as keys.
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
+@code{value}, @code{key-or-value}, @code{key-and-value}, or @code{t}
+which is an alias for @code{key-and-value}. If @var{weak} is @code{key}
+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.
+
+If @var{weak} is @code{value}, 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.
+If @var{weak} is @code{key-and-value} or @code{t}, both the key and
+the value must be live in order to preserve the association. Thus,
+the hash table does not protect either keys or values from garbage
+collection; if either one is collected as garbage, that removes the
+association.
+
+If @var{weak} is @code{key-or-value}, either the key or
+the value can preserve the association. Thus, associations are
+removed from the hash table when both their key and value would be
+collected as garbage (if not for references from weak hash tables).
+
The default for @var{weak} is @code{nil}, so that all keys and values
-referenced in the hash table are preserved from garbage collection. If
-@var{weak} is @code{t}, neither keys nor values are protected (that is,
-both are weak).
+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 too
small a size, the hash table will grow automatically when necessary, but
-doing that takes some extra time,
+doing that takes some extra time.
The default size is 65.
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.
+This specifies the criterion for when the hash table is ``full'' (so
+it should be made larger). 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
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}.
+This function is obsolete. Use @code{make-hash-table} instead.
@end defun
@node Hash Access
@section Hash Table Access
This section describes the functions for accessing and storing
-associations in a hash table.
+associations in a hash table. In general, any Lisp object can be used
+as a hash key, unless the comparison method imposes limits. Any Lisp
+object can also be used as the value.
@tindex gethash
@defun gethash key table &optional default
@end defun
@tindex puthash
-@defun puthash key value table
+@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.
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.
+
+@b{Common Lisp note:} In Common Lisp, @code{remhash} returns
+non-@code{nil} if it actually removed an association and @code{nil}
+otherwise. In Emacs Lisp, @code{remhash} always returns @code{nil}.
@end defun
@tindex clrhash
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.
+
+@b{Common Lisp note:} In Common Lisp, @code{clrhash} returns the empty
+@var{table}. In Emacs Lisp, it returns @code{nil}.
@end defun
@tindex maphash
@defun maphash function table
+@anchor{Definition of maphash}
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}.
+@var{value}. @code{maphash} returns @code{nil}.
@end defun
@node Defining Hash
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})}.
+@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; once in a rare while, by luck,
+you will encounter two distinct-looking objects that give the same
+result from @code{sxhash}.
+@end defun
-This example creates a hash table whose keys are strings that are
+ This example creates a hash table whose keys are strings that are
compared case-insensitively.
@example
(defun case-fold-string-hash (a)
(sxhash (upcase a)))
-(define-hash-table-test 'case-fold 'case-fold-string=
- 'case-fold-string-hash))
+(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.
+ Here is how you could define a hash table test equivalent to the
+predefined test value @code{equal}. The keys can be any Lisp object,
+and equal-looking objects are considered the same key.
-If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash
-@var{obj1})} and @code{(sxhash @var{obj2})} are the same integer.
+@example
+(define-hash-table-test 'contents-hash 'equal 'sxhash)
-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
+(make-hash-table :test 'contents-hash)
+@end example
@node Other Hash
@section Other Hash Table Functions
@defun hash-table-size table
This returns the current nominal size of @var{table}.
@end defun
+
+@ignore
+ arch-tag: 3b5107f9-d2f0-47d5-ad61-3498496bea0e
+@end ignore