3
@node Hash Tables, Filenames, Sequences, Top
7
* Hash Table Concepts::
8
* Hash Tables Dictionary::
11
@node Hash Table Concepts, Hash Tables Dictionary, Hash Tables, Hash Tables
12
@section Hash Table Concepts
14
@c including concept-hash-tables
17
* Hash-Table Operations::
18
* Modifying Hash Table Keys::
21
@node Hash-Table Operations, Modifying Hash Table Keys, Hash Table Concepts, Hash Table Concepts
22
@subsection Hash-Table Operations
24
Figure 18--1 lists some @i{defined names} that are applicable
25
to @i{hash tables}. The following rules apply to @i{hash tables}.
30
A @i{hash table} can only associate one value with a given
31
key. If an attempt is made to add a second value for a given key,
32
the second value will replace the first.
33
Thus, adding a value to a @i{hash table} is a destructive operation;
34
the @i{hash table} is modified.
37
There are four kinds of @i{hash tables}:
38
those whose keys are compared with @b{eq},
39
those whose keys are compared with @b{eql},
40
those whose keys are compared with @b{equal}, and
42
those whose keys are compared with @b{equalp}.
45
@i{Hash tables} are created by @b{make-hash-table}.
46
@b{gethash} is used to look up a key and find the associated value.
47
New entries are added to @i{hash tables} using @b{setf} with @b{gethash}.
48
@b{remhash} is used to remove an entry.
52
(setq a (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32536573>
53
(setf (gethash 'color a) 'brown) @result{} BROWN
54
(setf (gethash 'name a) 'fred) @result{} FRED
55
(gethash 'color a) @result{} BROWN, @i{true}
56
(gethash 'name a) @result{} FRED, @i{true}
57
(gethash 'pointy a) @result{} NIL, @i{false}
60
In this example, the symbols @t{color} and @t{name} are being used as
61
keys, and the symbols @t{brown} and @t{fred} are being used as the
62
associated values. The @i{hash table}
63
has two items in it, one of which
64
associates from @t{color} to @t{brown}, and the other of which
65
associates from @t{name} to @t{fred}.
68
A key or a value may be any @i{object}.
71
The existence of an entry in the @i{hash table} can be determined
72
from the @i{secondary value} returned by @b{gethash}.
78
@w{ clrhash hash-table-p remhash }
79
@w{ gethash make-hash-table sxhash }
80
@w{ hash-table-count maphash }
83
@w{ Figure 18--1: Hash-table defined names }
88
@node Modifying Hash Table Keys, , Hash-Table Operations, Hash Table Concepts
89
@subsection Modifying Hash Table Keys
91
The function supplied as the @t{:test} argument to @b{make-hash-table}
92
specifies the `equivalence test' for the @i{hash table} it creates.
94
An @i{object} is `visibly modified' with regard to an equivalence test
95
if there exists some set of @i{objects} (or potential @i{objects})
96
which are equivalent to the @i{object} before the modification but are
97
no longer equivalent afterwards.
99
If an @i{object} O_1 is used as a key in a @i{hash table} H
100
and is then visibly modified with regard to the equivalence test of H,
101
then the consequences are unspecified if O_1, or any @i{object}
102
O_2 equivalent to O_1 under the equivalence test (either before
103
or after the modification), is used as a key in further operations on H.
104
The consequences of using O_1 as a key are unspecified
105
even if O_1 is visibly modified
106
and then later modified again in such a way as
107
to undo the visible modification.
109
Following are specifications of the modifications which are visible to the
110
equivalence tests which must be supported by @i{hash tables}. The modifications
111
are described in terms of modification of components, and are defined
112
recursively. Visible modifications of components of the @i{object} are
113
visible modifications of the @i{object}.
116
* Visible Modification of Objects with respect to EQ and EQL::
117
* Visible Modification of Objects with respect to EQUAL::
118
* Visible Modification of Conses with respect to EQUAL::
119
* Visible Modification of Bit Vectors and Strings with respect to EQUAL::
120
* Visible Modification of Objects with respect to EQUALP::
121
* Visible Modification of Structures with respect to EQUALP::
122
* Visible Modification of Arrays with respect to EQUALP::
123
* Visible Modification of Hash Tables with respect to EQUALP::
124
* Visible Modifications by Language Extensions::
127
@node Visible Modification of Objects with respect to EQ and EQL, Visible Modification of Objects with respect to EQUAL, Modifying Hash Table Keys, Modifying Hash Table Keys
128
@subsubsection Visible Modification of Objects with respect to EQ and EQL
130
No @i{standardized} @i{function} is provided that is capable of visibly
131
modifying an @i{object} with regard to @b{eq} or @b{eql}.
133
@node Visible Modification of Objects with respect to EQUAL, Visible Modification of Conses with respect to EQUAL, Visible Modification of Objects with respect to EQ and EQL, Modifying Hash Table Keys
134
@subsubsection Visible Modification of Objects with respect to EQUAL
136
As a consequence of the behavior for @b{equal},
137
the rules for visible modification of @i{objects} not explicitly mentioned in this
138
section are inherited from those in @ref{Visible Modification of Objects with respect to EQ and EQL}.
140
@node Visible Modification of Conses with respect to EQUAL, Visible Modification of Bit Vectors and Strings with respect to EQUAL, Visible Modification of Objects with respect to EQUAL, Modifying Hash Table Keys
141
@subsubsection Visible Modification of Conses with respect to EQUAL
143
Any visible change to the @i{car} or the @i{cdr} of a @i{cons}
144
is considered a visible modification with regard to @b{equal}.
146
@node Visible Modification of Bit Vectors and Strings with respect to EQUAL, Visible Modification of Objects with respect to EQUALP, Visible Modification of Conses with respect to EQUAL, Modifying Hash Table Keys
147
@subsubsection Visible Modification of Bit Vectors and Strings with respect to EQUAL
149
For a @i{vector} of @i{type} @b{bit-vector} or of @i{type} @b{string}, any visible change
150
to an @i{active} @i{element} of the @i{vector},
151
or to the @i{length} of the @i{vector} (if it is @i{actually adjustable}
152
or has a @i{fill pointer})
153
is considered a visible modification with regard to @b{equal}.
155
@node Visible Modification of Objects with respect to EQUALP, Visible Modification of Structures with respect to EQUALP, Visible Modification of Bit Vectors and Strings with respect to EQUAL, Modifying Hash Table Keys
156
@subsubsection Visible Modification of Objects with respect to EQUALP
158
As a consequence of the behavior for @b{equalp},
159
the rules for visible modification of @i{objects} not explicitly mentioned in this
160
section are inherited from those in @ref{Visible Modification of Objects with respect to EQUAL}.
162
@node Visible Modification of Structures with respect to EQUALP, Visible Modification of Arrays with respect to EQUALP, Visible Modification of Objects with respect to EQUALP, Modifying Hash Table Keys
163
@subsubsection Visible Modification of Structures with respect to EQUALP
165
Any visible change to a @i{slot} of a @i{structure}
166
is considered a visible modification with regard to @b{equalp}.
168
@node Visible Modification of Arrays with respect to EQUALP, Visible Modification of Hash Tables with respect to EQUALP, Visible Modification of Structures with respect to EQUALP, Modifying Hash Table Keys
169
@subsubsection Visible Modification of Arrays with respect to EQUALP
171
In an @i{array}, any visible change
172
to an @i{active} @i{element},
173
to the @i{fill pointer} (if the @i{array} can and does have one),
174
or to the @i{dimensions} (if the @i{array} is @i{actually adjustable})
175
is considered a visible modification with regard to @b{equalp}.
177
@node Visible Modification of Hash Tables with respect to EQUALP, Visible Modifications by Language Extensions, Visible Modification of Arrays with respect to EQUALP, Modifying Hash Table Keys
178
@subsubsection Visible Modification of Hash Tables with respect to EQUALP
180
In a @i{hash table}, any visible change
181
to the count of entries in the @i{hash table},
183
or to the values associated with the keys
184
is considered a visible modification with regard to @b{equalp}.
186
Note that the visibility of modifications to the keys depends on the equivalence test
187
of the @i{hash table}, not on the specification of @b{equalp}.
189
@node Visible Modifications by Language Extensions, , Visible Modification of Hash Tables with respect to EQUALP, Modifying Hash Table Keys
190
@subsubsection Visible Modifications by Language Extensions
192
@i{Implementations} that extend the language by providing additional mutator
193
functions (or additional behavior for existing mutator functions) must
194
document how the use of these extensions interacts with equivalence tests and
195
@i{hash table} searches.
197
@i{Implementations} that extend the language by defining additional acceptable
198
equivalence tests for @i{hash tables} (allowing additional values for the @t{:test}
199
argument to @b{make-hash-table}) must document the visible components of these
202
@c end of including concept-hash-tables
204
@node Hash Tables Dictionary, , Hash Table Concepts, Hash Tables
205
@section Hash Tables Dictionary
207
@c including dict-hash-tables
214
* hash-table-rehash-size::
215
* hash-table-rehash-threshold::
221
* with-hash-table-iterator::
226
@node hash-table, make-hash-table, Hash Tables Dictionary, Hash Tables Dictionary
227
@subsection hash-table [System Class]
229
@subsubheading Class Precedence List::
233
@subsubheading Description::
235
@i{Hash tables} provide a way of mapping any @i{object} (a @i{key})
236
to an associated @i{object} (a @i{value}).
238
@subsubheading See Also::
240
@ref{Hash Table Concepts},
241
@ref{Printing Other Objects}
243
@subsubheading Notes::
245
The intent is that this mapping be implemented by a hashing mechanism,
246
such as that described in Section 6.4 ``Hashing'' of @b{The Art of Computer Programming, Volume 3}
247
(pp506-549). In spite of this intent, no @i{conforming implementation}
248
is required to use any particular technique to implement the mapping.
250
@node make-hash-table, hash-table-p, hash-table, Hash Tables Dictionary
251
@subsection make-hash-table [Function]
253
@code{make-hash-table} @i{@r{&key} test size rehash-size rehash-threshold} @result{} @i{hash-table}
255
@subsubheading Arguments and Values::
257
@i{test}---a @i{designator} for one of the @i{functions}
264
The default is @b{eql}.
266
@i{size}---a non-negative @i{integer}.
268
The default is @i{implementation-dependent}.
270
@i{rehash-size}---a @i{real} of @i{type} @t{(or (integer 1 *) (float (1.0) *))}.
271
The default is @i{implementation-dependent}.
273
@i{rehash-threshold}---a @i{real} of @i{type} @t{(real 0 1)}.
274
The default is @i{implementation-dependent}.
276
@i{hash-table}---a @i{hash table}.
278
@subsubheading Description::
280
Creates and returns a new @i{hash table}.
282
@i{test} determines how @i{keys} are compared.
283
An @i{object} is said to be present in the @i{hash-table}
284
if that @i{object} is the @i{same} under the @i{test}
285
as the @i{key} for some entry in the @i{hash-table}.
287
@i{size} is a hint to the @i{implementation} about how much initial space
288
to allocate in the @i{hash-table}.
290
This information, taken together with the @i{rehash-threshold}, controls
291
the approximate number of entries which it should be possible
292
to insert before the table has to grow.
294
The actual size might be rounded up from @i{size} to the next `good' size;
295
for example, some @i{implementations} might round to the next prime number.
297
@i{rehash-size} specifies a minimum amount to increase the size of the
298
@i{hash-table} when it becomes full
299
enough to require rehashing;
300
see @i{rehash-theshold} below.
302
If @i{rehash-size} is an @i{integer},
303
the expected growth rate for the table is additive and
304
the @i{integer} is the number of entries to add;
305
if it is a @i{float},
306
the expected growth rate for the table is multiplicative and
307
the @i{float} is the ratio of the new size to the old size.
309
As with @i{size}, the actual size of the increase might be rounded up.
311
@i{rehash-threshold} specifies how full the @i{hash-table} can get
314
It specifies the maximum desired hash-table occupancy level.
316
The @i{values} of @i{rehash-size} and @i{rehash-threshold} do not constrain the
317
@i{implementation} to use any particular method for computing when and by how much
318
the size of @i{hash-table} should be enlarged. Such decisions are
319
@i{implementation-dependent}, and these @i{values} only hints
320
from the @i{programmer} to the @i{implementation}, and the @i{implementation}
321
is permitted to ignore them.
323
@subsubheading Examples::
326
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 46142754>
327
(setf (gethash "one" table) 1) @result{} 1
328
(gethash "one" table) @result{} NIL, @i{false}
329
(setq table (make-hash-table :test 'equal)) @result{} #<HASH-TABLE EQUAL 0/139 46145547>
330
(setf (gethash "one" table) 1) @result{} 1
331
(gethash "one" table) @result{} 1, T
332
(make-hash-table :rehash-size 1.5 :rehash-threshold 0.7)
333
@result{} #<HASH-TABLE EQL 0/120 46156620>
336
@subsubheading See Also::
342
@node hash-table-p, hash-table-count, make-hash-table, Hash Tables Dictionary
343
@subsection hash-table-p [Function]
345
@code{hash-table-p} @i{object} @result{} @i{generalized-boolean}
347
@subsubheading Arguments and Values::
349
@i{object}---an @i{object}.
351
@i{generalized-boolean}---a @i{generalized boolean}.
353
@subsubheading Description::
355
Returns @i{true} if @i{object} is of @i{type} @b{hash-table};
356
otherwise, returns @i{false}.
358
@subsubheading Examples::
361
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32511220>
362
(hash-table-p table) @result{} @i{true}
363
(hash-table-p 37) @result{} @i{false}
364
(hash-table-p '((a . 1) (b . 2))) @result{} @i{false}
367
@subsubheading Notes::
370
(hash-table-p @i{object}) @equiv{} (typep @i{object} 'hash-table)
373
@node hash-table-count, hash-table-rehash-size, hash-table-p, Hash Tables Dictionary
374
@subsection hash-table-count [Function]
376
@code{hash-table-count} @i{hash-table} @result{} @i{count}
378
@subsubheading Arguments and Values::
380
@i{hash-table}---a @i{hash table}.
382
@i{count}---a non-negative @i{integer}.
384
@subsubheading Description::
386
Returns the number of entries in the @i{hash-table}.
387
If @i{hash-table} has just been created
388
or newly cleared (see @b{clrhash})
389
the entry count is @t{0}.
391
@subsubheading Examples::
394
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32115135>
395
(hash-table-count table) @result{} 0
396
(setf (gethash 57 table) "fifty-seven") @result{} "fifty-seven"
397
(hash-table-count table) @result{} 1
398
(dotimes (i 100) (setf (gethash i table) i)) @result{} NIL
399
(hash-table-count table) @result{} 100
402
@subsubheading Affected By::
406
@b{setf} of @b{gethash}
408
@subsubheading See Also::
410
@ref{hash-table-size}
412
@subsubheading Notes::
414
The following relationships are functionally correct, although in practice
415
using @b{hash-table-count} is probably much faster:
418
(hash-table-count @i{table}) @equiv{}
419
(loop for value being the hash-values of @i{table} count t) @equiv{}
421
(maphash #'(lambda (key value)
422
(declare (ignore key value))
428
@node hash-table-rehash-size, hash-table-rehash-threshold, hash-table-count, Hash Tables Dictionary
429
@subsection hash-table-rehash-size [Function]
431
@code{hash-table-rehash-size} @i{hash-table} @result{} @i{rehash-size}
433
@subsubheading Arguments and Values::
435
@i{hash-table}---a @i{hash table}.
437
@i{rehash-size}---a @i{real} of @i{type} @t{(or (integer 1 *) (float (1.0) *))}.
439
@subsubheading Description::
441
Returns the current rehash size of @i{hash-table},
442
suitable for use in a call to @b{make-hash-table}
443
in order to produce a @i{hash table}
444
with state corresponding to the current state of the @i{hash-table}.
446
@subsubheading Examples::
449
(setq table (make-hash-table :size 100 :rehash-size 1.4))
450
@result{} #<HASH-TABLE EQL 0/100 2556371>
451
(hash-table-rehash-size table) @result{} 1.4
454
@subsubheading Exceptional Situations::
456
Should signal an error of @i{type} @b{type-error}
457
if @i{hash-table} is not a @i{hash table}.
459
@subsubheading See Also::
461
@ref{make-hash-table}
463
@ref{hash-table-rehash-threshold}
465
@subsubheading Notes::
467
If the hash table was created with an @i{integer} rehash size,
468
the result is an @i{integer},
469
indicating that the rate of growth of the @i{hash-table} when rehashed
470
is intended to be additive;
472
the result is a @i{float},
473
indicating that the rate of growth of the @i{hash-table} when rehashed
474
is intended to be multiplicative.
475
However, this value is only advice to the @i{implementation};
476
the actual amount by which the @i{hash-table} will grow upon rehash is
477
@i{implementation-dependent}.
479
@node hash-table-rehash-threshold, hash-table-size, hash-table-rehash-size, Hash Tables Dictionary
480
@subsection hash-table-rehash-threshold [Function]
482
@code{hash-table-rehash-threshold} @i{hash-table} @result{} @i{rehash-threshold}
484
@subsubheading Arguments and Values::
486
@i{hash-table}---a @i{hash table}.
488
@i{rehash-threshold}---a @i{real} of @i{type} @t{(real 0 1)}.
490
@subsubheading Description::
492
Returns the current rehash threshold of @i{hash-table}, which is
493
suitable for use in a call to @b{make-hash-table} in order to
494
produce a @i{hash table} with state corresponding to the current
495
state of the @i{hash-table}.
497
@subsubheading Examples::
500
(setq table (make-hash-table :size 100 :rehash-threshold 0.5))
501
@result{} #<HASH-TABLE EQL 0/100 2562446>
502
(hash-table-rehash-threshold table) @result{} 0.5
505
@subsubheading Exceptional Situations::
507
Should signal an error of @i{type} @b{type-error}
508
if @i{hash-table} is not a @i{hash table}.
510
@subsubheading See Also::
512
@ref{make-hash-table}
514
@ref{hash-table-rehash-size}
516
@node hash-table-size, hash-table-test, hash-table-rehash-threshold, Hash Tables Dictionary
517
@subsection hash-table-size [Function]
519
@code{hash-table-size} @i{hash-table} @result{} @i{size}
521
@subsubheading Arguments and Values::
523
@i{hash-table}---a @i{hash table}.
525
@i{size}---a non-negative @i{integer}.
527
@subsubheading Description::
529
Returns the current size of @i{hash-table}, which is suitable for use in
530
a call to @b{make-hash-table} in order to produce a @i{hash table}
531
with state corresponding to the current state of the @i{hash-table}.
533
@subsubheading Exceptional Situations::
535
Should signal an error of @i{type} @b{type-error}
536
if @i{hash-table} is not a @i{hash table}.
538
@subsubheading See Also::
540
@ref{hash-table-count}
542
@ref{make-hash-table}
544
@node hash-table-test, gethash, hash-table-size, Hash Tables Dictionary
545
@subsection hash-table-test [Function]
547
@code{hash-table-test} @i{hash-table} @result{} @i{test}
549
@subsubheading Arguments and Values::
551
@i{hash-table}---a @i{hash table}.
553
@i{test}---a @i{function designator}.
554
For the four @i{standardized} @i{hash table} test @i{functions}
555
(see @b{make-hash-table}), the @i{test} value returned
556
is always a @i{symbol}. If an @i{implementation} permits additional
557
tests, it is @i{implementation-dependent} whether such tests are
558
returned as @i{function} @i{objects} or @i{function names}.
560
@subsubheading Description::
562
Returns the test used for comparing @i{keys} in @i{hash-table}.
564
@subsubheading Exceptional Situations::
566
Should signal an error of @i{type} @b{type-error}
567
if @i{hash-table} is not a @i{hash table}.
569
@subsubheading See Also::
571
@ref{make-hash-table}
573
@node gethash, remhash, hash-table-test, Hash Tables Dictionary
574
@subsection gethash [Accessor]
576
@code{gethash} @i{key hash-table @r{&optional} default} @result{} @i{value, present-p}
578
(setf (@code{ gethash} @i{key hash-table @r{&optional} default}) new-value)@*
580
@subsubheading Arguments and Values::
582
@i{key}---an @i{object}.
584
@i{hash-table}---a @i{hash table}.
586
@i{default}---an @i{object}.
587
The default is @b{nil}.
589
@i{value}---an @i{object}.
591
@i{present-p}---a @i{generalized boolean}.
593
@subsubheading Description::
595
@i{Value} is the @i{object} in @i{hash-table} whose @i{key}
596
is the @i{same} as @i{key} under the @i{hash-table}'s equivalence test.
597
If there is no such entry, @i{value} is the @i{default}.
599
@i{Present-p} is @i{true} if an entry is found; otherwise, it is @i{false}.
601
@b{setf} may be used with @b{gethash} to modify the @i{value}
602
associated with a given @i{key}, or to add a new entry.
604
When a @b{gethash} @i{form} is used as a @b{setf} @i{place},
605
any @i{default} which is supplied is evaluated according to normal
606
left-to-right evaluation rules, but its @i{value} is ignored.
608
@subsubheading Examples::
611
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32206334>
612
(gethash 1 table) @result{} NIL, @i{false}
613
(gethash 1 table 2) @result{} 2, @i{false}
614
(setf (gethash 1 table) "one") @result{} "one"
615
(setf (gethash 2 table "two") "two") @result{} "two"
616
(gethash 1 table) @result{} "one", @i{true}
617
(gethash 2 table) @result{} "two", @i{true}
618
(gethash nil table) @result{} NIL, @i{false}
619
(setf (gethash nil table) nil) @result{} NIL
620
(gethash nil table) @result{} NIL, @i{true}
621
(defvar *counters* (make-hash-table)) @result{} *COUNTERS*
622
(gethash 'foo *counters*) @result{} NIL, @i{false}
623
(gethash 'foo *counters* 0) @result{} 0, @i{false}
624
(defmacro how-many (obj) `(values (gethash ,obj *counters* 0))) @result{} HOW-MANY
625
(defun count-it (obj) (incf (how-many obj))) @result{} COUNT-IT
626
(dolist (x '(bar foo foo bar bar baz)) (count-it x))
627
(how-many 'foo) @result{} 2
628
(how-many 'bar) @result{} 3
629
(how-many 'quux) @result{} 0
632
@subsubheading See Also::
636
@subsubheading Notes::
638
The @i{secondary value}, @i{present-p},
639
can be used to distinguish the absence of an entry
640
from the presence of an entry that has a value of @i{default}.
642
@node remhash, maphash, gethash, Hash Tables Dictionary
643
@subsection remhash [Function]
645
@code{remhash} @i{key hash-table} @result{} @i{generalized-boolean}
647
@subsubheading Arguments and Values::
649
@i{key}---an @i{object}.
651
@i{hash-table}---a @i{hash table}.
653
@i{generalized-boolean}---a @i{generalized boolean}.
655
@subsubheading Description::
657
Removes the entry for @i{key} in @i{hash-table}, if any.
658
Returns @i{true} if there was such an entry, or @i{false} otherwise.
660
@subsubheading Examples::
662
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32115666>
663
(setf (gethash 100 table) "C") @result{} "C"
664
(gethash 100 table) @result{} "C", @i{true}
665
(remhash 100 table) @result{} @i{true}
666
(gethash 100 table) @result{} NIL, @i{false}
667
(remhash 100 table) @result{} @i{false}
670
@subsubheading Side Effects::
672
The @i{hash-table} is modified.
674
@node maphash, with-hash-table-iterator, remhash, Hash Tables Dictionary
675
@subsection maphash [Function]
677
@code{maphash} @i{function hash-table} @result{} @i{@b{nil}}
679
@subsubheading Arguments and Values::
681
@i{function}---a @i{designator} for a @i{function} of two @i{arguments},
682
the @i{key} and the @i{value}.
684
@i{hash-table}---a @i{hash table}.
686
@subsubheading Description::
688
Iterates over all entries in the @i{hash-table}. For each entry,
689
the @i{function} is called with two @i{arguments}--the @i{key}
690
and the @i{value} of that entry.
692
The consequences are unspecified if any attempt is made to add or remove
693
an entry from the @i{hash-table} while a @b{maphash} is in progress,
695
the @i{function} can use can use @b{setf} of @b{gethash}
696
to change the @i{value} part of the entry currently being processed,
697
or it can use @b{remhash} to remove that entry.
699
@subsubheading Examples::
702
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32304110>
703
(dotimes (i 10) (setf (gethash i table) i)) @result{} NIL
704
(let ((sum-of-squares 0))
705
(maphash #'(lambda (key val)
706
(let ((square (* val val)))
707
(incf sum-of-squares square)
708
(setf (gethash key table) square)))
710
sum-of-squares) @result{} 285
711
(hash-table-count table) @result{} 10
712
(maphash #'(lambda (key val)
713
(when (oddp val) (remhash key table)))
715
(hash-table-count table) @result{} 5
716
(maphash #'(lambda (k v) (print (list k v))) table)
725
@subsubheading Side Effects::
727
None, other than any which might be done by the @i{function}.
729
@subsubheading See Also::
733
@ref{with-hash-table-iterator}
736
@ref{Traversal Rules and Side Effects}
738
@node with-hash-table-iterator, clrhash, maphash, Hash Tables Dictionary
739
@subsection with-hash-table-iterator [Macro]
741
@code{with-hash-table-iterator} @i{@r{(}name hash-table@r{)}
742
@{@i{declaration}@}* @{@i{form}@}*} @result{} @i{@{@i{result}@}*}
744
@subsubheading Arguments and Values::
746
@i{name}---a name suitable for the first argument to @b{macrolet}.
748
@i{hash-table}---a @i{form}, evaluated once, that should produce a @i{hash table}.
750
@i{declaration}---a @b{declare} @i{expression}; not evaluated.
752
@i{forms}---an @i{implicit progn}.
754
@i{results}---the @i{values} returned by @i{forms}.
756
@subsubheading Description::
758
Within the lexical scope of the body, @i{name} is defined via @b{macrolet}
759
such that successive invocations of @t{(@i{name})} return the items,
760
one by one, from the @i{hash table} that is obtained by evaluating
761
@i{hash-table} only once.
763
An invocation @t{(@i{name})} returns three values as follows:
768
A @i{generalized boolean} that is @i{true} if an entry is returned.
770
The key from the @i{hash-table} entry.
772
The value from the @i{hash-table} entry.
775
After all entries have been returned by successive invocations of
776
@t{(@i{name})}, then only one value is returned, namely @b{nil}.
778
It is unspecified what happens if any of the implicit interior state
779
of an iteration is returned outside the dynamic extent of the
780
@b{with-hash-table-iterator} @i{form}
781
such as by returning some @i{closure} over the invocation @i{form}.
783
Any number of invocations of @b{with-hash-table-iterator}
784
can be nested, and the body of the innermost one can invoke all of the
785
locally @i{established} @i{macros}, provided all of those @i{macros}
786
have @i{distinct} names.
788
@subsubheading Examples::
790
The following function should return @b{t} on any
791
@i{hash table}, and signal
792
an error if the usage of @b{with-hash-table-iterator} does not agree
793
with the corresponding usage of @b{maphash}.
796
(defun test-hash-table-iterator (hash-table)
797
(let ((all-entries '())
798
(generated-entries '())
800
(maphash #'(lambda (key value) (push (list key value) all-entries))
802
(with-hash-table-iterator (generator-fn hash-table)
804
(multiple-value-bind (more? key value) (generator-fn)
805
(unless more? (return))
806
(unless (eql value (gethash key hash-table unique))
807
(error "Key ~S not found for value ~S" key value))
808
(push (list key value) generated-entries))))
809
(unless (= (length all-entries)
810
(length generated-entries)
811
(length (union all-entries generated-entries
812
:key #'car :test (hash-table-test hash-table))))
813
(error "Generated entries and Maphash entries don't correspond"))
817
The following could be an acceptable definition of
818
@b{maphash}, implemented by @b{with-hash-table-iterator}.
821
(defun maphash (function hash-table)
822
(with-hash-table-iterator (next-entry hash-table)
823
(loop (multiple-value-bind (more key value) (next-entry)
824
(unless more (return nil))
825
(funcall function key value)))))
828
@subsubheading Exceptional Situations::
830
The consequences are undefined if the local function named @i{name}
831
@i{established} by @b{with-hash-table-iterator} is called after it has
832
returned @i{false} as its @i{primary value}.
834
@subsubheading See Also::
836
@ref{Traversal Rules and Side Effects}
838
@node clrhash, sxhash, with-hash-table-iterator, Hash Tables Dictionary
839
@subsection clrhash [Function]
841
@code{clrhash} @i{hash-table} @result{} @i{hash-table}
843
@subsubheading Arguments and Values::
845
@i{hash-table}---a @i{hash table}.
847
@subsubheading Description::
849
Removes all entries from @i{hash-table},
850
and then returns that empty @i{hash table}.
852
@subsubheading Examples::
855
(setq table (make-hash-table)) @result{} #<HASH-TABLE EQL 0/120 32004073>
856
(dotimes (i 100) (setf (gethash i table) (format nil "~R" i))) @result{} NIL
857
(hash-table-count table) @result{} 100
858
(gethash 57 table) @result{} "fifty-seven", @i{true}
859
(clrhash table) @result{} #<HASH-TABLE EQL 0/120 32004073>
860
(hash-table-count table) @result{} 0
861
(gethash 57 table) @result{} NIL, @i{false}
864
@subsubheading Side Effects::
866
The @i{hash-table} is modified.
868
@node sxhash, , clrhash, Hash Tables Dictionary
869
@subsection sxhash [Function]
871
@code{sxhash} @i{object} @result{} @i{hash-code}
873
@subsubheading Arguments and Values::
875
@i{object}---an @i{object}.
877
@i{hash-code}---a non-negative @i{fixnum}.
879
@subsubheading Description::
881
@b{sxhash} returns a hash code for @i{object}.
883
The manner in which the hash code is computed is @i{implementation-dependent},
884
but subject to certain constraints:
889
@t{(equal @i{x} @i{y})} implies @t{(= (sxhash @i{x}) (sxhash @i{y}))}.
892
For any two @i{objects}, @i{x} and @i{y},
901
and which are @i{similar},
902
@t{(sxhash @i{x})} and @t{(sxhash @i{y})}
903
@i{yield} the same mathematical value
904
even if @i{x} and @i{y} exist in different @i{Lisp images} of
905
the same @i{implementation}.
906
See @ref{Literal Objects in Compiled Files}.
909
The @i{hash-code} for an @i{object} is always the @i{same}
910
within a single @i{session} provided that the @i{object} is not
911
visibly modified with regard to the equivalence test @b{equal}.
912
See @ref{Modifying Hash Table Keys}.
915
The @i{hash-code} is intended for hashing. This places no verifiable
916
constraint on a @i{conforming implementation}, but the intent is that
917
an @i{implementation} should make a good-faith effort to produce
918
@i{hash-codes} that are well distributed within the range of
919
non-negative @i{fixnums}.
922
Computation of the @i{hash-code} must terminate,
923
even if the @i{object} contains circularities.
926
@subsubheading Examples::
929
(= (sxhash (list 'list "ab")) (sxhash (list 'list "ab"))) @result{} @i{true}
930
(= (sxhash "a") (sxhash (make-string 1 :initial-element #\a))) @result{} @i{true}
931
(let ((r (make-random-state)))
932
(= (sxhash r) (sxhash (make-random-state r))))
933
@result{} @i{implementation-dependent}
936
@subsubheading Affected By::
938
The @i{implementation}.
940
@subsubheading Notes::
942
Many common hashing needs are satisfied by @b{make-hash-table} and the
943
related functions on @i{hash tables}. @b{sxhash} is intended for use
944
where the pre-defined abstractions are insufficient. Its main intent is to
945
allow the user a convenient means of implementing more complicated hashing
946
paradigms than are provided through @i{hash tables}.
948
The hash codes returned by @b{sxhash} are not necessarily related to
949
any hashing strategy used by any other @i{function} in @r{Common Lisp}.
951
For @i{objects} of @i{types} that @b{equal} compares
952
with @b{eq}, item 3 requires that the @i{hash-code} be
953
based on some immutable quality of the identity of the object.
954
Another legitimate implementation technique would be to have
955
@b{sxhash} assign (and cache) a random hash code for these
956
@i{objects}, since there is no requirement that @i{similar} but
957
non-@b{eq} objects have the same hash code.
959
Although @i{similarity} is defined for @i{symbols} in terms
960
of both the @i{symbol}'s @i{name} and the @i{packages} in which
961
the @i{symbol} is @i{accessible}, item 3 disallows using @i{package}
962
information to compute the hash code, since changes to the package status
963
of a symbol are not visible to @i{equal}.
965
@c end of including dict-hash-tables
added
removed
info/chap-18.texi
