-@node Hash Tables, Structures, Lists, Top
-@chapter Hash Tables
-
-@noindent
-A @dfn{hash table} is a data structure that maps ``keys'' onto
-``values.'' Keys and values can be arbitrary Lisp data objects.
-Hash tables have the property that the time to search for a given
-key is roughly constant; simpler data structures like association
-lists take time proportional to the number of entries in the list.
-
-@defun make-hash-table @t{&key :test :size}
-This function creates and returns a hash-table object whose
-function for comparing elements is @code{:test} (@code{eql}
-by default), and which is allocated to fit about @code{:size}
-elements. The @code{:size} argument is purely advisory; the
-table will stretch automatically if you store more elements in
-it. If @code{:size} is omitted, a reasonable default is used.
-
-Common Lisp allows only @code{eq}, @code{eql}, @code{equal},
-and @code{equalp} as legal values for the @code{:test} argument.
-In this package, any reasonable predicate function will work,
-though if you use something else you should check the details of
-the hashing function described below to make sure it is suitable
-for your predicate.
-
-Some versions of Emacs (like Lucid Emacs 19) include a built-in
-hash table type; in these versions, @code{make-hash-table} with
-a test of @code{eq} will use these built-in hash tables. In all
-other cases, it will return a hash-table object which takes the
-form of a list with an identifying ``tag'' symbol at the front.
-All of the hash table functions in this package can operate on
-both types of hash table; normally you will never know which
-type is being used.
-
-This function accepts the additional Common Lisp keywords
-@code{:rehash-size} and @code{:rehash-threshold}, but it ignores
-their values.
-@end defun
-
-@defun gethash key table &optional default
-This function looks up @var{key} in @var{table}. If @var{key}
-exists in the table, in the sense that it matches any of the existing
-keys according to the table's test function, then the associated value
-is returned. Otherwise, @var{default} (or @code{nil}) is returned.
-
-To store new data in the hash table, use @code{setf} on a call to
-@code{gethash}. If @var{key} already exists in the table, the
-corresponding value is changed to the stored value. If @var{key}
-does not already exist, a new entry is added to the table and the
-table is reallocated to a larger size if necessary. The @var{default}
-argument is allowed but ignored in this case. The situation is
-exactly analogous to that of @code{get*}; @pxref{Property Lists}.
-@end defun
-
-@defun remhash key table
-This function removes the entry for @var{key} from @var{table}.
-If an entry was removed, it returns @code{t}. If @var{key} does
-not appear in the table, it does nothing and returns @code{nil}.
-@end defun
-
-@defun clrhash table
-This function removes all the entries from @var{table}, leaving
-an empty hash table.
-@end defun
-
-@defun maphash function table
-This function calls @var{function} for each entry in @var{table}.
-It passes two arguments to @var{function}, the key and the value
-of the given entry. The return value of @var{function} is ignored;
-@var{maphash} itself returns @code{nil}. @xref{Loop Facility}, for
-an alternate way of iterating over hash tables.
-@end defun
-
-@defun hash-table-count table
-This function returns the number of entries in @var{table}.
-@strong{Warning:} The current implementation of Lucid Emacs 19
-hash-tables does not decrement the stored @code{count} when
-@code{remhash} removes an entry. Therefore, the return value of
-this function is not dependable if you have used @code{remhash}
-on the table and the table's test is @code{eq}. A slower, but
-reliable, way to count the entries is @code{(loop for x being the
-hash-keys of @var{table} count t)}.
-@end defun
-
-@defun hash-table-p object
-This function returns @code{t} if @var{object} is a hash table,
-@code{nil} otherwise. It recognizes both types of hash tables
-(both Lucid Emacs built-in tables and tables implemented with
-special lists.)
-@end defun
-
-Sometimes when dealing with hash tables it is useful to know the
-exact ``hash function'' that is used. This package implements
-hash tables using Emacs Lisp ``obarrays,'' which are the same
-data structure that Emacs Lisp uses to keep track of symbols.
-Each hash table includes an embedded obarray. Key values given
-to @code{gethash} are converted by various means into strings,
-which are then looked up in the obarray using @code{intern} and
-@code{intern-soft}. The symbol, or ``bucket,'' corresponding to
-a given key string includes as its @code{symbol-value} an association
-list of all key-value pairs which hash to that string. Depending
-on the test function, it is possible for many entries to hash to
-the same bucket. For example, if the test is @code{eql}, then the
-symbol @code{foo} and two separately built strings @code{"foo"} will
-create three entries in the same bucket. Search time is linear
-within buckets, so hash tables will be most effective if you arrange
-not to store too many things that hash the same.
-
-The following algorithm is used to convert Lisp objects to hash
-strings:
-
-@itemize @bullet
-@item
-Strings are used directly as hash strings. (However, if the test
-function is @code{equalp}, strings are @code{downcase}d first.)
-
-@item
-Symbols are hashed according to their @code{symbol-name}.
-
-@item
-Integers are hashed into one of 16 buckets depending on their value
-modulo 16. Floating-point numbers are truncated to integers and
-hashed modulo 16.
-
-@item
-Cons cells are hashed according to their @code{car}s; nonempty vectors
-are hashed according to their first element.
-
-@item
-All other types of objects hash into a single bucket named @code{"*"}.
-@end itemize
-
-@noindent
-Thus, for example, searching among many buffer objects in a hash table
-will devolve to a (still fairly fast) linear-time search through a
-single bucket, whereas searching for different symbols will be very
-fast since each symbol will, in general, hash into its own bucket.
-
-The size of the obarray in a hash table is automatically adjusted
-as the number of elements increases.
-
-As a special case, @code{make-hash-table} with a @code{:size} argument
-of 0 or 1 will create a hash-table object that uses a single association
-list rather than an obarray of many lists. For very small tables this
-structure will be more efficient since lookup does not require
-converting the key to a string or looking it up in an obarray.
-However, such tables are guaranteed to take time proportional to
-their size to do a search.
-