(imenu-eager-completion-buffer): Add :version.
[emacs.git] / lispref / hash.texi
blob107935f1ba06e4745a1dda010d4f1593f0d38551
1 @c -*-texinfo-*-
2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1999, 2003 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 @code{equal}, that
80 is, if they are equal in value and either both are integers or both
81 are floating point numbers; otherwise, two distinct objects are never
82 ``the same''.
84 @item eq
85 Any two distinct Lisp objects are ``different'' as keys.
87 @item equal
88 Two Lisp objects are ``the same'', as keys, if they are equal
89 according to @code{equal}.
90 @end table
92 You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to
93 define additional possibilities for @var{test}.
95 @item :weakness @var{weak}
96 The weakness of a hash table specifies whether the presence of a key or
97 value in the hash table preserves it from garbage collection.
99 The value, @var{weak}, must be one of @code{nil}, @code{key},
100 @code{value}, @code{key-or-value}, @code{key-and-value}, or @code{t}
101 which is an alias for @code{key-and-value}.  If @var{weak} is @code{key}
102 then the hash table does not prevent its keys from being collected as
103 garbage (if they are not referenced anywhere else); if a particular key
104 does get collected, the corresponding association is removed from the
105 hash table.
107 If @var{weak} is @code{value}, then the hash table does not prevent
108 values from being collected as garbage (if they are not referenced
109 anywhere else); if a particular value does get collected, the
110 corresponding association is removed from the hash table.
112 If @var{weak} is @code{key-and-value} or @code{t}, both the key and
113 the value must be live in order to preserve the association.  Thus,
114 the hash table does not protect either keys or values from garbage
115 collection; if either one is collected as garbage, that removes the
116 association.
118 If @var{weak} is @code{key-or-value}, either the key or
119 the value can preserve the association.  Thus, associations are
120 removed from the hash table when both their key and value would be
121 collected as garbage (if not for references from weak hash tables).
123 The default for @var{weak} is @code{nil}, so that all keys and values
124 referenced in the hash table are preserved from garbage collection.
126 @item :size @var{size}
127 This specifies a hint for how many associations you plan to store in the
128 hash table.  If you know the approximate number, you can make things a
129 little more efficient by specifying it this way.  If you specify too
130 small a size, the hash table will grow automatically when necessary, but
131 doing that takes some extra time.
133 The default size is 65.
135 @item :rehash-size @var{rehash-size}
136 When you add an association to a hash table and the table is ``full,''
137 it grows automatically.  This value specifies how to make the hash table
138 larger, at that time.
140 If @var{rehash-size} is an integer, it should be positive, and the hash
141 table grows by adding that much to the nominal size.  If
142 @var{rehash-size} is a floating point number, it had better be greater
143 than 1, and the hash table grows by multiplying the old size by that
144 number.
146 The default value is 1.5.
148 @item :rehash-threshold @var{threshold}
149 This specifies the criterion for when the hash table is ``full.''  The
150 value, @var{threshold}, should be a positive floating point number, no
151 greater than 1.  The hash table is ``full'' whenever the actual number of
152 entries exceeds this fraction of the nominal size.  The default for
153 @var{threshold} is 0.8.
154 @end table
155 @end defun
157 @tindex makehash
158 @defun makehash &optional test
159 This is equivalent to @code{make-hash-table}, but with a different style
160 argument list.  The argument @var{test} specifies the method
161 of key lookup.
163 This function is obsolete. Use @code{make-hash-table} instead.
164 @end defun
166 @node Hash Access
167 @section Hash Table Access
169   This section describes the functions for accessing and storing
170 associations in a hash table.
172 @tindex gethash
173 @defun gethash key table &optional default
174 This function looks up @var{key} in @var{table}, and returns its
175 associated @var{value}---or @var{default}, if @var{key} has no
176 association in @var{table}.
177 @end defun
179 @tindex puthash
180 @defun puthash key value table
181 This function enters an association for @var{key} in @var{table}, with
182 value @var{value}.  If @var{key} already has an association in
183 @var{table}, @var{value} replaces the old associated value.
184 @end defun
186 @tindex remhash
187 @defun remhash key table
188 This function removes the association for @var{key} from @var{table}, if
189 there is one.  If @var{key} has no association, @code{remhash} does
190 nothing.
192 @b{Common Lisp note:} In Common Lisp, @code{remhash} returns
193 non-@code{nil} if it actually removed an association and @code{nil}
194 otherwise.  In Emacs Lisp, @code{remhash} always returns @code{nil}.
195 @end defun
197 @tindex clrhash
198 @defun clrhash table
199 This function removes all the associations from hash table @var{table},
200 so that it becomes empty.  This is also called @dfn{clearing} the hash
201 table.
203 @b{Common Lisp note:} In Common Lisp, @code{clrhash} returns the empty
204 @var{table}.  In Emacs Lisp, it returns @code{nil}.
205 @end defun
207 @tindex maphash
208 @defun maphash function table
209 @anchor{Definition of maphash}
210 This function calls @var{function} once for each of the associations in
211 @var{table}.  The function @var{function} should accept two
212 arguments---a @var{key} listed in @var{table}, and its associated
213 @var{value}.
214 @end defun
216 @node Defining Hash
217 @section Defining Hash Comparisons
218 @cindex hash code
220   You can define new methods of key lookup by means of
221 @code{define-hash-table-test}.  In order to use this feature, you need
222 to understand how hash tables work, and what a @dfn{hash code} means.
224   You can think of a hash table conceptually as a large array of many
225 slots, each capable of holding one association.  To look up a key,
226 @code{gethash} first computes an integer, the hash code, from the key.
227 It reduces this integer modulo the length of the array, to produce an
228 index in the array.  Then it looks in that slot, and if necessary in
229 other nearby slots, to see if it has found the key being sought.
231   Thus, to define a new method of key lookup, you need to specify both a
232 function to compute the hash code from a key, and a function to compare
233 two keys directly.
235 @tindex define-hash-table-test
236 @defun define-hash-table-test name test-fn hash-fn
237 This function defines a new hash table test, named @var{name}.
239 After defining @var{name} in this way, you can use it as the @var{test}
240 argument in @code{make-hash-table}.  When you do that, the hash table
241 will use @var{test-fn} to compare key values, and @var{hash-fn} to compute
242 a ``hash code'' from a key value.
244 The function @var{test-fn} should accept two arguments, two keys, and
245 return non-@code{nil} if they are considered ``the same.''
247 The function @var{hash-fn} should accept one argument, a key, and return
248 an integer that is the ``hash code'' of that key.  For good results, the
249 function should use the whole range of integer values for hash codes,
250 including negative integers.
252 The specified functions are stored in the property list of @var{name}
253 under the property @code{hash-table-test}; the property value's form is
254 @code{(@var{test-fn} @var{hash-fn})}.
255 @end defun
257 @tindex sxhash
258 @defun sxhash obj
259 This function returns a hash code for Lisp object @var{obj}.
260 This is an integer which reflects the contents of @var{obj}
261 and the other Lisp objects it points to.
263 If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash
264 @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer.
266 If the two objects are not equal, the values returned by @code{sxhash}
267 are usually different, but not always; once in a rare while, by luck,
268 you will encounter two distinct-looking objects that give the same
269 result from @code{sxhash}.
270 @end defun
272   This example creates a hash table whose keys are strings that are
273 compared case-insensitively.
275 @example
276 (defun case-fold-string= (a b)
277   (compare-strings a nil nil b nil nil t))
279 (defun case-fold-string-hash (a)
280   (sxhash (upcase a)))
282 (define-hash-table-test 'case-fold 'case-fold-string=
283                         'case-fold-string-hash))
285 (make-hash-table :test 'case-fold)
286 @end example
288   Here is how you could define a hash table test equivalent to the
289 predefined test value @code{equal}.  The keys can be any Lisp object,
290 and equal-looking objects are considered the same key.
292 @example
293 (define-hash-table-test 'contents-hash 'equal 'sxhash)
295 (make-hash-table :test 'contents-hash)
296 @end example
298 @node Other Hash
299 @section Other Hash Table Functions
301   Here are some other functions for working with hash tables.
303 @tindex hash-table-p
304 @defun hash-table-p table
305 This returns non-@code{nil} if @var{table} is a hash table object.
306 @end defun
308 @tindex copy-hash-table
309 @defun copy-hash-table table
310 This function creates and returns a copy of @var{table}.  Only the table
311 itself is copied---the keys and values are shared.
312 @end defun
314 @tindex hash-table-count
315 @defun hash-table-count table
316 This function returns the actual number of entries in @var{table}.
317 @end defun
319 @tindex hash-table-test
320 @defun hash-table-test table
321 This returns the @var{test} value that was given when @var{table} was
322 created, to specify how to hash and compare keys.  See
323 @code{make-hash-table} (@pxref{Creating Hash}).
324 @end defun
326 @tindex hash-table-weakness
327 @defun hash-table-weakness table
328 This function returns the @var{weak} value that was specified for hash
329 table @var{table}.
330 @end defun
332 @tindex hash-table-rehash-size
333 @defun hash-table-rehash-size table
334 This returns the rehash size of @var{table}.
335 @end defun
337 @tindex hash-table-rehash-threshold
338 @defun hash-table-rehash-threshold table
339 This returns the rehash threshold of @var{table}.
340 @end defun
342 @tindex hash-table-size
343 @defun hash-table-size table
344 This returns the current nominal size of @var{table}.
345 @end defun
347 @ignore
348    arch-tag: 3b5107f9-d2f0-47d5-ad61-3498496bea0e
349 @end ignore