Mercurial > emacs

--- a/lispref/hash.texi	Thu Sep 06 04:11:29 2007 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,337 +0,0 @@
-@c -*-texinfo-*-
-@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1999, 2001, 2002, 2003, 2004, 2005,
-@c   2006, 2007  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
-@cindex lookup tables
-
-  A hash table is a very fast kind of lookup table, somewhat like an
-alist (@pxref{Association Lists}) 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 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.
-
-@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 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::       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
-@section Creating Hash Tables
-@cindex creating hash tables
-
-  The principal function for creating a hash table is
-@code{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{:weakness}.
-
-@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 @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.
-
-@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}, @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.
-
-@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.
-
-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 should be positive, and the hash
-table grows by adding that much to the nominal 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'' (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
-
-@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.
-
-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.  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.
-
-@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
-
-@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
-
-@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.
-
-@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
-
-@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.
-
-@b{Common Lisp note:} In Common Lisp, @code{clrhash} returns the empty
-@var{table}.  In Emacs Lisp, it returns @code{nil}.
-@end defun
-
-@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}.  @code{maphash} returns @code{nil}.
-@end defun
-
-@node Defining Hash
-@section Defining Hash Comparisons
-@cindex hash code
-@cindex define hash comparisons
-
-  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.
-
-@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})}.
-@end defun
-
-@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
-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
-
-  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.
-
-@example
-(define-hash-table-test 'contents-hash 'equal 'sxhash)
-
-(make-hash-table :test 'contents-hash)
-@end example
-
-@node Other Hash
-@section Other Hash Table Functions
-
-  Here are some other functions for working with hash tables.
-
-@defun hash-table-p table
-This returns non-@code{nil} if @var{table} is a hash table object.
-@end defun
-
-@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
-
-@defun hash-table-count table
-This function returns the actual number of entries in @var{table}.
-@end defun
-
-@defun hash-table-test table
-This returns the @var{test} value that was given when @var{table} was
-created, to specify how to hash and compare keys.  See
-@code{make-hash-table} (@pxref{Creating Hash}).
-@end defun
-
-@defun hash-table-weakness table
-This function returns the @var{weak} value that was specified for hash
-table @var{table}.
-@end defun
-
-@defun hash-table-rehash-size table
-This returns the rehash size of @var{table}.
-@end defun
-
-@defun hash-table-rehash-threshold table
-This returns the rehash threshold of @var{table}.
-@end defun
-
-@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