@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 likean alist in that it maps keys to corresponding values. It differsfrom an alist in these ways:@itemize @bullet@itemLookup in a hash table is extremely fast for large tables---in fact, thetime required is essentially @emph{independent} of how many elements arestored in the table. For smaller tables (a few tens of elements)alists may still be faster because hash tables have a more-or-lessconstant overhead.@itemThe correspondences in a hash table are in no particular order.@itemThere 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 hashtable 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 withthe term ``hash table.'') Obarrays are also a kind of hash table, but they are a different typeof 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-argsThis function creates a new hash table according to the specifiedarguments. The arguments should consist of alternating keywords(particular symbols recognized specially) and values corresponding tothem.Several keywords make sense in @code{make-hash-table}, but the only twothat 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. Thedefault is @code{eql}; @code{eq} and @code{equal} are otheralternatives:@table @code@item eqlKeys which are numbers are ``the same'' if they are equal in value;otherwise, two distinct objects are never ``the same''.@item eqAny two distinct Lisp objects are ``different'' as keys.@item equalTwo Lisp objects are ``the same'', as keys, if they are equalaccording to @code{equal}.@end tableYou can use @code{define-hash-table-test} (@pxref{Defining Hash}) todefine additional possibilities for @var{test}.@item :weakness @var{weak}The weakness of a hash table specifies whether the presence of a key orvalue 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 asgarbage (if they are not referenced anywhere else); if a particular keydoes get collected, the corresponding association is removed from thehash table.If @var{weak} is @code{value}, then the hash table does not preventvalues from being collected as garbage (if they are not referencedanywhere else); if a particular value does get collected, thecorresponding association is removed from the hash table.If @var{weak} is @code{key-or-value} or @code{t}, the hash table doesnot protect either keys or values from garbage collection; if eitherone is collected as garbage, the association is removed.If @var{weak} is @code{key-and-value}, associations are removed fromthe hash table when both their key and value would be collected asgarbage, again not considering references to the key and value fromweak hash tables.The default for @var{weak} is @code{nil}, so that all keys and valuesreferenced 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).@item :size @var{size}This specifies a hint for how many associations you plan to store in thehash table. If you know the approximate number, you can make things alittle more efficient by specifying it this way. If you specify toosmall a size, the hash table will grow automatically when necessary, butdoing 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 tablelarger, at that time.If @var{rehash-size} is an integer, it should be positive, and the hashtable grows by adding that much to the nominal size. If@var{rehash-size} is a floating point number, it had better be greaterthan 1, and the hash table grows by multiplying the old size by thatnumber.The default value is 1.5.@item :rehash-threshold @var{threshold}This specifies the criterion for when the hash table is ``full.'' Thevalue, @var{threshold}, should be a positive floating point number, nogreater than 1. The hash table is ``full'' whenever the actual number ofentries exceeds this fraction of the nominal size. The default for@var{threshold} is 0.8.@end table@end defun@tindex makehash@defun makehash &optional testThis is equivalent to @code{make-hash-table}, but with a different styleargument list. The argument @var{test} specifies the methodof 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 storingassociations in a hash table.@tindex gethash@defun gethash key table &optional defaultThis function looks up @var{key} in @var{table}, and returns itsassociated @var{value}---or @var{default}, if @var{key} has noassociation in @var{table}.@end defun@tindex puthash@defun puthash key value table This function enters an association for @var{key} in @var{table}, withvalue @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 tableThis function removes the association for @var{key} from @var{table}, ifthere is one. If @var{key} has no association, @code{remhash} doesnothing.@end defun@tindex clrhash@defun clrhash tableThis function removes all the associations from hash table @var{table},so that it becomes empty. This is also called @dfn{clearing} the hashtable.@end defun@tindex maphash@defun maphash function tableThis function calls @var{function} once for each of the associations in@var{table}. The function @var{function} should accept twoarguments---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 needto 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 manyslots, 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 anindex in the array. Then it looks in that slot, and if necessary inother 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 afunction to compute the hash code from a key, and a function to comparetwo keys directly.@tindex define-hash-table-test@defun define-hash-table-test name test-fn hash-fnThis 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 tablewill use @var{test-fn} to compare key values, and @var{hash-fn} to computea ``hash code'' from a key value.The function @var{test-fn} should accept two arguments, two keys, andreturn non-@code{nil} if they are considered ``the same.''The function @var{hash-fn} should accept one argument, a key, and returnan integer that is the ``hash code'' of that key. For good results, thefunction 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@tindex sxhash@defun sxhash objThis 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, byluck, you will encounter two distinct-looking objects that give the sameresult from @code{sxhash}.@end defun This example creates a hash table whose keys are strings that arecompared 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 thepredefined 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.@tindex hash-table-p@defun hash-table-p tableThis returns non-@code{nil} if @var{table} is a hash table object.@end defun@tindex copy-hash-table@defun copy-hash-table tableThis function creates and returns a copy of @var{table}. Only the tableitself is copied---the keys and values are shared.@end defun@tindex hash-table-count@defun hash-table-count tableThis function returns the actual number of entries in @var{table}.@end defun@tindex hash-table-test@defun hash-table-test tableThis returns the @var{test} value that was given when @var{table} wascreated, to specify how to hash and compare keys. See@code{make-hash-table} (@pxref{Creating Hash}).@end defun@tindex hash-table-weakness@defun hash-table-weakness tableThis function returns the @var{weak} value that was specified for hashtable @var{table}.@end defun@tindex hash-table-rehash-size@defun hash-table-rehash-size tableThis returns the rehash size of @var{table}.@end defun@tindex hash-table-rehash-threshold@defun hash-table-rehash-threshold tableThis returns the rehash threshold of @var{table}.@end defun@tindex hash-table-size@defun hash-table-size tableThis returns the current nominal size of @var{table}.@end defun