Mercurial > hg > xemacs-beta
annotate man/lispref/hash-tables.texi @ 4888:c27efc9acb5a
merge
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Wed, 27 Jan 2010 00:37:59 -0600 |
| parents | e6dec75ded0e |
| children | 71ee43b8a74d |
| rev | line source |
|---|---|
| 428 | 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 | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
68 #s(hash-table :size 20 :data (foo 1 bar 2)) |
| 428 | 69 @end example |
| 70 | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
71 The structure syntax accepts the same keywords as |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
72 @code{make-hash-table}, as well as the additional keyword @code{data}, |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
73 which specifies the initial hash table contents. Older versions of |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
74 XEmacs required that the keywords not have the initial ``:'' in the |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
75 structure syntax, and this version of XEmacs still supports that syntax, |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
76 but you cannot mix the two styles within one structure. |
| 428 | 77 |
| 78 @defun make-hash-table &key @code{test} @code{size} @code{rehash-size} @code{rehash-threshold} @code{weakness} | |
| 79 This function returns a new empty hash table object. | |
| 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{:size} specifies the number of keys likely to be inserted. | |
| 87 This number of entries can be inserted without enlarging the hash table. | |
| 88 | |
| 89 Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies | |
| 90 the factor by which to increase the size of the hash table when enlarging. | |
| 91 | |
| 92 Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0, | |
| 93 and specifies the load factor of the hash table which triggers enlarging. | |
| 94 | |
| 442 | 95 Non-standard keyword @code{:weakness} can be @code{nil} (default), |
| 96 @code{t}, @code{key-and-value}, @code{key}, @code{value} or | |
| 97 @code{key-or-value}. @code{t} is an alias for @code{key-and-value}. | |
| 428 | 98 |
| 442 | 99 A key-and-value-weak hash table, also known as a fully-weak or simply |
| 100 as a weak hash table, is one whose pointers do not count as GC | |
| 101 referents: for any key-value pair in the hash table, if the only | |
| 102 remaining pointer to either the key or the value is in a weak hash | |
| 103 table, then the pair will be removed from the hash table, and the key | |
| 104 and value collected. A non-weak hash table (or any other pointer) | |
| 105 would prevent the object from being collected. | |
| 428 | 106 |
| 107 A key-weak hash table is similar to a fully-weak hash table except that | |
| 108 a key-value pair will be removed only if the key remains unmarked | |
| 109 outside of weak hash tables. The pair will remain in the hash table if | |
| 110 the key is pointed to by something other than a weak hash table, even | |
| 111 if the value is not. | |
| 112 | |
| 113 A value-weak hash table is similar to a fully-weak hash table except | |
| 114 that a key-value pair will be removed only if the value remains | |
| 115 unmarked outside of weak hash tables. The pair will remain in the | |
| 116 hash table if the value is pointed to by something other than a weak | |
| 117 hash table, even if the key is not. | |
| 442 | 118 |
| 119 A key-or-value-weak hash table is similar to a fully-weak hash table except | |
| 120 that a key-value pair will be removed only if the value and the key remain | |
| 121 unmarked outside of weak hash tables. The pair will remain in the | |
| 122 hash table if the value or key are pointed to by something other than a weak | |
| 123 hash table, even if the other is not. | |
| 428 | 124 @end defun |
| 125 | |
| 126 @defun copy-hash-table hash-table | |
| 127 This function returns a new hash table which contains the same keys and | |
| 128 values as @var{hash-table}. The keys and values will not themselves be | |
| 129 copied. | |
| 130 @end defun | |
| 131 | |
| 132 @defun hash-table-count hash-table | |
| 133 This function returns the number of entries in @var{hash-table}. | |
| 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-size hash-table | |
| 142 This function returns the current number of slots in @var{hash-table}, | |
| 143 whether occupied or not. | |
| 144 @end defun | |
| 145 | |
| 146 @defun hash-table-rehash-size hash-table | |
| 147 This function returns the current rehash size of @var{hash-table}. | |
| 148 This is a float greater than 1.0; the factor by which @var{hash-table} | |
| 149 is enlarged when the rehash threshold is exceeded. | |
| 150 @end defun | |
| 151 | |
| 152 @defun hash-table-rehash-threshold hash-table | |
| 153 This function returns the current rehash threshold of @var{hash-table}. | |
| 154 This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of | |
| 155 @var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing. | |
| 156 @end defun | |
| 157 | |
| 158 @defun hash-table-weakness hash-table | |
| 159 This function returns the weakness of @var{hash-table}. | |
| 160 This can be one of @code{nil}, @code{t}, @code{key} or @code{value}. | |
| 161 @end defun | |
| 162 | |
| 163 @node Working With Hash Tables | |
| 164 @section Working With Hash Tables | |
| 165 | |
| 166 @defun puthash key value hash-table | |
| 167 This function hashes @var{key} to @var{value} in @var{hash-table}. | |
| 168 @end defun | |
| 169 | |
| 170 @defun gethash key hash-table &optional default | |
| 171 This function finds the hash value for @var{key} in @var{hash-table}. | |
| 172 If there is no entry for @var{key} in @var{hash-table}, @var{default} is | |
| 173 returned (which in turn defaults to @code{nil}). | |
| 174 @end defun | |
| 175 | |
| 176 @defun remhash key hash-table | |
| 177 This function removes the entry for @var{key} from @var{hash-table}. | |
| 178 Does nothing if there is no entry for @var{key} in @var{hash-table}. | |
| 179 @end defun | |
| 180 | |
| 181 @defun clrhash hash-table | |
| 182 This function removes all entries from @var{hash-table}, leaving it empty. | |
| 183 @end defun | |
| 184 | |
| 185 @defun maphash function hash-table | |
| 186 This function maps @var{function} over entries in @var{hash-table}, | |
| 187 calling it with two args, each key and value in the hash table. | |
| 188 | |
| 189 @var{function} may not modify @var{hash-table}, with the one exception | |
| 190 that @var{function} may remhash or puthash the entry currently being | |
| 191 processed by @var{function}. | |
| 192 @end defun | |
| 193 | |
| 194 | |
| 195 @node Weak Hash Tables | |
| 196 @section Weak Hash Tables | |
| 197 @cindex hash table, weak | |
| 198 @cindex weak hash table | |
| 199 | |
| 200 A @dfn{weak hash table} is a special variety of hash table whose | |
| 201 elements do not count as GC referents. For any key-value pair in such a | |
| 202 hash table, if either the key or value (or in some cases, if one | |
| 203 particular one of the two) has no references to it outside of weak hash | |
| 204 tables (and similar structures such as weak lists), the pair will be | |
| 205 removed from the table, and the key and value collected. A non-weak | |
| 206 hash table (or any other pointer) would prevent the objects from being | |
| 207 collected. | |
| 208 | |
| 209 Weak hash tables are useful for keeping track of information in a | |
| 210 non-obtrusive way, for example to implement caching. If the cache | |
| 211 contains objects such as buffers, markers, image instances, etc. that | |
| 212 will eventually disappear and get garbage-collected, using a weak hash | |
| 213 table ensures that these objects are collected normally rather than | |
| 214 remaining around forever, long past their actual period of use. | |
| 215 (Otherwise, you'd have to explicitly map over the hash table every so | |
| 216 often and remove unnecessary elements.) | |
| 217 | |
| 442 | 218 There are four types of weak hash tables: |
| 428 | 219 |
| 220 @table @asis | |
| 442 | 221 @item key-and-value-weak hash tables |
| 222 In these hash tables, also known as fully weak or simply as weak hash | |
| 223 tables, a pair disappears if either the key or the value is unreferenced | |
| 224 outside of the table. | |
| 428 | 225 @item key-weak hash tables |
| 226 In these hash tables, a pair disappears if the key is unreferenced outside | |
| 227 of the table, regardless of how the value is referenced. | |
| 228 @item value-weak hash tables | |
| 229 In these hash tables, a pair disappears if the value is unreferenced outside | |
| 230 of the table, regardless of how the key is referenced. | |
| 442 | 231 @item key-or-value-weak hash tables |
| 232 In these hash tables, a pair disappears if both the key and the value | |
| 233 are unreferenced outside of the table. | |
| 428 | 234 @end table |
| 235 | |
| 236 Also see @ref{Weak Lists}. | |
| 237 | |
| 238 Weak hash tables are created by specifying the @code{:weakness} keyword to | |
| 239 @code{make-hash-table}. |