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