Mercurial > hg > xemacs-beta

comparison man/lispref/hash-tables.texi @ 0:376386a54a3c r19-14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r19-14
author cvs
date Mon, 13 Aug 2007 08:45:50 +0200
parents
children 8626e4521993
comparison
equal deleted inserted replaced
-1:000000000000 0:376386a54a3c
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