# HG changeset patch # User Glenn Morris # Date 1189051895 0 # Node ID f29ed3b78ac8730156a560f260fd063ad761c3e9 # Parent 6b812ccc5fb406a59a4f375ac92d9913cc1b47f1 Move to ../doc/lispref diff -r 6b812ccc5fb4 -r f29ed3b78ac8 lispref/hash.texi --- 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{} # -@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