2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1999, 2003 Free Software Foundation, Inc.
4 @c See the file elisp.texi for copying conditions.
5 @setfilename ../info/hash
6 @node Hash Tables, Symbols, Sequences Arrays Vectors, Top
10 A hash table is a very fast kind of lookup table, somewhat like
11 an alist in that it maps keys to corresponding values. It differs
12 from an alist in these ways:
16 Lookup in a hash table is extremely fast for large tables---in fact, the
17 time required is essentially @emph{independent} of how many elements are
18 stored in the table. For smaller tables (a few tens of elements)
19 alists may still be faster because hash tables have a more-or-less
23 The correspondences in a hash table are in no particular order.
26 There is no way to share structure between two hash tables,
27 the way two alists can share a common tail.
30 Emacs Lisp (starting with Emacs 21) provides a general-purpose hash
31 table data type, along with a series of functions for operating on them.
32 Hash tables have no read syntax, and print in hash notation, like this:
36 @result{} #<hash-table 'eql nil 0/65 0x83af980>
40 (The term ``hash notation'' refers to the initial @samp{#}
41 character---@pxref{Printed Representation}---and has nothing to do with
42 the term ``hash table.'')
44 Obarrays are also a kind of hash table, but they are a different type
45 of object and are used only for recording interned symbols
46 (@pxref{Creating Symbols}).
56 @section Creating Hash Tables
58 The principal function for creating a hash table is
59 @code{make-hash-table}.
61 @tindex make-hash-table
62 @defun make-hash-table &rest keyword-args
63 This function creates a new hash table according to the specified
64 arguments. The arguments should consist of alternating keywords
65 (particular symbols recognized specially) and values corresponding to
68 Several keywords make sense in @code{make-hash-table}, but the only two
69 that you really need to know about are @code{:test} and @code{:weakness}.
72 @item :test @var{test}
73 This specifies the method of key lookup for this hash table. The
74 default is @code{eql}; @code{eq} and @code{equal} are other
79 Keys which are numbers are ``the same'' if they are @code{equal}, that
80 is, if they are equal in value and either both are integers or both
81 are floating point numbers; otherwise, two distinct objects are never
85 Any two distinct Lisp objects are ``different'' as keys.
88 Two Lisp objects are ``the same'', as keys, if they are equal
89 according to @code{equal}.
92 You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to
93 define additional possibilities for @var{test}.
95 @item :weakness @var{weak}
96 The weakness of a hash table specifies whether the presence of a key or
97 value in the hash table preserves it from garbage collection.
99 The value, @var{weak}, must be one of @code{nil}, @code{key},
100 @code{value}, @code{key-or-value}, @code{key-and-value}, or @code{t}
101 which is an alias for @code{key-or-value}. If @var{weak} is @code{key}
102 then the hash table does not prevent its keys from being collected as
103 garbage (if they are not referenced anywhere else); if a particular key
104 does get collected, the corresponding association is removed from the
107 If @var{weak} is @code{value}, then the hash table does not prevent
108 values from being collected as garbage (if they are not referenced
109 anywhere else); if a particular value does get collected, the
110 corresponding association is removed from the hash table.
112 If @var{weak} is @code{key-or-value} or @code{t}, the hash table does
113 not protect either keys or values from garbage collection; if either
114 one is collected as garbage, the association is removed.
116 If @var{weak} is @code{key-and-value}, associations are removed from
117 the hash table when both their key and value would be collected as
118 garbage, again not considering references to the key and value from
121 The default for @var{weak} is @code{nil}, so that all keys and values
122 referenced in the hash table are preserved from garbage collection. If
123 @var{weak} is @code{t}, neither keys nor values are protected (that is,
126 @item :size @var{size}
127 This specifies a hint for how many associations you plan to store in the
128 hash table. If you know the approximate number, you can make things a
129 little more efficient by specifying it this way. If you specify too
130 small a size, the hash table will grow automatically when necessary, but
131 doing that takes some extra time.
133 The default size is 65.
135 @item :rehash-size @var{rehash-size}
136 When you add an association to a hash table and the table is ``full,''
137 it grows automatically. This value specifies how to make the hash table
138 larger, at that time.
140 If @var{rehash-size} is an integer, it should be positive, and the hash
141 table grows by adding that much to the nominal size. If
142 @var{rehash-size} is a floating point number, it had better be greater
143 than 1, and the hash table grows by multiplying the old size by that
146 The default value is 1.5.
148 @item :rehash-threshold @var{threshold}
149 This specifies the criterion for when the hash table is ``full.'' The
150 value, @var{threshold}, should be a positive floating point number, no
151 greater than 1. The hash table is ``full'' whenever the actual number of
152 entries exceeds this fraction of the nominal size. The default for
153 @var{threshold} is 0.8.
158 @defun makehash &optional test
159 This is equivalent to @code{make-hash-table}, but with a different style
160 argument list. The argument @var{test} specifies the method
163 This function is obsolete. Use @code{make-hash-table} instead.
167 @section Hash Table Access
169 This section describes the functions for accessing and storing
170 associations in a hash table.
173 @defun gethash key table &optional default
174 This function looks up @var{key} in @var{table}, and returns its
175 associated @var{value}---or @var{default}, if @var{key} has no
176 association in @var{table}.
180 @defun puthash key value table
181 This function enters an association for @var{key} in @var{table}, with
182 value @var{value}. If @var{key} already has an association in
183 @var{table}, @var{value} replaces the old associated value.
187 @defun remhash key table
188 This function removes the association for @var{key} from @var{table}, if
189 there is one. If @var{key} has no association, @code{remhash} does
192 @b{Common Lisp note:} In Common Lisp, @code{remhash} returns
193 non-@code{nil} if it actually removed an association and @code{nil}
194 otherwise. In Emacs Lisp, @code{remhash} always returns @code{nil}.
199 This function removes all the associations from hash table @var{table},
200 so that it becomes empty. This is also called @dfn{clearing} the hash
203 @b{Common Lisp note:} In Common Lisp, @code{clrhash} returns the empty
204 @var{table}. In Emacs Lisp, it returns @code{nil}.
208 @defun maphash function table
209 This function calls @var{function} once for each of the associations in
210 @var{table}. The function @var{function} should accept two
211 arguments---a @var{key} listed in @var{table}, and its associated
216 @section Defining Hash Comparisons
219 You can define new methods of key lookup by means of
220 @code{define-hash-table-test}. In order to use this feature, you need
221 to understand how hash tables work, and what a @dfn{hash code} means.
223 You can think of a hash table conceptually as a large array of many
224 slots, each capable of holding one association. To look up a key,
225 @code{gethash} first computes an integer, the hash code, from the key.
226 It reduces this integer modulo the length of the array, to produce an
227 index in the array. Then it looks in that slot, and if necessary in
228 other nearby slots, to see if it has found the key being sought.
230 Thus, to define a new method of key lookup, you need to specify both a
231 function to compute the hash code from a key, and a function to compare
234 @tindex define-hash-table-test
235 @defun define-hash-table-test name test-fn hash-fn
236 This function defines a new hash table test, named @var{name}.
238 After defining @var{name} in this way, you can use it as the @var{test}
239 argument in @code{make-hash-table}. When you do that, the hash table
240 will use @var{test-fn} to compare key values, and @var{hash-fn} to compute
241 a ``hash code'' from a key value.
243 The function @var{test-fn} should accept two arguments, two keys, and
244 return non-@code{nil} if they are considered ``the same.''
246 The function @var{hash-fn} should accept one argument, a key, and return
247 an integer that is the ``hash code'' of that key. For good results, the
248 function should use the whole range of integer values for hash codes,
249 including negative integers.
251 The specified functions are stored in the property list of @var{name}
252 under the property @code{hash-table-test}; the property value's form is
253 @code{(@var{test-fn} @var{hash-fn})}.
258 This function returns a hash code for Lisp object @var{obj}.
259 This is an integer which reflects the contents of @var{obj}
260 and the other Lisp objects it points to.
262 If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash
263 @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer.
265 If the two objects are not equal, the values returned by @code{sxhash}
266 are usually different, but not always; once in a rare while, by luck,
267 you will encounter two distinct-looking objects that give the same
268 result from @code{sxhash}.
271 This example creates a hash table whose keys are strings that are
272 compared case-insensitively.
275 (defun case-fold-string= (a b)
276 (compare-strings a nil nil b nil nil t))
278 (defun case-fold-string-hash (a)
281 (define-hash-table-test 'case-fold 'case-fold-string=
282 'case-fold-string-hash))
284 (make-hash-table :test 'case-fold)
287 Here is how you could define a hash table test equivalent to the
288 predefined test value @code{equal}. The keys can be any Lisp object,
289 and equal-looking objects are considered the same key.
292 (define-hash-table-test 'contents-hash 'equal 'sxhash)
294 (make-hash-table :test 'contents-hash)
298 @section Other Hash Table Functions
300 Here are some other functions for working with hash tables.
303 @defun hash-table-p table
304 This returns non-@code{nil} if @var{table} is a hash table object.
307 @tindex copy-hash-table
308 @defun copy-hash-table table
309 This function creates and returns a copy of @var{table}. Only the table
310 itself is copied---the keys and values are shared.
313 @tindex hash-table-count
314 @defun hash-table-count table
315 This function returns the actual number of entries in @var{table}.
318 @tindex hash-table-test
319 @defun hash-table-test table
320 This returns the @var{test} value that was given when @var{table} was
321 created, to specify how to hash and compare keys. See
322 @code{make-hash-table} (@pxref{Creating Hash}).
325 @tindex hash-table-weakness
326 @defun hash-table-weakness table
327 This function returns the @var{weak} value that was specified for hash
331 @tindex hash-table-rehash-size
332 @defun hash-table-rehash-size table
333 This returns the rehash size of @var{table}.
336 @tindex hash-table-rehash-threshold
337 @defun hash-table-rehash-threshold table
338 This returns the rehash threshold of @var{table}.
341 @tindex hash-table-size
342 @defun hash-table-size table
343 This returns the current nominal size of @var{table}.
347 arch-tag: 3b5107f9-d2f0-47d5-ad61-3498496bea0e