*** empty log message ***
[emacs.git] / lispref / hash.texi
blobe20b67b430a766cdb30af8cee5260ec8346bf558
1 @c -*-texinfo-*-
2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1999 Free Software Foundation, Inc. 
4 @c See the file elisp.texi for copying conditions.
5 @setfilename ../info/hash
6 @node Hash Tables, Symbols, Sequences Arrays Vectors, Top
7 @chapter Hash Tables
8 @cindex hash tables
10   A hash table is a very fast kind of lookup table, somewhat like
11 an alist in that it maps keys to corresponding values.  It differs
12 from an alist in these ways:
14 @itemize @bullet
15 @item
16 Lookup in a hash table is extremely fast for large tables---in fact, the
17 time required is essentially @emph{independent} of how many elements are
18 stored in the table.  For smaller tables (a few tens of elements)
19 alists may still be faster because hash tables have a more-or-less
20 constant overhead.
22 @item
23 The correspondences in a hash table are in no particular order.
25 @item
26 There is no way to share structure between two hash tables,
27 the way two alists can share a common tail.
28 @end itemize
30   Emacs Lisp (starting with Emacs 21) provides a general-purpose hash
31 table data type, along with a series of functions for operating on them.
32 Hash tables have no read syntax, and print in hash notation, like this:
34 @example
35 (make-hash-table)
36      @result{} #<hash-table 'eql nil 0/65 0x83af980>
37 @end example
39 @noindent
40 (The term ``hash notation'' refers to the initial @samp{#}
41 character---@pxref{Printed Representation}---and has nothing to do with
42 the term ``hash table.'')
44   Obarrays are also a kind of hash table, but they are a different type
45 of object and are used only for recording interned symbols
46 (@pxref{Creating Symbols}).
48 @menu
49 * Creating Hash::
50 * Hash Access::
51 * Defining Hash::
52 * Other Hash::
53 @end menu
55 @node Creating Hash
56 @section Creating Hash Tables
58   The principal function for creating a hash table is
59 @code{make-hash-table}.
61 @tindex make-hash-table
62 @defun make-hash-table &rest keyword-args
63 This function creates a new hash table according to the specified
64 arguments.  The arguments should consist of alternating keywords
65 (particular symbols recognized specially) and values corresponding to
66 them.
68 Several keywords make sense in @code{make-hash-table}, but the only two
69 that you really need to know about are @code{:test} and @code{:weakness}.
71 @table @code
72 @item :test @var{test}
73 This specifies the method of key lookup for this hash table.  The
74 default is @code{eql}; @code{eq} and @code{equal} are other
75 alternatives:
77 @table @code
78 @item eql
79 Keys which are numbers are ``the same'' if they are equal in value;
80 otherwise, two distinct objects are never ``the same''.
82 @item eq
83 Any two distinct Lisp objects are ``different'' as keys.
85 @item equal
86 Two Lisp objects are ``the same'', as keys, if they are equal
87 according to @code{equal}.
88 @end table
90 You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to
91 define additional possibilities for @var{test}.
93 @item :weakness @var{weak}
94 The weakness of a hash table specifies whether the presence of a key or
95 value in the hash table preserves it from garbage collection.
97 The value, @var{weak}, must be one of @code{nil}, @code{key},
98 @code{value} or @code{t}.  If @var{weak} is @code{key} or @code{t}, then
99 the hash table does not prevent its keys from being collected as garbage
100 (if they are not referenced anywhere else); if a particular key does get
101 collected, the corresponding association is removed from the hash table.
103 Likewise, if @var{weak} is @code{value} or @code{t}, then the hash table
104 does not prevent values from being collected as garbage (if they are not
105 referenced anywhere else); if a particular value does get collected, the
106 corresponding association is removed from the hash table.
108 The default for @var{weak} is @code{nil}, so that all keys and values
109 referenced in the hash table are preserved from garbage collection.  If
110 @var{weak} is @code{t}, neither keys nor values are protected (that is,
111 both are weak).
113 @item :size @var{size}
114 This specifies a hint for how many associations you plan to store in the
115 hash table.  If you know the approximate number, you can make things a
116 little more efficient by specifying it this way.  If you specify too
117 small a size, the hash table will grow automatically when necessary, but
118 doing that takes some extra time.
120 The default size is 65.
122 @item :rehash-size @var{rehash-size}
123 When you add an association to a hash table and the table is ``full,''
124 it grows automatically.  This value specifies how to make the hash table
125 larger, at that time.
127 If @var{rehash-size} is an integer, it should be positive, and the hash
128 table grows by adding that much to the nominal size.  If
129 @var{rehash-size} is a floating point number, it had better be greater
130 than 1, and the hash table grows by multiplying the old size by that
131 number.
133 The default value is 1.5.
135 @item :rehash-threshold @var{threshold}
136 This specifies the criterion for when the hash table is ``full.''  The
137 value, @var{threshold}, should be a positive floating point number, no
138 greater than 1.  The hash table is ``full'' whenever the actual number of
139 entries exceeds this fraction of the nominal size.  The default for
140 @var{threshold} is 0.8.
141 @end table
142 @end defun
144 @tindex makehash
145 @defun makehash &optional test
146 This is equivalent to @code{make-hash-table}, but with a different style
147 argument list.  The argument @var{test} specifies the method
148 of key lookup.
150 If you want to specify other parameters, you should use
151 @code{make-hash-table}.
152 @end defun
154 @node Hash Access
155 @section Hash Table Access
157   This section describes the functions for accessing and storing
158 associations in a hash table.
160 @tindex gethash
161 @defun gethash key table &optional default
162 This function looks up @var{key} in @var{table}, and returns its
163 associated @var{value}---or @var{default}, if @var{key} has no
164 association in @var{table}.
165 @end defun
167 @tindex puthash
168 @defun puthash key value table 
169 This function enters an association for @var{key} in @var{table}, with
170 value @var{value}.  If @var{key} already has an association in
171 @var{table}, @var{value} replaces the old associated value.
172 @end defun
174 @tindex remhash
175 @defun remhash key table
176 This function removes the association for @var{key} from @var{table}, if
177 there is one.  If @var{key} has no association, @code{remhash} does
178 nothing.
179 @end defun
181 @tindex clrhash
182 @defun clrhash table
183 This function removes all the associations from hash table @var{table},
184 so that it becomes empty.  This is also called @dfn{clearing} the hash
185 table.
186 @end defun
188 @tindex maphash
189 @defun maphash function table
190 This function calls @var{function} once for each of the associations in
191 @var{table}.  The function @var{function} should accept two
192 arguments---a @var{key} listed in @var{table}, and its associated
193 @var{value}.
194 @end defun
196 @node Defining Hash
197 @section Defining Hash Comparisons
198 @cindex hash code
200   You can define new methods of key lookup by means of
201 @code{define-hash-table-test}.  In order to use this feature, you need
202 to understand how hash tables work, and what a @dfn{hash code} means.
204   You can think of a hash table conceptually as a large array of many
205 slots, each capable of holding one association.  To look up a key,
206 @code{gethash} first computes an integer, the hash code, from the key.
207 It reduces this integer modulo the length of the array, to produce an
208 index in the array.  Then it looks in that slot, and if necessary in
209 other nearby slots, to see if it has found the key being sought.
211   Thus, to define a new method of key lookup, you need to specify both a
212 function to compute the hash code from a key, and a function to compare
213 two keys directly.
215 @tindex define-hash-table-test
216 @defun define-hash-table-test name test-fn hash-fn
217 This function defines a new hash table test, named @var{name}.
219 After defining @var{name} in this way, you can use it as the @var{test}
220 argument in @code{make-hash-table}.  When you do that, the hash table
221 will use @var{test-fn} to compare key values, and @var{hash-fn} to compute
222 a ``hash code'' from a key value.
224 The function @var{test-fn} should accept two arguments, two keys, and
225 return non-@code{nil} if they are considered ``the same.''
227 The function @var{hash-fn} should accept one argument, a key, and return
228 an integer that is the ``hash code'' of that key.  For good results, the
229 function should use the whole range of integer values for hash codes,
230 including negative integers.
232 The specified functions are stored in the property list of @var{name}
233 under the property @code{hash-table-test}; the property value's form is
234 @code{(@var{test-fn} @var{hash-fn})}.
236 This example creates a hash table whose keys are strings that are
237 compared case-insensitively.
239 @example
240 (defun case-fold-string= (a b)
241   (compare-strings a nil nil b nil nil t))
243 (defun case-fold-string-hash (a)
244   (sxhash (upcase a)))
246 (define-hash-table-test 'case-fold 'case-fold-string= 
247                         'case-fold-string-hash))
249 (make-hash-table :test 'case-fold)
250 @end example
251 @end defun
253 @tindex sxhash
254 @defun sxhash obj
255 This function returns a hash code for Lisp object @var{obj}.
256 This is an integer which reflects the contents of @var{obj}
257 and the other Lisp objects it points to.
259 If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash
260 @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer.
262 If the two objects are not equal, the values returned by @code{sxhash}
263 are usually different, but not always; but once in a rare while, by
264 luck, you will encounter two distinct-looking objects that give the same
265 result from @code{sxhash}.
266 @end defun
268 @node Other Hash
269 @section Other Hash Table Functions
271   Here are some other functions for working with hash tables.
273 @tindex hash-table-p
274 @defun hash-table-p table
275 This returns non-@code{nil} if @var{table} is a hash table object.
276 @end defun
278 @tindex copy-hash-table
279 @defun copy-hash-table table
280 This function creates and returns a copy of @var{table}.  Only the table
281 itself is copied---the keys and values are shared.
282 @end defun
284 @tindex hash-table-count
285 @defun hash-table-count table
286 This function returns the actual number of entries in @var{table}.
287 @end defun
289 @tindex hash-table-test
290 @defun hash-table-test table
291 This returns the @var{test} value that was given when @var{table} was
292 created, to specify how to hash and compare keys.  See
293 @code{make-hash-table} (@pxref{Creating Hash}).
294 @end defun
296 @tindex hash-table-weakness
297 @defun hash-table-weakness table
298 This function returns the @var{weak} value that was specified for hash
299 table @var{table}.
300 @end defun
302 @tindex hash-table-rehash-size
303 @defun hash-table-rehash-size table
304 This returns the rehash size of @var{table}.
305 @end defun
307 @tindex hash-table-rehash-threshold
308 @defun hash-table-rehash-threshold table
309 This returns the rehash threshold of @var{table}.
310 @end defun
312 @tindex hash-table-size
313 @defun hash-table-size table
314 This returns the current nominal size of @var{table}.
315 @end defun