Mercurial > hg > xemacs-beta

comparison man/lispref/hash-tables.texi @ 380:8626e4521993 r21-2-5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-5
author cvs
date Mon, 13 Aug 2007 11:07:10 +0200
parents 376386a54a3c
children 74fd4e045ea6
comparison
equal deleted inserted replaced
379:76b7d63099ad 380:8626e4521993
5 @setfilename ../../info/hash-tables.info 5 @setfilename ../../info/hash-tables.info
6 @node Hash Tables, Range Tables, Display, top 6 @node Hash Tables, Range Tables, Display, top
7 @chapter Hash Tables 7 @chapter Hash Tables
8 @cindex hash table 8 @cindex hash table
9 9
10 @defun hashtablep object 10 @defun hash-table-p object
11 This function returns non-@code{nil} if @var{object} is a hash table. 11 This function returns @code{t} if @var{object} is a hash table, else @code{nil}.
12 @end defun 12 @end defun
13 13
14 @menu 14 @menu
15 * Introduction to Hash Tables:: Hash tables are fast data structures for 15 * Introduction to Hash Tables:: Hash tables are fast data structures for
16 implementing simple tables (i.e. finite 16 implementing simple tables (i.e. finite
21 @end menu 21 @end menu
22 22
23 @node Introduction to Hash Tables 23 @node Introduction to Hash Tables
24 @section Introduction to Hash Tables 24 @section Introduction to Hash Tables
25 25
26 A hash table is a data structure that provides mappings from 26 A @dfn{hash table} is a data structure that provides mappings from
27 arbitrary Lisp objects (called @dfn{keys}) to other arbitrary Lisp 27 arbitrary Lisp objects called @dfn{keys} to other arbitrary Lisp objects
28 objects (called @dfn{values}). There are many ways other than 28 called @dfn{values}. A key/value pair is sometimes called an
29 hash tables of implementing the same sort of mapping, e.g. 29 @dfn{entry} in the hash table. There are many ways other than hash
30 association lists (@pxref{Association Lists}) and property lists 30 tables of implementing the same sort of mapping, e.g. association lists
31 (@pxref{Property Lists}), but hash tables provide much faster lookup. 31 (@pxref{Association Lists}) and property lists (@pxref{Property Lists}),
32 32 but hash tables provide much faster lookup when there are many entries
33 When you create a hash table, you specify a size, which indicates the 33 in the mapping. Hash tables are an implementation of the abstract data
34 expected number of elements that the table will hold. You are not 34 type @dfn{dictionary}, also known as @dfn{associative array}.
35 bound by this size, however; hash tables automatically resize themselves 35
36 if the number of elements becomes too large. 36 Internally, hash tables are hashed using the @dfn{linear probing} hash
37 37 table implementation method. This method hashes each key to a
38 (Internally, hash tables are hashed using a modification of the 38 particular spot in the hash table, and then scans forward sequentially
39 @dfn{linear probing} hash table method. This method hashes each 39 until a blank entry is found. To look up a key, hash to the appropriate
40 key to a particular spot in the hash table, and then scans forward 40 spot, then search forward for the key until either a key is found or a
41 sequentially until a blank entry is found. To look up a key, hash 41 blank entry stops the search. This method is used in preference to
42 to the appropriate spot, then search forward for the key until either 42 double hashing because of changes in recent hardware. The penalty for
43 a key is found or a blank entry stops the search. The modification 43 non-sequential access to memory has been increasing, and this
44 actually used is called @dfn{double hashing} and involves moving forward 44 compensates for the problem of clustering that linear probing entails.
45 by a fixed increment, whose value is computed from the original hash 45
46 value, rather than always moving forward by one. This eliminates 46 When hash tables are created, the user may (but is not required to)
47 problems with clustering that can arise from the simple linear probing 47 specify initial properties that influence performance.
48 method. For more information, see @cite{Algorithms} (second edition) 48
49 by Robert Sedgewick, pp. 236-241.) 49 Use the @code{:size} parameter to specify the number of entries that are
50 50 likely to be stored in the hash table, to avoid the overhead of resizing
51 @defun make-hashtable size &optional test-fun 51 the table. But if the pre-allocated space for the entries is never
52 This function makes a hash table of initial size @var{size}. Comparison 52 used, it is simply wasted and makes XEmacs slower. Excess unused hash
53 between keys is normally done with @code{eql}; i.e. two keys must be the 53 table entries exact a small continuous performance penalty, since they
54 same object to be considered equivalent. However, you can explicitly 54 must be scanned at every garbage collection. If the number of entries
55 specify the comparison function using @var{test-fun}, which must be 55 in the hash table is unknown, simply avoid using the @code{:size}
56 one of @code{eq}, @code{eql}, or @code{equal}. 56 keyword.
57 57
58 Note that currently, @code{eq} and @code{eql} are the same. This will 58 Use the @code{:rehash-size} and @code{:rehash-threshold} keywords to
59 change when bignums are implemented. 59 adjust the algorithm for deciding when to rehash the hash table. For
60 @end defun 60 temporary hash tables that are going to be very heavily used, use a
61 61 small rehash threshold, for example, 0.4 and a large rehash size, for
62 @defun copy-hashtable old-table 62 example 2.0. For permanent hash tables that will be infrequently used,
63 This function makes a new hash table which contains the same keys and 63 specify a large rehash threshold, for example 0.8.
64 values as the given table. The keys and values will not themselves be 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{:size} @code{:test} @code{:type} @code{:rehash-size} @code{:rehash-threshold}
76 This function returns a new empty hash table object.
77
78 Keyword @code{:size} specifies the number of keys likely to be inserted.
79 This number of entries can be inserted without enlarging the hash table.
80
81 Keyword @code{:test} can be @code{eq}, @code{eql} (default) or @code{equal}.
82 Comparison between keys is done using this function.
83 If speed is important, consider using @code{eq}.
84 When storing strings in the hash table, you will likely need to use @code{equal}.
85
86 Keyword @code{:type} can be @code{non-weak} (default), @code{weak},
87 @code{key-weak} or @code{value-weak}.
88
89 A weak hash table is one whose pointers do not count as GC referents:
90 for any key-value pair in the hash table, if the only remaining pointer
91 to either the key or the value is in a weak hash table, then the pair
92 will be removed from the hash table, and the key and value collected.
93 A non-weak hash table (or any other pointer) would prevent the object
94 from being collected.
95
96 A key-weak hash table is similar to a fully-weak hash table except that
97 a key-value pair will be removed only if the key remains unmarked
98 outside of weak hash tables. The pair will remain in the hash table if
99 the key is pointed to by something other than a weak hash table, even
100 if the value is not.
101
102 A value-weak hash table is similar to a fully-weak hash table except
103 that a key-value pair will be removed only if the value remains
104 unmarked outside of weak hash tables. The pair will remain in the
105 hash table if the value is pointed to by something other than a weak
106 hash table, even if the key is not.
107
108 Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies
109 the factor by which to increase the size of the hash table when enlarging.
110
111 Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0,
112 and specifies the load factor of the hash table which triggers enlarging.
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
65 copied. 118 copied.
66 @end defun 119 @end defun
67 120
68 @defun hashtable-fullness table 121 @defun hash-table-count hash-table
69 This function returns number of entries in @var{table}. 122 This function returns the number of entries in @var{hash-table}.
123 @end defun
124
125 @defun hash-table-size hash-table
126 This function returns the current number of slots in @var{hash-table},
127 whether occupied or not.
128 @end defun
129
130 @defun hash-table-type hash-table
131 This function returns the type of @var{hash-table}.
132 This can be one of @code{non-weak}, @code{weak}, @code{key-weak} or
133 @code{value-weak}.
134 @end defun
135
136 @defun hash-table-test hash-table
137 This function returns the test function of @var{hash-table}.
138 This can be one of @code{eq}, @code{eql} or @code{equal}.
139 @end defun
140
141 @defun hash-table-rehash-size hash-table
142 This function returns the current rehash size of @var{hash-table}.
143 This is a float greater than 1.0; the factor by which @var{hash-table}
144 is enlarged when the rehash threshold is exceeded.
145 @end defun
146
147 @defun hash-table-rehash-threshold hash-table
148 This function returns the current rehash threshold of @var{hash-table}.
149 This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of
150 @var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing.
70 @end defun 151 @end defun
71 152
72 @node Working With Hash Tables 153 @node Working With Hash Tables
73 @section Working With Hash Tables 154 @section Working With Hash Tables
74 155
75 @defun puthash key val table 156 @defun puthash key value hash-table
76 This function hashes @var{key} to @var{val} in @var{table}. 157 This function hashes @var{key} to @var{value} in @var{hash-table}.
77 @end defun 158 @end defun
78 159
79 @defun gethash key table &optional default 160 @defun gethash key hash-table &optional default
80 This function finds the hash value for @var{key} in @var{table}. If 161 This function finds the hash value for @var{key} in @var{hash-table}.
81 there is no corresponding value, @var{default} is returned (defaults to 162 If there is no entry for @var{key} in @var{hash-table}, @var{default} is
82 @code{nil}). 163 returned (which in turn defaults to @code{nil}).
83 @end defun 164 @end defun
84 165
85 @defun remhash key table 166 @defun remhash key hash-table
86 This function removes the hash value for @var{key} in @var{table}. 167 This function removes the entry for @var{key} from @var{hash-table}.
87 @end defun 168 Does nothing if there is no entry for @var{key} in @var{hash-table}.
88 169 @end defun
89 @defun clrhash table 170
90 This function flushes @var{table}. Afterwards, the hash table will 171 @defun clrhash hash-table
91 contain no entries. 172 This function removes all entries from @var{hash-table}, leaving it empty.
92 @end defun 173 @end defun
93 174
94 @defun maphash function table 175 @defun maphash function hash-table
95 This function maps @var{function} over entries in @var{table}, calling 176 This function maps @var{function} over entries in @var{hash-table},
96 it with two args, each key and value in the table. 177 calling it with two args, each key and value in the hash table.
178
179 @var{function} may not modify @var{hash-table}, with the one exception
180 that @var{function} may remhash or puthash the entry currently being
181 processed by @var{function}.
97 @end defun 182 @end defun
98 183
99 @node Weak Hash Tables 184 @node Weak Hash Tables
100 @section Weak Hash Tables 185 @section Weak Hash Tables
101 @cindex hash table, weak 186 @cindex hash table, weak
133 of the table, regardless of how the key is referenced. 218 of the table, regardless of how the key is referenced.
134 @end table 219 @end table
135 220
136 Also see @ref{Weak Lists}. 221 Also see @ref{Weak Lists}.
137 222
138 @defun make-weak-hashtable size &optional test-fun 223 Weak hash tables are created by specifying the @code{:type} keyword to
139 This function makes a fully weak hash table of initial size @var{size}. 224 @code{make-hash-table}.
140 @var{test-fun} is as in @code{make-hashtable}.
141 @end defun
142
143 @defun make-key-weak-hashtable size &optional test-fun
144 This function makes a key-weak hash table of initial size @var{size}.
145 @var{test-fun} is as in @code{make-hashtable}.
146 @end defun
147
148 @defun make-value-weak-hashtable size &optional test-fun
149 This function makes a value-weak hash table of initial size @var{size}.
150 @var{test-fun} is as in @code{make-hashtable}.
151 @end defun