Mercurial > emacs
annotate lispref/hash.texi @ 56026:bb6720f21c54
Revision: miles@gnu.org--gnu-2004/emacs--cvs-trunk--0--patch-396
Tweak arch tagging to make build/install-in-place less annoying
Previously, autoconf-created Makefiles and the like would contain
duplicate taglines (unfortunately, autoconf doesn't seem to have a
`strip in generated file' comment mechanism) leading to conflicts, and
installing in place would create unknown directories and copies of
source directories (leading to conflicts with the source directories).
This changeset makes all autoconf-processed files use explicit id-tags
and adds .arch-inventory entries to ignore installation directories.
author | Miles Bader <miles@gnu.org> |
---|---|
date | Fri, 11 Jun 2004 02:39:51 +0000 |
parents | 41fd82e27495 |
children | c9aa4127a482 |
rev | line source |
---|---|
25634 | 1 @c -*-texinfo-*- |
2 @c This is part of the GNU Emacs Lisp Reference Manual. | |
51585
b29f076f791a
(Creating Hash): Fix description of :weakness.
Andreas Schwab <schwab@suse.de>
parents:
49600
diff
changeset
|
3 @c Copyright (C) 1999, 2003 Free Software Foundation, Inc. |
25634 | 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 | |
53025
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
79 Keys which are numbers are ``the same'' if they are @code{equal}, that |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
80 is, if they are equal in value and either both are integers or both |
53037
9958d8677feb
*** empty log message ***
Luc Teirlinck <teirllm@auburn.edu>
parents:
53025
diff
changeset
|
81 are floating point numbers; otherwise, two distinct objects are never |
9958d8677feb
*** empty log message ***
Luc Teirlinck <teirllm@auburn.edu>
parents:
53025
diff
changeset
|
82 ``the same''. |
25634 | 83 |
84 @item eq | |
85 Any two distinct Lisp objects are ``different'' as keys. | |
86 | |
87 @item equal | |
88 Two Lisp objects are ``the same'', as keys, if they are equal | |
89 according to @code{equal}. | |
90 @end table | |
91 | |
92 You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to | |
93 define additional possibilities for @var{test}. | |
94 | |
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. | |
98 | |
99 The value, @var{weak}, must be one of @code{nil}, @code{key}, | |
30524 | 100 @code{value}, @code{key-or-value}, @code{key-and-value}, or @code{t} |
54263
41fd82e27495
(Creating Hash): Correct the meaning of t for WEAK in make-hash-table.
Richard M. Stallman <rms@gnu.org>
parents:
54031
diff
changeset
|
101 which is an alias for @code{key-and-value}. If @var{weak} is @code{key} |
30524 | 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 | |
105 hash table. | |
25634 | 106 |
30524 | 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 | |
25634 | 110 corresponding association is removed from the hash table. |
111 | |
54031
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
112 If @var{weak} is @code{key-and-value} or @code{t}, both the key and |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
113 the value must be live in order to preserve the association. Thus, |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
114 the hash table does not protect either keys or values from garbage |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
115 collection; if either one is collected as garbage, that removes the |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
116 association. |
38786 | 117 |
54031
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
118 If @var{weak} is @code{key-or-value}, either the key or |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
119 the value can preserve the association. Thus, associations are |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
120 removed from the hash table when both their key and value would be |
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
121 collected as garbage (if not for references from weak hash tables). |
30524 | 122 |
25634 | 123 The default for @var{weak} is @code{nil}, so that all keys and values |
54031
fcad69b9ff7b
(Creating Hash): Correct and clarify doc of WEAK values.
Richard M. Stallman <rms@gnu.org>
parents:
53480
diff
changeset
|
124 referenced in the hash table are preserved from garbage collection. |
25634 | 125 |
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 | |
26182 | 129 little more efficient by specifying it this way. If you specify too |
25634 | 130 small a size, the hash table will grow automatically when necessary, but |
26303 | 131 doing that takes some extra time. |
25634 | 132 |
133 The default size is 65. | |
134 | |
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. | |
139 | |
25875 | 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 | |
144 number. | |
25634 | 145 |
146 The default value is 1.5. | |
147 | |
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. | |
154 @end table | |
155 @end defun | |
156 | |
157 @tindex makehash | |
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 | |
161 of key lookup. | |
162 | |
53025
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
163 This function is obsolete. Use @code{make-hash-table} instead. |
25634 | 164 @end defun |
165 | |
166 @node Hash Access | |
167 @section Hash Table Access | |
168 | |
169 This section describes the functions for accessing and storing | |
170 associations in a hash table. | |
171 | |
172 @tindex gethash | |
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}. | |
177 @end defun | |
178 | |
179 @tindex puthash | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
38786
diff
changeset
|
180 @defun puthash key value table |
25634 | 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. | |
184 @end defun | |
185 | |
186 @tindex remhash | |
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. | |
53025
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
191 |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
192 @b{Common Lisp note:} In Common Lisp, @code{remhash} returns |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
193 non-@code{nil} if it actually removed an association and @code{nil} |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
194 otherwise. In Emacs Lisp, @code{remhash} always returns @code{nil}. |
25634 | 195 @end defun |
196 | |
197 @tindex clrhash | |
198 @defun clrhash table | |
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 | |
201 table. | |
53025
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
202 |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
203 @b{Common Lisp note:} In Common Lisp, @code{clrhash} returns the empty |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
204 @var{table}. In Emacs Lisp, it returns @code{nil}. |
25634 | 205 @end defun |
206 | |
207 @tindex maphash | |
53480
879f6aa2d2c7
(Hash Access): Add anchor.
Luc Teirlinck <teirllm@auburn.edu>
parents:
53037
diff
changeset
|
208 @anchor{Definition of maphash} |
25634 | 209 @defun maphash function table |
210 This function calls @var{function} once for each of the associations in | |
211 @var{table}. The function @var{function} should accept two | |
212 arguments---a @var{key} listed in @var{table}, and its associated | |
213 @var{value}. | |
214 @end defun | |
215 | |
216 @node Defining Hash | |
217 @section Defining Hash Comparisons | |
218 @cindex hash code | |
219 | |
220 You can define new methods of key lookup by means of | |
221 @code{define-hash-table-test}. In order to use this feature, you need | |
222 to understand how hash tables work, and what a @dfn{hash code} means. | |
223 | |
224 You can think of a hash table conceptually as a large array of many | |
225 slots, each capable of holding one association. To look up a key, | |
226 @code{gethash} first computes an integer, the hash code, from the key. | |
227 It reduces this integer modulo the length of the array, to produce an | |
228 index in the array. Then it looks in that slot, and if necessary in | |
229 other nearby slots, to see if it has found the key being sought. | |
230 | |
231 Thus, to define a new method of key lookup, you need to specify both a | |
232 function to compute the hash code from a key, and a function to compare | |
233 two keys directly. | |
234 | |
235 @tindex define-hash-table-test | |
236 @defun define-hash-table-test name test-fn hash-fn | |
237 This function defines a new hash table test, named @var{name}. | |
238 | |
239 After defining @var{name} in this way, you can use it as the @var{test} | |
240 argument in @code{make-hash-table}. When you do that, the hash table | |
241 will use @var{test-fn} to compare key values, and @var{hash-fn} to compute | |
242 a ``hash code'' from a key value. | |
243 | |
244 The function @var{test-fn} should accept two arguments, two keys, and | |
245 return non-@code{nil} if they are considered ``the same.'' | |
246 | |
247 The function @var{hash-fn} should accept one argument, a key, and return | |
248 an integer that is the ``hash code'' of that key. For good results, the | |
249 function should use the whole range of integer values for hash codes, | |
250 including negative integers. | |
251 | |
252 The specified functions are stored in the property list of @var{name} | |
253 under the property @code{hash-table-test}; the property value's form is | |
254 @code{(@var{test-fn} @var{hash-fn})}. | |
255 @end defun | |
256 | |
257 @tindex sxhash | |
258 @defun sxhash obj | |
259 This function returns a hash code for Lisp object @var{obj}. | |
260 This is an integer which reflects the contents of @var{obj} | |
261 and the other Lisp objects it points to. | |
262 | |
263 If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash | |
264 @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer. | |
265 | |
266 If the two objects are not equal, the values returned by @code{sxhash} | |
53025
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
267 are usually different, but not always; once in a rare while, by luck, |
53be3d7fa5da
(Creating Hash): Clarify description of `eql'. `makehash' is obsolete.
Luc Teirlinck <teirllm@auburn.edu>
parents:
52401
diff
changeset
|
268 you will encounter two distinct-looking objects that give the same |
25634 | 269 result from @code{sxhash}. |
270 @end defun | |
271 | |
38786 | 272 This example creates a hash table whose keys are strings that are |
273 compared case-insensitively. | |
274 | |
275 @example | |
276 (defun case-fold-string= (a b) | |
277 (compare-strings a nil nil b nil nil t)) | |
278 | |
279 (defun case-fold-string-hash (a) | |
280 (sxhash (upcase a))) | |
281 | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
38786
diff
changeset
|
282 (define-hash-table-test 'case-fold 'case-fold-string= |
38786 | 283 'case-fold-string-hash)) |
284 | |
285 (make-hash-table :test 'case-fold) | |
286 @end example | |
287 | |
288 Here is how you could define a hash table test equivalent to the | |
289 predefined test value @code{equal}. The keys can be any Lisp object, | |
290 and equal-looking objects are considered the same key. | |
291 | |
292 @example | |
293 (define-hash-table-test 'contents-hash 'equal 'sxhash) | |
294 | |
295 (make-hash-table :test 'contents-hash) | |
296 @end example | |
297 | |
25634 | 298 @node Other Hash |
299 @section Other Hash Table Functions | |
300 | |
301 Here are some other functions for working with hash tables. | |
302 | |
303 @tindex hash-table-p | |
304 @defun hash-table-p table | |
305 This returns non-@code{nil} if @var{table} is a hash table object. | |
306 @end defun | |
307 | |
308 @tindex copy-hash-table | |
309 @defun copy-hash-table table | |
310 This function creates and returns a copy of @var{table}. Only the table | |
311 itself is copied---the keys and values are shared. | |
312 @end defun | |
313 | |
314 @tindex hash-table-count | |
315 @defun hash-table-count table | |
316 This function returns the actual number of entries in @var{table}. | |
317 @end defun | |
318 | |
26182 | 319 @tindex hash-table-test |
320 @defun hash-table-test table | |
25875 | 321 This returns the @var{test} value that was given when @var{table} was |
322 created, to specify how to hash and compare keys. See | |
25634 | 323 @code{make-hash-table} (@pxref{Creating Hash}). |
324 @end defun | |
325 | |
326 @tindex hash-table-weakness | |
327 @defun hash-table-weakness table | |
328 This function returns the @var{weak} value that was specified for hash | |
329 table @var{table}. | |
330 @end defun | |
331 | |
332 @tindex hash-table-rehash-size | |
333 @defun hash-table-rehash-size table | |
334 This returns the rehash size of @var{table}. | |
335 @end defun | |
336 | |
337 @tindex hash-table-rehash-threshold | |
338 @defun hash-table-rehash-threshold table | |
339 This returns the rehash threshold of @var{table}. | |
340 @end defun | |
341 | |
26182 | 342 @tindex hash-table-size |
343 @defun hash-table-size table | |
25634 | 344 This returns the current nominal size of @var{table}. |
345 @end defun | |
52401 | 346 |
347 @ignore | |
348 arch-tag: 3b5107f9-d2f0-47d5-ad61-3498496bea0e | |
349 @end ignore |