|
0
|
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 hashtablep object
|
|
|
11 This function returns non-@code{nil} if @var{object} is a hash table.
|
|
|
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 hash table is a data structure that provides mappings from
|
|
|
27 arbitrary Lisp objects (called @dfn{keys}) to other arbitrary Lisp
|
|
|
28 objects (called @dfn{values}). There are many ways other than
|
|
|
29 hash tables of implementing the same sort of mapping, e.g.
|
|
|
30 association lists (@pxref{Association Lists}) and property lists
|
|
|
31 (@pxref{Property Lists}), but hash tables provide much faster lookup.
|
|
|
32
|
|
|
33 When you create a hash table, you specify a size, which indicates the
|
|
|
34 expected number of elements that the table will hold. You are not
|
|
|
35 bound by this size, however; hash tables automatically resize themselves
|
|
|
36 if the number of elements becomes too large.
|
|
|
37
|
|
|
38 (Internally, hash tables are hashed using a modification of the
|
|
|
39 @dfn{linear probing} hash table method. This method hashes each
|
|
|
40 key to a particular spot in the hash table, and then scans forward
|
|
|
41 sequentially until a blank entry is found. To look up a key, hash
|
|
|
42 to the appropriate spot, then search forward for the key until either
|
|
|
43 a key is found or a blank entry stops the search. The modification
|
|
|
44 actually used is called @dfn{double hashing} and involves moving forward
|
|
|
45 by a fixed increment, whose value is computed from the original hash
|
|
|
46 value, rather than always moving forward by one. This eliminates
|
|
|
47 problems with clustering that can arise from the simple linear probing
|
|
|
48 method. For more information, see @cite{Algorithms} (second edition)
|
|
|
49 by Robert Sedgewick, pp. 236-241.)
|
|
|
50
|
|
|
51 @defun make-hashtable size &optional test-fun
|
|
|
52 This function makes a hash table of initial size @var{size}. Comparison
|
|
|
53 between keys is normally done with @code{eql}; i.e. two keys must be the
|
|
|
54 same object to be considered equivalent. However, you can explicitly
|
|
|
55 specify the comparison function using @var{test-fun}, which must be
|
|
|
56 one of @code{eq}, @code{eql}, or @code{equal}.
|
|
|
57
|
|
|
58 Note that currently, @code{eq} and @code{eql} are the same. This will
|
|
|
59 change when bignums are implemented.
|
|
|
60 @end defun
|
|
|
61
|
|
|
62 @defun copy-hashtable old-table
|
|
|
63 This function makes a new hash table which contains the same keys and
|
|
|
64 values as the given table. The keys and values will not themselves be
|
|
|
65 copied.
|
|
|
66 @end defun
|
|
|
67
|
|
|
68 @defun hashtable-fullness table
|
|
|
69 This function returns number of entries in @var{table}.
|
|
|
70 @end defun
|
|
|
71
|
|
|
72 @node Working With Hash Tables
|
|
|
73 @section Working With Hash Tables
|
|
|
74
|
|
|
75 @defun puthash key val table
|
|
|
76 This function hashes @var{key} to @var{val} in @var{table}.
|
|
|
77 @end defun
|
|
|
78
|
|
|
79 @defun gethash key table &optional default
|
|
|
80 This function finds the hash value for @var{key} in @var{table}. If
|
|
|
81 there is no corresponding value, @var{default} is returned (defaults to
|
|
|
82 @code{nil}).
|
|
|
83 @end defun
|
|
|
84
|
|
|
85 @defun remhash key table
|
|
|
86 This function removes the hash value for @var{key} in @var{table}.
|
|
|
87 @end defun
|
|
|
88
|
|
|
89 @defun clrhash table
|
|
|
90 This function flushes @var{table}. Afterwards, the hash table will
|
|
|
91 contain no entries.
|
|
|
92 @end defun
|
|
|
93
|
|
|
94 @defun maphash function table
|
|
|
95 This function maps @var{function} over entries in @var{table}, calling
|
|
|
96 it with two args, each key and value in the table.
|
|
|
97 @end defun
|
|
|
98
|
|
|
99 @node Weak Hash Tables
|
|
|
100 @section Weak Hash Tables
|
|
|
101 @cindex hash table, weak
|
|
|
102 @cindex weak hash table
|
|
|
103
|
|
|
104 A @dfn{weak hash table} is a special variety of hash table whose
|
|
|
105 elements do not count as GC referents. For any key-value pair in such a
|
|
|
106 hash table, if either the key or value (or in some cases, if one
|
|
|
107 particular one of the two) has no references to it outside of weak hash
|
|
|
108 tables (and similar structures such as weak lists), the pair will be
|
|
|
109 removed from the table, and the key and value collected. A non-weak
|
|
|
110 hash table (or any other pointer) would prevent the objects from being
|
|
|
111 collected.
|
|
|
112
|
|
|
113 Weak hash tables are useful for keeping track of information in a
|
|
|
114 non-obtrusive way, for example to implement caching. If the cache
|
|
|
115 contains objects such as buffers, markers, image instances, etc. that
|
|
|
116 will eventually disappear and get garbage-collected, using a weak hash
|
|
|
117 table ensures that these objects are collected normally rather than
|
|
|
118 remaining around forever, long past their actual period of use.
|
|
|
119 (Otherwise, you'd have to explicitly map over the hash table every so
|
|
|
120 often and remove unnecessary elements.)
|
|
|
121
|
|
|
122 There are three types of weak hash tables:
|
|
|
123
|
|
|
124 @table @asis
|
|
|
125 @item fully weak hash tables
|
|
|
126 In these hash tables, a pair disappears if either the key or the value
|
|
|
127 is unreferenced outside of the table.
|
|
|
128 @item key-weak hash tables
|
|
|
129 In these hash tables, a pair disappears if the key is unreferenced outside
|
|
|
130 of the table, regardless of how the value is referenced.
|
|
|
131 @item value-weak hash tables
|
|
|
132 In these hash tables, a pair disappears if the value is unreferenced outside
|
|
|
133 of the table, regardless of how the key is referenced.
|
|
|
134 @end table
|
|
|
135
|
|
|
136 Also see @ref{Weak Lists}.
|
|
|
137
|
|
|
138 @defun make-weak-hashtable size &optional test-fun
|
|
|
139 This function makes a fully weak hash table of initial size @var{size}.
|
|
|
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
|
