Commit | Line | Data |
---|---|---|
7d15d35d RS |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Emacs Lisp Reference Manual. | |
3 | @c Copyright (C) 1999 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 | |
7 | @chapter Hash Tables | |
8 | @cindex hash tables | |
9 | ||
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: | |
13 | ||
14 | @itemize @bullet | |
15 | @item | |
16 | Lookup in a hash table is extremely fast---in fact, the time required | |
17 | is essentially @emph{independent} of how many elements are stored | |
18 | in the table. | |
19 | ||
20 | @item | |
21 | The correspondences in a hash table are in no particular order. | |
22 | ||
23 | @item | |
24 | There is no way to share structure between two hash tables, | |
25 | the way two alists can share a common tail. | |
26 | @end itemize | |
27 | ||
28 | Emacs Lisp (starting with Emacs 21) provides a general-purpose hash | |
29 | table data type, along with a series of functions for operating on them. | |
30 | Hash tables have no read syntax, and print in hash notation, like this: | |
31 | ||
32 | @example | |
33 | (make-hash-table) | |
34 | @result{} #<hash-table 'eql nil 0/65 0x83af980> | |
35 | @end example | |
36 | ||
37 | Obarrays are also a kind of hash table, but they are a different type | |
38 | of object and are used only for recording interned symbols | |
39 | (@pxref{Creating Symbols}). | |
40 | ||
41 | @menu | |
42 | * Creating Hash:: | |
43 | * Hash Access:: | |
44 | * Defining Hash:: | |
45 | * Other Hash:: | |
46 | @end menu | |
47 | ||
48 | @node Creating Hash | |
49 | @section Creating Hash Tables | |
50 | ||
51 | The principal function for creating a hash table is | |
52 | @code{make-hash-table}. | |
53 | ||
54 | @tindex make-hash-table | |
55 | @defun make-hash-table &rest keyword-args | |
56 | This function creates a new hash table according to the specified | |
57 | arguments. The arguments should consist of alternating keywords | |
58 | (particular symbols recognized specially) and values corresponding to | |
59 | them. | |
60 | ||
61 | Several keywords make sense in @code{make-hash-table}, but the only two | |
62 | that you really need to know about are @code{:test} and @code{:weak}. | |
63 | ||
64 | @table @code | |
65 | @item :test @var{test} | |
66 | This specifies the method of key lookup for this hash table. The | |
67 | default is @code{eql}; @code{eq} and @code{equal} are other | |
68 | alternatives: | |
69 | ||
70 | @table @code | |
71 | @item eql | |
72 | Keys which are numbers are ``the same'' if they are equal in value; | |
73 | otherwise, two distinct objects are never ``the same''. | |
74 | ||
75 | @item eq | |
76 | Any two distinct Lisp objects are ``different'' as keys. | |
77 | ||
78 | @item equal | |
79 | Two Lisp objects are ``the same'', as keys, if they are equal | |
80 | according to @code{equal}. | |
81 | @end table | |
82 | ||
83 | You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to | |
84 | define additional possibilities for @var{test}. | |
85 | ||
86 | @item :weakness @var{weak} | |
87 | The weakness of a hash table specifies whether the presence of a key or | |
88 | value in the hash table preserves it from garbage collection. | |
89 | ||
90 | The value, @var{weak}, must be one of @code{nil}, @code{key}, | |
91 | @code{value} or @code{t}. If @var{weak} is @code{key} or @code{t}, then | |
92 | the hash table does not prevent its keys from being collected as garbage | |
93 | (if they are not referenced anywhere else); if a particular key does get | |
94 | collected, the corresponding association is removed from the hash table. | |
95 | ||
96 | Likewise, if @var{weak} is @code{value} or @code{t}, then the hash table | |
97 | does not prevent values from being collected as garbage (if they are not | |
98 | referenced anywhere else); if a particular value does get collected, the | |
99 | corresponding association is removed from the hash table. | |
100 | ||
101 | The default for @var{weak} is @code{nil}, so that all keys and values | |
102 | referenced in the hash table are preserved from garbage collection. | |
103 | ||
104 | @item :size @var{size} | |
105 | This specifies a hint for how many associations you plan to store in the | |
106 | hash table. If you know the approximate number, you can make things a | |
107 | little more efficient by specifying it this way. If you specify to | |
108 | small a size, the hash table will grow automatically when necessary, but | |
109 | doing that takes some extra time, | |
110 | ||
111 | The default size is 65. | |
112 | ||
113 | @item :rehash-size @var{rehash-size} | |
114 | When you add an association to a hash table and the table is ``full,'' | |
115 | it grows automatically. This value specifies how to make the hash table | |
116 | larger, at that time. | |
117 | ||
118 | If @var{rehash-size} is an integer, it had better be positive, and the | |
119 | hash table grows by adding that much to the size. If @var{rehash-size} | |
120 | is a floating point number, it had better be greater than 1, and the | |
121 | hash table grows by multiplying the old size by that number. | |
122 | ||
123 | The default value is 1.5. | |
124 | ||
125 | @item :rehash-threshold @var{threshold} | |
126 | This specifies the criterion for when the hash table is ``full.'' The | |
127 | value, @var{threshold}, should be a positive floating point number, no | |
128 | greater than 1. The hash table is ``full'' whenever the actual number of | |
129 | entries exceeds this fraction of the nominal size. The default for | |
130 | @var{threshold} is 0.8. | |
131 | @end table | |
132 | @end defun | |
133 | ||
134 | @tindex makehash | |
135 | @defun makehash &optional test | |
136 | This is equivalent to @code{make-hash-table}, but with a different style | |
137 | argument list. The argument @var{test} specifies the method | |
138 | of key lookup. | |
139 | ||
140 | If you want to specify other parameters, you should use | |
141 | @code{make-hash-table}. | |
142 | @end defun | |
143 | ||
144 | @node Hash Access | |
145 | @section Hash Table Access | |
146 | ||
147 | This section describes the functions for accessing and storing | |
148 | associations in a hash table. | |
149 | ||
150 | @tindex gethash | |
151 | @defun gethash key table &optional default | |
152 | This function looks up @var{key} in @var{table}, and returns its | |
153 | associated @var{value}---or @var{default}, if @var{key} has no | |
154 | association in @var{table}. | |
155 | @end defun | |
156 | ||
157 | @tindex puthash | |
158 | @defun puthash key value table | |
159 | This function enters an association for @var{key} in @var{table}, with | |
160 | value @var{value}. If @var{key} already has an association in | |
161 | @var{table}, @var{value} replaces the old associated value. | |
162 | @end defun | |
163 | ||
164 | @tindex remhash | |
165 | @defun remhash key table | |
166 | This function removes the association for @var{key} from @var{table}, if | |
167 | there is one. If @var{key} has no association, @code{remhash} does | |
168 | nothing. | |
169 | @end defun | |
170 | ||
171 | @tindex clrhash | |
172 | @defun clrhash table | |
173 | This function removes all the associations from hash table @var{table}, | |
174 | so that it becomes empty. This is also called @dfn{clearing} the hash | |
175 | table. | |
176 | @end defun | |
177 | ||
178 | @tindex maphash | |
179 | @defun maphash function table | |
180 | This function calls @var{function} once for each of the associations in | |
181 | @var{table}. The function @var{function} should accept two | |
182 | arguments---a @var{key} listed in @var{table}, and its associated | |
183 | @var{value}. | |
184 | @end defun | |
185 | ||
186 | @node Defining Hash | |
187 | @section Defining Hash Comparisons | |
188 | @cindex hash code | |
189 | ||
190 | You can define new methods of key lookup by means of | |
191 | @code{define-hash-table-test}. In order to use this feature, you need | |
192 | to understand how hash tables work, and what a @dfn{hash code} means. | |
193 | ||
194 | You can think of a hash table conceptually as a large array of many | |
195 | slots, each capable of holding one association. To look up a key, | |
196 | @code{gethash} first computes an integer, the hash code, from the key. | |
197 | It reduces this integer modulo the length of the array, to produce an | |
198 | index in the array. Then it looks in that slot, and if necessary in | |
199 | other nearby slots, to see if it has found the key being sought. | |
200 | ||
201 | Thus, to define a new method of key lookup, you need to specify both a | |
202 | function to compute the hash code from a key, and a function to compare | |
203 | two keys directly. | |
204 | ||
205 | @tindex define-hash-table-test | |
206 | @defun define-hash-table-test name test-fn hash-fn | |
207 | This function defines a new hash table test, named @var{name}. | |
208 | ||
209 | After defining @var{name} in this way, you can use it as the @var{test} | |
210 | argument in @code{make-hash-table}. When you do that, the hash table | |
211 | will use @var{test-fn} to compare key values, and @var{hash-fn} to compute | |
212 | a ``hash code'' from a key value. | |
213 | ||
214 | The function @var{test-fn} should accept two arguments, two keys, and | |
215 | return non-@code{nil} if they are considered ``the same.'' | |
216 | ||
217 | The function @var{hash-fn} should accept one argument, a key, and return | |
218 | an integer that is the ``hash code'' of that key. For good results, the | |
219 | function should use the whole range of integer values for hash codes, | |
220 | including negative integers. | |
221 | ||
222 | The specified functions are stored in the property list of @var{name} | |
223 | under the property @code{hash-table-test}; the property value's form is | |
224 | @code{(@var{test-fn} @var{hash-fn})}. | |
225 | ||
226 | This example creates a hash table whose keys are strings that are | |
227 | compared case-insensitively. | |
228 | ||
229 | @example | |
230 | (defun case-fold-string= (a b) | |
231 | (compare-strings a nil nil b nil nil t)) | |
232 | ||
233 | (defun case-fold-string-hash (a) | |
234 | (sxhash (upcase a))) | |
235 | ||
236 | (define-hash-table-test 'case-fold 'case-fold-string= | |
237 | 'case-fold-string-hash)) | |
238 | ||
239 | (make-hash-table :test 'case-fold) | |
240 | @end example | |
241 | @end defun | |
242 | ||
243 | @tindex sxhash | |
244 | @defun sxhash obj | |
245 | This function returns a hash code for Lisp object @var{obj}. | |
246 | This is an integer which reflects the contents of @var{obj} | |
247 | and the other Lisp objects it points to. | |
248 | ||
249 | If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash | |
250 | @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer. | |
251 | ||
252 | If the two objects are not equal, the values returned by @code{sxhash} | |
253 | are usually different, but not always; but once in a rare while, by | |
254 | luck, you will encounter two distinct-looking objects that give the same | |
255 | result from @code{sxhash}. | |
256 | @end defun | |
257 | ||
258 | @node Other Hash | |
259 | @section Other Hash Table Functions | |
260 | ||
261 | Here are some other functions for working with hash tables. | |
262 | ||
263 | @tindex hash-table-p | |
264 | @defun hash-table-p table | |
265 | This returns non-@code{nil} if @var{table} is a hash table object. | |
266 | @end defun | |
267 | ||
268 | @tindex copy-hash-table | |
269 | @defun copy-hash-table table | |
270 | This function creates and returns a copy of @var{table}. Only the table | |
271 | itself is copied---the keys and values are shared. | |
272 | @end defun | |
273 | ||
274 | @tindex hash-table-count | |
275 | @defun hash-table-count table | |
276 | This function returns the actual number of entries in @var{table}. | |
277 | @end defun | |
278 | ||
279 | @tindex hash-table-rehash-test | |
280 | @defun hash-table-rehash-test table | |
281 | This returns the test @var{table} uses to hash and compare keys---see | |
282 | @code{make-hash-table} (@pxref{Creating Hash}). | |
283 | @end defun | |
284 | ||
285 | @tindex hash-table-weakness | |
286 | @defun hash-table-weakness table | |
287 | This function returns the @var{weak} value that was specified for hash | |
288 | table @var{table}. | |
289 | @end defun | |
290 | ||
291 | @tindex hash-table-rehash-size | |
292 | @defun hash-table-rehash-size table | |
293 | This returns the rehash size of @var{table}. | |
294 | @end defun | |
295 | ||
296 | @tindex hash-table-rehash-threshold | |
297 | @defun hash-table-rehash-threshold table | |
298 | This returns the rehash threshold of @var{table}. | |
299 | @end defun | |
300 | ||
301 | @tindex hash-table-rehash-size | |
302 | @defun hash-table-rehash-size table | |
303 | This returns the current nominal size of @var{table}. | |
304 | @end defun |