Mercurial > hg > xemacs-beta

comparison man/lispref/hash-tables.texi @ 428:3ecd8885ac67 r21-2-22

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-22
author cvs
date Mon, 13 Aug 2007 11:28:15 +0200
parents
children abe6d1db359e
comparison
equal deleted inserted replaced
427:0a0253eac470 428:3ecd8885ac67
1 @c -*-texinfo-*-
2 @c This is part of the XEmacs Lisp Reference Manual.
3 @c Copyright (C) 1996 Ben Wing.
4 @c See the file lispref.texi for copying conditions.
5 @setfilename ../../info/hash-tables.info
6 @node Hash Tables, Range Tables, Display, top
7 @chapter Hash Tables
8 @cindex hash table
9
10 @defun hash-table-p object
11 This function returns @code{t} if @var{object} is a hash table, else @code{nil}.
12 @end defun
13
14 @menu
15 * Introduction to Hash Tables:: Hash tables are fast data structures for
16 implementing simple tables (i.e. finite
17 mappings from keys to values).
18 * Working With Hash Tables:: Hash table functions.
19 * Weak Hash Tables:: Hash tables with special garbage-collection
20 behavior.
21 @end menu
22
23 @node Introduction to Hash Tables
24 @section Introduction to Hash Tables
25
26 A @dfn{hash table} is a data structure that provides mappings from
27 arbitrary Lisp objects called @dfn{keys} to other arbitrary Lisp objects
28 called @dfn{values}. A key/value pair is sometimes called an
29 @dfn{entry} in the hash table. There are many ways other than hash
30 tables of implementing the same sort of mapping, e.g. association lists
31 (@pxref{Association Lists}) and property lists (@pxref{Property Lists}),
32 but hash tables provide much faster lookup when there are many entries
33 in the mapping. Hash tables are an implementation of the abstract data
34 type @dfn{dictionary}, also known as @dfn{associative array}.
35
36 Internally, hash tables are hashed using the @dfn{linear probing} hash
37 table implementation method. This method hashes each key to a
38 particular spot in the hash table, and then scans forward sequentially
39 until a blank entry is found. To look up a key, hash to the appropriate
40 spot, then search forward for the key until either a key is found or a
41 blank entry stops the search. This method is used in preference to
42 double hashing because of changes in recent hardware. The penalty for
43 non-sequential access to memory has been increasing, and this
44 compensates for the problem of clustering that linear probing entails.
45
46 When hash tables are created, the user may (but is not required to)
47 specify initial properties that influence performance.
48
49 Use the @code{:size} parameter to specify the number of entries that are
50 likely to be stored in the hash table, to avoid the overhead of resizing
51 the table. But if the pre-allocated space for the entries is never
52 used, it is simply wasted and makes XEmacs slower. Excess unused hash
53 table entries exact a small continuous performance penalty, since they
54 must be scanned at every garbage collection. If the number of entries
55 in the hash table is unknown, simply avoid using the @code{:size}
56 keyword.
57
58 Use the @code{:rehash-size} and @code{:rehash-threshold} keywords to
59 adjust the algorithm for deciding when to rehash the hash table. For
60 temporary hash tables that are going to be very heavily used, use a
61 small rehash threshold, for example, 0.4 and a large rehash size, for
62 example 2.0. For permanent hash tables that will be infrequently used,
63 specify a large rehash threshold, for example 0.8.
64
65 Hash tables can also be created by the lisp reader using structure
66 syntax, for example:
67 @example
68 #s(hash-table size 20 data (foo 1 bar 2))
69 @end example
70
71 The structure syntax accepts the same keywords as @code{make-hash-table}
72 (without the @code{:} character), as well as the additional keyword
73 @code{data}, which specifies the initial hash table contents.
74
75 @defun make-hash-table &key @code{test} @code{size} @code{rehash-size} @code{rehash-threshold} @code{weakness}
76 This function returns a new empty hash table object.
77
78 Keyword @code{:test} can be @code{eq}, @code{eql} (default) or @code{equal}.
79 Comparison between keys is done using this function.
80 If speed is important, consider using @code{eq}.
81 When storing strings in the hash table, you will likely need to use @code{equal}.
82
83 Keyword @code{:size} specifies the number of keys likely to be inserted.
84 This number of entries can be inserted without enlarging the hash table.
85
86 Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies
87 the factor by which to increase the size of the hash table when enlarging.
88
89 Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0,
90 and specifies the load factor of the hash table which triggers enlarging.
91
92 Keyword @code{:weakness} can be @code{nil} (default), @code{t},
93 @code{key} or @code{value}.
94
95 A weak hash table is one whose pointers do not count as GC referents:
96 for any key-value pair in the hash table, if the only remaining pointer
97 to either the key or the value is in a weak hash table, then the pair
98 will be removed from the hash table, and the key and value collected.
99 A non-weak hash table (or any other pointer) would prevent the object
100 from being collected.
101
102 A key-weak hash table is similar to a fully-weak hash table except that
103 a key-value pair will be removed only if the key remains unmarked
104 outside of weak hash tables. The pair will remain in the hash table if
105 the key is pointed to by something other than a weak hash table, even
106 if the value is not.
107
108 A value-weak hash table is similar to a fully-weak hash table except
109 that a key-value pair will be removed only if the value remains
110 unmarked outside of weak hash tables. The pair will remain in the
111 hash table if the value is pointed to by something other than a weak
112 hash table, even if the key is not.
113 @end defun
114
115 @defun copy-hash-table hash-table
116 This function returns a new hash table which contains the same keys and
117 values as @var{hash-table}. The keys and values will not themselves be
118 copied.
119 @end defun
120
121 @defun hash-table-count hash-table
122 This function returns the number of entries in @var{hash-table}.
123 @end defun
124
125 @defun hash-table-test hash-table
126 This function returns the test function of @var{hash-table}.
127 This can be one of @code{eq}, @code{eql} or @code{equal}.
128 @end defun
129
130 @defun hash-table-size hash-table
131 This function returns the current number of slots in @var{hash-table},
132 whether occupied or not.
133 @end defun
134
135 @defun hash-table-rehash-size hash-table
136 This function returns the current rehash size of @var{hash-table}.
137 This is a float greater than 1.0; the factor by which @var{hash-table}
138 is enlarged when the rehash threshold is exceeded.
139 @end defun
140
141 @defun hash-table-rehash-threshold hash-table
142 This function returns the current rehash threshold of @var{hash-table}.
143 This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of
144 @var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing.
145 @end defun
146
147 @defun hash-table-weakness hash-table
148 This function returns the weakness of @var{hash-table}.
149 This can be one of @code{nil}, @code{t}, @code{key} or @code{value}.
150 @end defun
151
152 @node Working With Hash Tables
153 @section Working With Hash Tables
154
155 @defun puthash key value hash-table
156 This function hashes @var{key} to @var{value} in @var{hash-table}.
157 @end defun
158
159 @defun gethash key hash-table &optional default
160 This function finds the hash value for @var{key} in @var{hash-table}.
161 If there is no entry for @var{key} in @var{hash-table}, @var{default} is
162 returned (which in turn defaults to @code{nil}).
163 @end defun
164
165 @defun remhash key hash-table
166 This function removes the entry for @var{key} from @var{hash-table}.
167 Does nothing if there is no entry for @var{key} in @var{hash-table}.
168 @end defun
169
170 @defun clrhash hash-table
171 This function removes all entries from @var{hash-table}, leaving it empty.
172 @end defun
173
174 @defun maphash function hash-table
175 This function maps @var{function} over entries in @var{hash-table},
176 calling it with two args, each key and value in the hash table.
177
178 @var{function} may not modify @var{hash-table}, with the one exception
179 that @var{function} may remhash or puthash the entry currently being
180 processed by @var{function}.
181 @end defun
182
183
184 @node Weak Hash Tables
185 @section Weak Hash Tables
186 @cindex hash table, weak
187 @cindex weak hash table
188
189 A @dfn{weak hash table} is a special variety of hash table whose
190 elements do not count as GC referents. For any key-value pair in such a
191 hash table, if either the key or value (or in some cases, if one
192 particular one of the two) has no references to it outside of weak hash
193 tables (and similar structures such as weak lists), the pair will be
194 removed from the table, and the key and value collected. A non-weak
195 hash table (or any other pointer) would prevent the objects from being
196 collected.
197
198 Weak hash tables are useful for keeping track of information in a
199 non-obtrusive way, for example to implement caching. If the cache
200 contains objects such as buffers, markers, image instances, etc. that
201 will eventually disappear and get garbage-collected, using a weak hash
202 table ensures that these objects are collected normally rather than
203 remaining around forever, long past their actual period of use.
204 (Otherwise, you'd have to explicitly map over the hash table every so
205 often and remove unnecessary elements.)
206
207 There are three types of weak hash tables:
208
209 @table @asis
210 @item fully weak hash tables
211 In these hash tables, a pair disappears if either the key or the value
212 is unreferenced outside of the table.
213 @item key-weak hash tables
214 In these hash tables, a pair disappears if the key is unreferenced outside
215 of the table, regardless of how the value is referenced.
216 @item value-weak hash tables
217 In these hash tables, a pair disappears if the value is unreferenced outside
218 of the table, regardless of how the key is referenced.
219 @end table
220
221 Also see @ref{Weak Lists}.
222
223 Weak hash tables are created by specifying the @code{:weakness} keyword to
224 @code{make-hash-table}.