Commit | Line | Data |
---|---|---|
7d15d35d RS |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Emacs Lisp Reference Manual. | |
b3d90e46 GM |
3 | @c Copyright (C) 1999, 2001, 2002, 2003, 2004, 2005, |
4 | @c 2006, 2007 Free Software Foundation, Inc. | |
7d15d35d RS |
5 | @c See the file elisp.texi for copying conditions. |
6 | @setfilename ../info/hash | |
7 | @node Hash Tables, Symbols, Sequences Arrays Vectors, Top | |
8 | @chapter Hash Tables | |
9 | @cindex hash tables | |
b6a5d601 | 10 | @cindex lookup tables |
7d15d35d | 11 | |
b6a5d601 EZ |
12 | A hash table is a very fast kind of lookup table, somewhat like an |
13 | alist (@pxref{Association Lists}) in that it maps keys to | |
14 | corresponding values. It differs from an alist in these ways: | |
7d15d35d RS |
15 | |
16 | @itemize @bullet | |
17 | @item | |
1107d4ca DL |
18 | Lookup in a hash table is extremely fast for large tables---in fact, the |
19 | time required is essentially @emph{independent} of how many elements are | |
20 | stored in the table. For smaller tables (a few tens of elements) | |
21 | alists may still be faster because hash tables have a more-or-less | |
22 | constant overhead. | |
7d15d35d RS |
23 | |
24 | @item | |
25 | The correspondences in a hash table are in no particular order. | |
26 | ||
27 | @item | |
28 | There is no way to share structure between two hash tables, | |
29 | the way two alists can share a common tail. | |
30 | @end itemize | |
31 | ||
cc5fdad9 RS |
32 | Emacs Lisp provides a general-purpose hash table data type, along |
33 | with a series of functions for operating on them. Hash tables have no | |
34 | read syntax, and print in hash notation, like this: | |
7d15d35d RS |
35 | |
36 | @example | |
37 | (make-hash-table) | |
38 | @result{} #<hash-table 'eql nil 0/65 0x83af980> | |
39 | @end example | |
40 | ||
00510a6b GM |
41 | @noindent |
42 | (The term ``hash notation'' refers to the initial @samp{#} | |
43 | character---@pxref{Printed Representation}---and has nothing to do with | |
44 | the term ``hash table.'') | |
45 | ||
7d15d35d RS |
46 | Obarrays are also a kind of hash table, but they are a different type |
47 | of object and are used only for recording interned symbols | |
48 | (@pxref{Creating Symbols}). | |
49 | ||
50 | @menu | |
38bf67d3 RS |
51 | * Creating Hash:: Functions to create hash tables. |
52 | * Hash Access:: Reading and writing the hash table contents. | |
53 | * Defining Hash:: Defining new comparison methods | |
54 | * Other Hash:: Miscellaneous. | |
7d15d35d RS |
55 | @end menu |
56 | ||
57 | @node Creating Hash | |
58 | @section Creating Hash Tables | |
2d4b90d0 | 59 | @cindex creating hash tables |
7d15d35d RS |
60 | |
61 | The principal function for creating a hash table is | |
62 | @code{make-hash-table}. | |
63 | ||
7d15d35d RS |
64 | @defun make-hash-table &rest keyword-args |
65 | This function creates a new hash table according to the specified | |
66 | arguments. The arguments should consist of alternating keywords | |
67 | (particular symbols recognized specially) and values corresponding to | |
68 | them. | |
69 | ||
70 | Several keywords make sense in @code{make-hash-table}, but the only two | |
711331aa | 71 | that you really need to know about are @code{:test} and @code{:weakness}. |
7d15d35d RS |
72 | |
73 | @table @code | |
74 | @item :test @var{test} | |
75 | This specifies the method of key lookup for this hash table. The | |
76 | default is @code{eql}; @code{eq} and @code{equal} are other | |
77 | alternatives: | |
78 | ||
79 | @table @code | |
80 | @item eql | |
b02495f1 LT |
81 | Keys which are numbers are ``the same'' if they are @code{equal}, that |
82 | is, if they are equal in value and either both are integers or both | |
e57d0aa8 | 83 | are floating point numbers; otherwise, two distinct objects are never |
827b7ee7 | 84 | ``the same.'' |
7d15d35d RS |
85 | |
86 | @item eq | |
87 | Any two distinct Lisp objects are ``different'' as keys. | |
88 | ||
89 | @item equal | |
827b7ee7 | 90 | Two Lisp objects are ``the same,'' as keys, if they are equal |
7d15d35d RS |
91 | according to @code{equal}. |
92 | @end table | |
93 | ||
94 | You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to | |
95 | define additional possibilities for @var{test}. | |
96 | ||
97 | @item :weakness @var{weak} | |
98 | The weakness of a hash table specifies whether the presence of a key or | |
99 | value in the hash table preserves it from garbage collection. | |
100 | ||
101 | The value, @var{weak}, must be one of @code{nil}, @code{key}, | |
18925e78 | 102 | @code{value}, @code{key-or-value}, @code{key-and-value}, or @code{t} |
1c673658 | 103 | which is an alias for @code{key-and-value}. If @var{weak} is @code{key} |
18925e78 GM |
104 | then the hash table does not prevent its keys from being collected as |
105 | garbage (if they are not referenced anywhere else); if a particular key | |
106 | does get collected, the corresponding association is removed from the | |
107 | hash table. | |
108 | ||
109 | If @var{weak} is @code{value}, then the hash table does not prevent | |
110 | values from being collected as garbage (if they are not referenced | |
111 | anywhere else); if a particular value does get collected, the | |
7d15d35d RS |
112 | corresponding association is removed from the hash table. |
113 | ||
2c6d3eef RS |
114 | If @var{weak} is @code{key-and-value} or @code{t}, both the key and |
115 | the value must be live in order to preserve the association. Thus, | |
116 | the hash table does not protect either keys or values from garbage | |
117 | collection; if either one is collected as garbage, that removes the | |
118 | association. | |
a9749dab | 119 | |
2c6d3eef RS |
120 | If @var{weak} is @code{key-or-value}, either the key or |
121 | the value can preserve the association. Thus, associations are | |
122 | removed from the hash table when both their key and value would be | |
123 | collected as garbage (if not for references from weak hash tables). | |
18925e78 | 124 | |
7d15d35d | 125 | The default for @var{weak} is @code{nil}, so that all keys and values |
2c6d3eef | 126 | referenced in the hash table are preserved from garbage collection. |
7d15d35d RS |
127 | |
128 | @item :size @var{size} | |
129 | This specifies a hint for how many associations you plan to store in the | |
130 | hash table. If you know the approximate number, you can make things a | |
711331aa | 131 | little more efficient by specifying it this way. If you specify too |
7d15d35d | 132 | small a size, the hash table will grow automatically when necessary, but |
00510a6b | 133 | doing that takes some extra time. |
7d15d35d RS |
134 | |
135 | The default size is 65. | |
136 | ||
137 | @item :rehash-size @var{rehash-size} | |
138 | When you add an association to a hash table and the table is ``full,'' | |
139 | it grows automatically. This value specifies how to make the hash table | |
140 | larger, at that time. | |
141 | ||
a40d4712 PR |
142 | If @var{rehash-size} is an integer, it should be positive, and the hash |
143 | table grows by adding that much to the nominal size. If | |
144 | @var{rehash-size} is a floating point number, it had better be greater | |
145 | than 1, and the hash table grows by multiplying the old size by that | |
146 | number. | |
7d15d35d RS |
147 | |
148 | The default value is 1.5. | |
149 | ||
150 | @item :rehash-threshold @var{threshold} | |
38bf67d3 RS |
151 | This specifies the criterion for when the hash table is ``full'' (so |
152 | it should be made larger). The value, @var{threshold}, should be a | |
153 | positive floating point number, no greater than 1. The hash table is | |
154 | ``full'' whenever the actual number of entries exceeds this fraction | |
155 | of the nominal size. The default for @var{threshold} is 0.8. | |
7d15d35d RS |
156 | @end table |
157 | @end defun | |
158 | ||
7d15d35d RS |
159 | @defun makehash &optional test |
160 | This is equivalent to @code{make-hash-table}, but with a different style | |
161 | argument list. The argument @var{test} specifies the method | |
162 | of key lookup. | |
163 | ||
b02495f1 | 164 | This function is obsolete. Use @code{make-hash-table} instead. |
7d15d35d RS |
165 | @end defun |
166 | ||
167 | @node Hash Access | |
168 | @section Hash Table Access | |
169 | ||
170 | This section describes the functions for accessing and storing | |
38bf67d3 RS |
171 | associations in a hash table. In general, any Lisp object can be used |
172 | as a hash key, unless the comparison method imposes limits. Any Lisp | |
173 | object can also be used as the value. | |
7d15d35d | 174 | |
7d15d35d RS |
175 | @defun gethash key table &optional default |
176 | This function looks up @var{key} in @var{table}, and returns its | |
177 | associated @var{value}---or @var{default}, if @var{key} has no | |
178 | association in @var{table}. | |
179 | @end defun | |
180 | ||
177c0ea7 | 181 | @defun puthash key value table |
7d15d35d RS |
182 | This function enters an association for @var{key} in @var{table}, with |
183 | value @var{value}. If @var{key} already has an association in | |
184 | @var{table}, @var{value} replaces the old associated value. | |
185 | @end defun | |
186 | ||
7d15d35d RS |
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 | |
190 | nothing. | |
b02495f1 LT |
191 | |
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}. | |
7d15d35d RS |
195 | @end defun |
196 | ||
7d15d35d RS |
197 | @defun clrhash table |
198 | This function removes all the associations from hash table @var{table}, | |
199 | so that it becomes empty. This is also called @dfn{clearing} the hash | |
200 | table. | |
b02495f1 LT |
201 | |
202 | @b{Common Lisp note:} In Common Lisp, @code{clrhash} returns the empty | |
203 | @var{table}. In Emacs Lisp, it returns @code{nil}. | |
7d15d35d RS |
204 | @end defun |
205 | ||
7d15d35d | 206 | @defun maphash function table |
7baeca0c | 207 | @anchor{Definition of maphash} |
7d15d35d RS |
208 | This function calls @var{function} once for each of the associations in |
209 | @var{table}. The function @var{function} should accept two | |
210 | arguments---a @var{key} listed in @var{table}, and its associated | |
38bf67d3 | 211 | @var{value}. @code{maphash} returns @code{nil}. |
7d15d35d RS |
212 | @end defun |
213 | ||
214 | @node Defining Hash | |
215 | @section Defining Hash Comparisons | |
216 | @cindex hash code | |
c115a463 | 217 | @cindex define hash comparisons |
7d15d35d RS |
218 | |
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. | |
222 | ||
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. | |
229 | ||
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 | |
232 | two keys directly. | |
233 | ||
7d15d35d RS |
234 | @defun define-hash-table-test name test-fn hash-fn |
235 | This function defines a new hash table test, named @var{name}. | |
236 | ||
237 | After defining @var{name} in this way, you can use it as the @var{test} | |
238 | argument in @code{make-hash-table}. When you do that, the hash table | |
239 | will use @var{test-fn} to compare key values, and @var{hash-fn} to compute | |
240 | a ``hash code'' from a key value. | |
241 | ||
242 | The function @var{test-fn} should accept two arguments, two keys, and | |
243 | return non-@code{nil} if they are considered ``the same.'' | |
244 | ||
245 | The function @var{hash-fn} should accept one argument, a key, and return | |
246 | an integer that is the ``hash code'' of that key. For good results, the | |
247 | function should use the whole range of integer values for hash codes, | |
248 | including negative integers. | |
249 | ||
250 | The specified functions are stored in the property list of @var{name} | |
251 | under the property @code{hash-table-test}; the property value's form is | |
252 | @code{(@var{test-fn} @var{hash-fn})}. | |
a9749dab RS |
253 | @end defun |
254 | ||
a9749dab RS |
255 | @defun sxhash obj |
256 | This function returns a hash code for Lisp object @var{obj}. | |
257 | This is an integer which reflects the contents of @var{obj} | |
258 | and the other Lisp objects it points to. | |
259 | ||
260 | If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash | |
261 | @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer. | |
262 | ||
263 | If the two objects are not equal, the values returned by @code{sxhash} | |
b02495f1 LT |
264 | are usually different, but not always; once in a rare while, by luck, |
265 | you will encounter two distinct-looking objects that give the same | |
a9749dab RS |
266 | result from @code{sxhash}. |
267 | @end defun | |
7d15d35d | 268 | |
a9749dab | 269 | This example creates a hash table whose keys are strings that are |
7d15d35d RS |
270 | compared case-insensitively. |
271 | ||
272 | @example | |
273 | (defun case-fold-string= (a b) | |
274 | (compare-strings a nil nil b nil nil t)) | |
7d15d35d RS |
275 | (defun case-fold-string-hash (a) |
276 | (sxhash (upcase a))) | |
277 | ||
848c2934 RS |
278 | (define-hash-table-test 'case-fold |
279 | 'case-fold-string= 'case-fold-string-hash) | |
7d15d35d RS |
280 | |
281 | (make-hash-table :test 'case-fold) | |
282 | @end example | |
7d15d35d | 283 | |
a9749dab RS |
284 | Here is how you could define a hash table test equivalent to the |
285 | predefined test value @code{equal}. The keys can be any Lisp object, | |
286 | and equal-looking objects are considered the same key. | |
7d15d35d | 287 | |
a9749dab RS |
288 | @example |
289 | (define-hash-table-test 'contents-hash 'equal 'sxhash) | |
7d15d35d | 290 | |
a9749dab RS |
291 | (make-hash-table :test 'contents-hash) |
292 | @end example | |
7d15d35d RS |
293 | |
294 | @node Other Hash | |
295 | @section Other Hash Table Functions | |
296 | ||
297 | Here are some other functions for working with hash tables. | |
298 | ||
7d15d35d RS |
299 | @defun hash-table-p table |
300 | This returns non-@code{nil} if @var{table} is a hash table object. | |
301 | @end defun | |
302 | ||
7d15d35d RS |
303 | @defun copy-hash-table table |
304 | This function creates and returns a copy of @var{table}. Only the table | |
305 | itself is copied---the keys and values are shared. | |
306 | @end defun | |
307 | ||
7d15d35d RS |
308 | @defun hash-table-count table |
309 | This function returns the actual number of entries in @var{table}. | |
310 | @end defun | |
311 | ||
711331aa | 312 | @defun hash-table-test table |
a40d4712 PR |
313 | This returns the @var{test} value that was given when @var{table} was |
314 | created, to specify how to hash and compare keys. See | |
7d15d35d RS |
315 | @code{make-hash-table} (@pxref{Creating Hash}). |
316 | @end defun | |
317 | ||
7d15d35d RS |
318 | @defun hash-table-weakness table |
319 | This function returns the @var{weak} value that was specified for hash | |
320 | table @var{table}. | |
321 | @end defun | |
322 | ||
7d15d35d RS |
323 | @defun hash-table-rehash-size table |
324 | This returns the rehash size of @var{table}. | |
325 | @end defun | |
326 | ||
7d15d35d RS |
327 | @defun hash-table-rehash-threshold table |
328 | This returns the rehash threshold of @var{table}. | |
329 | @end defun | |
330 | ||
711331aa | 331 | @defun hash-table-size table |
7d15d35d RS |
332 | This returns the current nominal size of @var{table}. |
333 | @end defun | |
ab5796a9 MB |
334 | |
335 | @ignore | |
336 | arch-tag: 3b5107f9-d2f0-47d5-ad61-3498496bea0e | |
337 | @end ignore |