annotate lispref/hash.texi @ 32635:9a3072529aa5

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