File: chap-18.texi

package info (click to toggle)
gclinfo 2.2-9
  • links: PTS
  • area: main
  • in suites: potato
  • size: 3,928 kB
  • ctags: 15
  • sloc: sed: 1,681; makefile: 127; lisp: 58; sh: 40
file content (966 lines) | stat: -rw-r--r-- 33,759 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966


@node Hash Tables, Filenames, Sequences, Top
@chapter Hash Tables

@menu
* Hash Table Concepts::		
* Hash Tables Dictionary::	
@end menu

@node Hash Table Concepts, Hash Tables Dictionary, Hash Tables, Hash Tables
@section Hash Table Concepts

@c including concept-hash-tables

@menu
* Hash-Table Operations::	
* Modifying Hash Table Keys::	
@end menu

@node Hash-Table Operations, Modifying Hash Table Keys, Hash Table Concepts, Hash Table Concepts
@subsection Hash-Table Operations

Figure 18--1 lists some @i{defined names} that are applicable 
to @i{hash tables}.  The following rules apply to @i{hash tables}.

@table @asis

@item --  
A @i{hash table} can only associate one value with a given
key. If an attempt is made to add a second value for a given key,
the second value will replace the first.
Thus, adding a value to a @i{hash table} is a destructive operation;
the @i{hash table} is modified.  

@item --  
There are four kinds of @i{hash tables}:
  those whose keys are compared with @b{eq},
  those whose keys are compared with @b{eql},
  those whose keys are compared with @b{equal}, and

  those whose keys are compared with @b{equalp}.  

@item --  
@i{Hash tables} are created by @b{make-hash-table}. 
@b{gethash} is used to look up a key and find the associated value.
New entries are added to @i{hash tables} using @b{setf} with @b{gethash}.
@b{remhash} is used to remove an entry.
For example:

@example
 (setq a (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32536573>
 (setf (gethash 'color a) 'brown) @result{}  BROWN
 (setf (gethash 'name a) 'fred) @result{}  FRED
 (gethash 'color a) @result{}  BROWN, @i{true}
 (gethash 'name a) @result{}  FRED, @i{true}
 (gethash 'pointy a) @result{}  NIL, @i{false}
@end example

In this example, the symbols @t{color} and @t{name} are being used as
keys, and the symbols @t{brown} and @t{fred} are being used as the
associated values.  The @i{hash table} 
has two items in it, one of which                              
associates from @t{color} to @t{brown}, and the other of which
associates from @t{name} to @t{fred}.

@item --  
A key or a value may be any @i{object}.

@item --  
The existence of an entry in the @i{hash table} can be determined
from the @i{secondary value} returned by @b{gethash}.
@end table

@group
@noindent
@w{  clrhash           hash-table-p     remhash  }
@w{  gethash           make-hash-table  sxhash   }
@w{  hash-table-count  maphash                   }

@noindent
@w{     Figure 18--1: Hash-table defined names   }

@end group

@node Modifying Hash Table Keys,  , Hash-Table Operations, Hash Table Concepts
@subsection Modifying Hash Table Keys

The function supplied as the @t{:test} argument to @b{make-hash-table}
specifies the `equivalence test' for the @i{hash table} it creates.

An @i{object} is `visibly modified' with regard to an equivalence test
if there exists some set of @i{objects} (or potential @i{objects})
which are equivalent to the @i{object} before the modification but are
no longer equivalent afterwards.

If an @i{object} O_1 is used as a key in a @i{hash table} H
and is then visibly modified with regard to the equivalence test of H,
then the consequences are unspecified if O_1, or any @i{object}
O_2 equivalent to O_1 under the equivalence test (either before
or after the modification), is used as a key in further operations on H.
The consequences of using O_1 as a key are unspecified 
even if O_1 is visibly modified 
and then later modified again in such a way as 
to undo the visible modification.

Following are specifications of the modifications which are visible to the
equivalence tests which must be supported by @i{hash tables}.  The modifications
are described in terms of modification of components, and are defined
recursively.  Visible modifications of components of the @i{object} are 
visible modifications of the @i{object}.

@menu
* Visible Modification of Objects with respect to EQ and EQL::	
* Visible Modification of Objects with respect to EQUAL::  
* 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 EQUALP::  
* Visible Modification of Structures with respect to EQUALP::  
* Visible Modification of Arrays with respect to EQUALP::  
* Visible Modification of Hash Tables with respect to EQUALP::	
* Visible Modifications by Language Extensions::  
@end menu

@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
@subsubsection Visible Modification of Objects with respect to EQ and EQL

No @i{standardized} @i{function} is provided that is capable of visibly
modifying an @i{object} with regard to @b{eq} or @b{eql}.

@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
@subsubsection Visible Modification of Objects with respect to EQUAL

As a consequence of the behavior for @b{equal},
the rules for visible modification of @i{objects} not explicitly mentioned in this
section are inherited from those in @ref{Visible Modification of Objects with respect to EQ and EQL}.

@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
@subsubsection Visible Modification of Conses with respect to EQUAL

Any visible change to the @i{car} or the @i{cdr} of a @i{cons}
is considered a visible modification with regard to @b{equal}.

@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
@subsubsection Visible Modification of Bit Vectors and Strings with respect to EQUAL

For a @i{vector} of @i{type} @b{bit-vector} or of @i{type} @b{string}, any visible change
     to an @i{active} @i{element} of the @i{vector},
  or to the @i{length} of the @i{vector} (if it is @i{actually adjustable} 
					           or has a @i{fill pointer})
is considered a visible modification with regard to @b{equal}.

@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
@subsubsection Visible Modification of Objects with respect to EQUALP

As a consequence of the behavior for @b{equalp},
the rules for visible modification of @i{objects} not explicitly mentioned in this
section are inherited from those in @ref{Visible Modification of Objects with respect to EQUAL}.

@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
@subsubsection Visible Modification of Structures with respect to EQUALP

Any visible change to a @i{slot} of a @i{structure}
is considered a visible modification with regard to @b{equalp}.

@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
@subsubsection Visible Modification of Arrays with respect to EQUALP

In an @i{array}, any visible change
     to an @i{active} @i{element},
     to the @i{fill pointer} (if the @i{array} can and does have one),
  or to the @i{dimensions} (if the @i{array} is @i{actually adjustable})
is considered a visible modification with regard to @b{equalp}.

@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
@subsubsection Visible Modification of Hash Tables with respect to EQUALP

In a @i{hash table}, any visible change
     to the count of entries in the @i{hash table},
     to the keys,
  or to the values associated with the keys
is considered a visible modification with regard to @b{equalp}.

Note that the visibility of modifications to the keys depends on the equivalence test
of the @i{hash table}, not on the specification of @b{equalp}.

@node Visible Modifications by Language Extensions,  , Visible Modification of Hash Tables with respect to EQUALP, Modifying Hash Table Keys
@subsubsection Visible Modifications by Language Extensions

@i{Implementations} that extend the language by providing additional mutator
functions (or additional behavior for existing mutator functions) must
document how the use of these extensions interacts with equivalence tests and
@i{hash table} searches.

@i{Implementations} that extend the language by defining additional acceptable
equivalence tests for @i{hash tables} (allowing additional values for the @t{:test}
argument to @b{make-hash-table}) must document the visible components of these
tests.

@c end of including concept-hash-tables

@node Hash Tables Dictionary,  , Hash Table Concepts, Hash Tables
@section Hash Tables Dictionary

@c including dict-hash-tables

@menu
* hash-table::			
* make-hash-table::		
* hash-table-p::		
* hash-table-count::		
* hash-table-rehash-size::	
* hash-table-rehash-threshold::	 
* hash-table-size::		
* hash-table-test::		
* gethash::			
* remhash::			
* maphash::			
* with-hash-table-iterator::	
* clrhash::			
* sxhash::			
@end menu

@node hash-table, make-hash-table, Hash Tables Dictionary, Hash Tables Dictionary
@subsection hash-table                                                   [System Class]

@subsubheading  Class Precedence List::
@b{hash-table},
@b{t}

@subsubheading  Description::

@i{Hash tables} provide a way of mapping any @i{object} (a @i{key})
to an associated @i{object} (a @i{value}).

@subsubheading  See Also::

@ref{Hash Table Concepts},
@ref{Printing Other Objects}

@subsubheading  Notes::

The intent is that this mapping be implemented by a hashing mechanism,
such as that described in Section 6.4 ``Hashing'' of {The Art of Computer Programming, Volume 3}
(pp506-549).  In spite of this intent, no @i{conforming implementation} 
is required to use any particular technique to implement the mapping.

@node make-hash-table, hash-table-p, hash-table, Hash Tables Dictionary
@subsection make-hash-table                                                  [Function]

@code{make-hash-table}  @i{{&key} test size rehash-size rehash-threshold} @result{}  @i{hash-table}

@subsubheading  Arguments and Values::

@i{test}---a @i{designator} for one of the @i{functions}
	       @b{eq},
	       @b{eql},
	       @b{equal}, or

	       @b{equalp}.

  The default is @b{eql}.

@i{size}---a non-negative @i{integer}.

  The default is @i{implementation-dependent}.

@i{rehash-size}---a @i{real} of @i{type} @t{(or (integer 1 *) (float (1.0) *))}.
  The default is @i{implementation-dependent}.

@i{rehash-threshold}---a @i{real} of @i{type} @t{(real 0 1)}.
  The default is @i{implementation-dependent}.

@i{hash-table}---a @i{hash table}.

@subsubheading  Description::

Creates and returns a new @i{hash table}.

@i{test} determines how @i{keys} are compared.
An @i{object} is said to be present in the @i{hash-table}
if that @i{object} is the @i{same} under the @i{test} 
as the @i{key} for some entry in the @i{hash-table}.

@i{size} is a hint to the @i{implementation} about how much initial space
to allocate in the @i{hash-table}.

This information, taken together with the @i{rehash-threshold}, controls
the approximate number of entries which it should be possible
to insert before the table has to grow.

The actual size might be rounded up from @i{size} to the next `good' size;
for example, some @i{implementations} might round to the next prime number.

@i{rehash-size} specifies a minimum amount to increase the size of the 
@i{hash-table} when it becomes full
enough to require rehashing; 
see @i{rehash-theshold} below.

If @i{rehash-size} is an @i{integer},
the expected growth rate for the table is additive and
the @i{integer} is the number of entries to add;
if it is a @i{float},
the expected growth rate for the table is multiplicative and
the @i{float} is the ratio of the new size to the old size.

As with @i{size}, the actual size of the increase might be rounded up.

@i{rehash-threshold} specifies how full the @i{hash-table} can get 
before it must grow.

It specifies the maximum desired hash-table occupancy level.

The @i{values} of @i{rehash-size} and @i{rehash-threshold} do not constrain the
@i{implementation} to use any particular method for computing when and by how much
the size of @i{hash-table} should be enlarged.  Such decisions are   
@i{implementation-dependent}, and these @i{values} only hints
from the @i{programmer} to the @i{implementation}, and the @i{implementation}
is permitted to ignore them.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 46142754>
 (setf (gethash "one" table) 1) @result{}  1
 (gethash "one" table) @result{}  NIL, @i{false}
 (setq table (make-hash-table :test 'equal)) @result{}  #<HASH-TABLE EQUAL 0/139 46145547>
 (setf (gethash "one" table) 1) @result{}  1
 (gethash "one" table) @result{}  1, T
 (make-hash-table :rehash-size 1.5 :rehash-threshold 0.7) 
@result{}  #<HASH-TABLE EQL 0/120 46156620>
@end example

@subsubheading  See Also::

@ref{gethash}
,
@b{hash-table}

@node hash-table-p, hash-table-count, make-hash-table, Hash Tables Dictionary
@subsection hash-table-p                                                     [Function]

@code{hash-table-p}  @i{object} @result{}  @i{generalized-boolean}

@subsubheading  Arguments and Values::

@i{object}---an @i{object}.

@i{generalized-boolean}---a @i{generalized boolean}.

@subsubheading  Description::

Returns @i{true} if @i{object} is of @i{type} @b{hash-table};
otherwise, returns @i{false}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32511220>
 (hash-table-p table) @result{}  @i{true}
 (hash-table-p 37) @result{}  @i{false}
 (hash-table-p '((a . 1) (b . 2))) @result{}  @i{false}
@end example

@subsubheading  Notes::

@example
 (hash-table-p @i{object}) @equiv{} (typep @i{object} 'hash-table)
@end example

@node hash-table-count, hash-table-rehash-size, hash-table-p, Hash Tables Dictionary
@subsection hash-table-count                                                 [Function]

@code{hash-table-count}  @i{hash-table} @result{}  @i{count}

@subsubheading  Arguments and Values::

@i{hash-table}---a @i{hash table}.

@i{count}---a non-negative @i{integer}.

@subsubheading  Description::

Returns the number of entries in the @i{hash-table}.
If @i{hash-table} has just been created 
or newly cleared (see @b{clrhash})
the entry count is @t{0}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32115135>
 (hash-table-count table) @result{}  0
 (setf (gethash 57 table) "fifty-seven") @result{}  "fifty-seven"
 (hash-table-count table) @result{}  1
 (dotimes (i 100) (setf (gethash i table) i)) @result{}  NIL
 (hash-table-count table) @result{}  100
@end example

@subsubheading  Affected By::

@b{clrhash},
@b{remhash},
@b{setf} of @b{gethash}

@subsubheading  See Also::

@ref{hash-table-size}

@subsubheading  Notes::

The following relationships are functionally correct, although in practice
using @b{hash-table-count} is probably much faster:

@example
 (hash-table-count @i{table}) @equiv{}
 (loop for value being the hash-values of @i{table} count t) @equiv{}
 (let ((total 0))
   (maphash #'(lambda (key value)
                (declare (ignore key value))
                (incf total))
            @i{table})
   total)
@end example

@node hash-table-rehash-size, hash-table-rehash-threshold, hash-table-count, Hash Tables Dictionary
@subsection hash-table-rehash-size                                           [Function]

@code{hash-table-rehash-size}  @i{hash-table} @result{}  @i{rehash-size}

@subsubheading  Arguments and Values:: 

@i{hash-table}---a @i{hash table}.

@i{rehash-size}---a @i{real} of @i{type} @t{(or (integer 1 *) (float (1.0) *))}.

@subsubheading  Description::

Returns the current rehash size of @i{hash-table},
suitable for use in a call to @b{make-hash-table} 
in order to produce a @i{hash table} 
with state corresponding to the current state of the @i{hash-table}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table :size 100 :rehash-size 1.4))
@result{}  #<HASH-TABLE EQL 0/100 2556371>
 (hash-table-rehash-size table) @result{}  1.4
@end example

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{make-hash-table}
,
@ref{hash-table-rehash-threshold}

@subsubheading  Notes::

If the hash table was created with an @i{integer} rehash size,
the result is an @i{integer},
indicating that the rate of growth of the @i{hash-table} when rehashed
is intended to be additive;
otherwise,
the result is a @i{float}, 
indicating that the rate of growth of the @i{hash-table} when rehashed
is intended to be multiplicative.
However, this value is only advice to the @i{implementation};
the actual amount by which the @i{hash-table} will grow upon rehash is
@i{implementation-dependent}.

@node hash-table-rehash-threshold, hash-table-size, hash-table-rehash-size, Hash Tables Dictionary
@subsection hash-table-rehash-threshold                                      [Function]

@code{hash-table-rehash-threshold}  @i{hash-table} @result{}  @i{rehash-threshold}

@subsubheading  Arguments and Values::

@i{hash-table}---a @i{hash table}.

@i{rehash-threshold}---a @i{real} of @i{type} @t{(real 0 1)}.

@subsubheading  Description::

Returns the current rehash threshold of @i{hash-table}, which is
suitable for use in a call to @b{make-hash-table} in order to
produce a @i{hash table} with state corresponding to the current 
state of the @i{hash-table}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table :size 100 :rehash-threshold 0.5))
@result{}  #<HASH-TABLE EQL 0/100 2562446>
 (hash-table-rehash-threshold table) @result{}  0.5
@end example

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{make-hash-table}
,
@ref{hash-table-rehash-size}

@node hash-table-size, hash-table-test, hash-table-rehash-threshold, Hash Tables Dictionary
@subsection hash-table-size                                                  [Function]

@code{hash-table-size}  @i{hash-table} @result{}  @i{size}

@subsubheading  Arguments and Values:: 

@i{hash-table}---a @i{hash table}.

@i{size}---a non-negative @i{integer}.

@subsubheading  Description::

Returns the current size of @i{hash-table}, which is suitable for use in
a call to @b{make-hash-table} in order to produce a @i{hash table} 
with state corresponding to the current state of the @i{hash-table}.

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{hash-table-count}
,
@ref{make-hash-table}

@node hash-table-test, gethash, hash-table-size, Hash Tables Dictionary
@subsection hash-table-test                                                  [Function]

@code{hash-table-test}  @i{hash-table} @result{}  @i{test}

@subsubheading  Arguments and Values::

@i{hash-table}---a @i{hash table}.

@i{test}---a @i{function designator}.
 For the four @i{standardized} @i{hash table} test @i{functions}
 (see @b{make-hash-table}), the @i{test} value returned
 is always a @i{symbol}.  If an @i{implementation} permits additional 
 tests, it is @i{implementation-dependent} whether such tests are
 returned as @i{function} @i{objects} or @i{function names}.

@subsubheading  Description::

Returns the test used for comparing @i{keys} in @i{hash-table}.

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{make-hash-table}

@node gethash, remhash, hash-table-test, Hash Tables Dictionary
@subsection gethash                                                          [Accessor]

@code{gethash}  @i{key hash-table {&optional} default} @result{}  @i{value, present-p}

(setf (@code{         gethash} @i{key hash-table {&optional} default}) new-value)@*

@subsubheading  Arguments and Values::

@i{key}---an @i{object}.

@i{hash-table}---a @i{hash table}.

@i{default}---an @i{object}.
 The default is @b{nil}.

@i{value}---an @i{object}.

@i{present-p}---a @i{generalized boolean}.

@subsubheading  Description::

@i{Value} is the @i{object} in @i{hash-table} whose @i{key} 
is the @i{same} as @i{key} under the @i{hash-table}'s equivalence test.
If there is no such entry, @i{value} is the @i{default}.

@i{Present-p} is @i{true} if an entry is found; otherwise, it is @i{false}.

@b{setf} may be used with @b{gethash} to modify the @i{value}
associated with a given @i{key}, or to add a new entry.

When a @b{gethash} @i{form} is used as a @b{setf} @i{place},
any @i{default} which is supplied is evaluated according to normal
left-to-right evaluation rules, but its @i{value} is ignored.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32206334>
 (gethash 1 table) @result{}  NIL, @i{false}
 (gethash 1 table 2) @result{}  2, @i{false}
 (setf (gethash 1 table) "one") @result{}  "one"
 (setf (gethash 2 table "two") "two") @result{}  "two"
 (gethash 1 table) @result{}  "one", @i{true}
 (gethash 2 table) @result{}  "two", @i{true}
 (gethash nil table) @result{}  NIL, @i{false}
 (setf (gethash nil table) nil) @result{}  NIL 
 (gethash nil table) @result{}  NIL, @i{true}
 (defvar *counters* (make-hash-table)) @result{}  *COUNTERS*
 (gethash 'foo *counters*) @result{}  NIL, @i{false}
 (gethash 'foo *counters* 0) @result{}  0, @i{false}
 (defmacro how-many (obj) `(values (gethash ,obj *counters* 0))) @result{}  HOW-MANY
 (defun count-it (obj) (incf (how-many obj))) @result{}  COUNT-IT
 (dolist (x '(bar foo foo bar bar baz)) (count-it x))
 (how-many 'foo) @result{}  2
 (how-many 'bar) @result{}  3
 (how-many 'quux) @result{}  0
@end example

@subsubheading  See Also::

@ref{remhash}

@subsubheading  Notes::

The @i{secondary value}, @i{present-p},
can be used to distinguish the absence of an entry
from the presence of an entry that has a value of @i{default}.

@node remhash, maphash, gethash, Hash Tables Dictionary
@subsection remhash                                                          [Function]

@code{remhash}  @i{key hash-table} @result{}  @i{generalized-boolean}

@subsubheading  Arguments and Values:: 

@i{key}---an @i{object}.

@i{hash-table}---a @i{hash table}.

@i{generalized-boolean}---a @i{generalized boolean}.

@subsubheading  Description::

Removes the entry for @i{key} in @i{hash-table}, if any.
Returns @i{true} if there was such an entry, or @i{false} otherwise.

@subsubheading  Examples::
@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32115666>
 (setf (gethash 100 table) "C") @result{}  "C"
 (gethash 100 table) @result{}  "C", @i{true}
 (remhash 100 table) @result{}  @i{true}
 (gethash 100 table) @result{}  NIL, @i{false}
 (remhash 100 table) @result{}  @i{false}
@end example

@subsubheading  Side Effects::

The @i{hash-table} is modified.

@node maphash, with-hash-table-iterator, remhash, Hash Tables Dictionary
@subsection maphash                                                          [Function]

@code{maphash}  @i{function hash-table} @result{}  @i{@b{nil}}

@subsubheading  Arguments and Values::

@i{function}---a @i{designator} for a @i{function} of two @i{arguments},
		     the @i{key} and the @i{value}.

@i{hash-table}---a @i{hash table}.

@subsubheading  Description::

Iterates over all entries in the @i{hash-table}.  For each entry,
the @i{function} is called with two @i{arguments}--the @i{key} 
and the @i{value} of that entry.

The consequences are unspecified if any attempt is made to add or remove
an entry from the @i{hash-table} while a @b{maphash} is in progress,
with two exceptions:
   the @i{function} can use can use @b{setf} of @b{gethash}
   to change the @i{value} part of the entry currently being processed, 
or it can use @b{remhash} to remove that entry.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32304110>
 (dotimes (i 10) (setf (gethash i table) i)) @result{}  NIL
 (let ((sum-of-squares 0))
    (maphash #'(lambda (key val) 
                 (let ((square (* val val)))
                   (incf sum-of-squares square)
                   (setf (gethash key table) square)))
             table)
    sum-of-squares) @result{}  285
 (hash-table-count table) @result{}  10
 (maphash #'(lambda (key val)
               (when (oddp val) (remhash key table)))
           table) @result{}  NIL
 (hash-table-count table) @result{}  5
 (maphash #'(lambda (k v) (print (list k v))) table)
(0 0) 
(8 64) 
(2 4) 
(6 36) 
(4 16) 
@result{}  NIL
@end example

@subsubheading  Side Effects::

None, other than any which might be done by the @i{function}.

@subsubheading  See Also::

@ref{loop}
,
@ref{with-hash-table-iterator}
,

@ref{Traversal Rules and Side Effects}

@node with-hash-table-iterator, clrhash, maphash, Hash Tables Dictionary
@subsection with-hash-table-iterator                                            [Macro]

@code{with-hash-table-iterator}  @i{@r{(}name hash-table@r{)} 
	           @{@i{declaration}@}{*} @{@i{form}@}{*}} @result{}  @i{@{@i{result}@}{*}}

@subsubheading  Arguments and Values::

@i{name}---a name suitable for the first argument to @b{macrolet}.

@i{hash-table}---a @i{form}, evaluated once, that should produce a @i{hash table}.

@i{declaration}---a @b{declare} @i{expression}; not evaluated.

@i{forms}---an @i{implicit progn}.

@i{results}---the @i{values} returned by @i{forms}.

@subsubheading  Description::

Within the lexical scope of the body, @i{name} is defined via @b{macrolet} 
such that successive invocations of @t{(@i{name})} return the items,
one by one, from the @i{hash table} that is obtained by evaluating
@i{hash-table} only once.

An invocation @t{(@i{name})} returns three values as follows:

@table @asis

@item 1.  
A @i{generalized boolean} that is @i{true} if an entry is returned.
@item 2.  
The key from the @i{hash-table} entry.
@item 3.  
The value from the @i{hash-table} entry.
@end table

After all entries have been returned by successive invocations of
@t{(@i{name})}, then only one value is returned, namely @b{nil}.

It is unspecified what happens if any of the implicit interior state 
of an iteration is returned outside the dynamic extent of the 
@b{with-hash-table-iterator} @i{form}
such as by returning some @i{closure} over the invocation @i{form}.

Any number of invocations of @b{with-hash-table-iterator} 
can be nested, and the body of the innermost one can invoke all of the
locally @i{established} @i{macros}, provided all of those @i{macros}
have @i{distinct} names.

@subsubheading  Examples::

The following function should return @b{t} on any 
@i{hash table}, and signal
an error if the usage of @b{with-hash-table-iterator} does not agree
with the corresponding usage of @b{maphash}.

@example
 (defun test-hash-table-iterator (hash-table)
   (let ((all-entries '())
         (generated-entries '())
         (unique (list nil)))
     (maphash #'(lambda (key value) (push (list key value) all-entries))
              hash-table)
     (with-hash-table-iterator (generator-fn hash-table)
       (loop     
         (multiple-value-bind (more? key value) (generator-fn)
           (unless more? (return))
           (unless (eql value (gethash key hash-table unique))
             (error "Key ~S not found for value ~S" key value))
           (push (list key value) generated-entries))))
     (unless (= (length all-entries)
                (length generated-entries)
                (length (union all-entries generated-entries
                               :key #'car :test (hash-table-test hash-table))))
       (error "Generated entries and Maphash entries don't correspond"))
     t))
@end example

The following could be an acceptable definition of 
@b{maphash}, implemented by @b{with-hash-table-iterator}.

@example
 (defun maphash (function hash-table)
   (with-hash-table-iterator (next-entry hash-table)
     (loop (multiple-value-bind (more key value) (next-entry)
             (unless more (return nil))
             (funcall function key value)))))
@end example

@subsubheading  Exceptional Situations::

The consequences are undefined if the local function named @i{name}
@i{established} by @b{with-hash-table-iterator} is called after it has
returned @i{false} as its @i{primary value}.

@subsubheading  See Also::

@ref{Traversal Rules and Side Effects}

@node clrhash, sxhash, with-hash-table-iterator, Hash Tables Dictionary
@subsection clrhash                                                          [Function]

@code{clrhash}  @i{hash-table} @result{}  @i{hash-table}

@subsubheading  Arguments and Values:: 

@i{hash-table}---a @i{hash table}.

@subsubheading  Description::

Removes all entries from @i{hash-table},
and then returns that empty @i{hash table}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32004073>
 (dotimes (i 100) (setf (gethash i table) (format nil "~R" i))) @result{}  NIL
 (hash-table-count table) @result{}  100
 (gethash 57 table) @result{}  "fifty-seven", @i{true}
 (clrhash table) @result{}  #<HASH-TABLE EQL 0/120 32004073>
 (hash-table-count table) @result{}  0
 (gethash 57 table) @result{}  NIL, @i{false}
@end example

@subsubheading  Side Effects::

The @i{hash-table} is modified.

@node sxhash,  , clrhash, Hash Tables Dictionary
@subsection sxhash                                                           [Function]

@code{sxhash}  @i{object} @result{}  @i{hash-code}

@subsubheading  Arguments and Values::

@i{object}---an @i{object}.

@i{hash-code}---a non-negative @i{fixnum}.

@subsubheading  Description::

@b{sxhash} returns a hash code for @i{object}. 

The manner in which the hash code is computed is @i{implementation-dependent},
but subject to certain constraints:

@table @asis

@item 1.  
@t{(equal @i{x} @i{y})} implies @t{(= (sxhash @i{x}) (sxhash @i{y}))}.

@item 2.  
For any two @i{objects}, @i{x} and @i{y},
       both of which are 
          @i{bit vectors},
          @i{characters}, 
          @i{conses},
          @i{numbers},
          @i{pathnames},
          @i{strings},
       or @i{symbols},
   and which are @i{similar},
   @t{(sxhash @i{x})} and @t{(sxhash @i{y})}
   @i{yield} the same mathematical value 
   even if @i{x} and @i{y} exist in different @i{Lisp images} of
   the same @i{implementation}.
   See @ref{Literal Objects in Compiled Files}.

@item 3.  
The @i{hash-code} for an @i{object} is always the @i{same}
  within a single @i{session} provided that the @i{object} is not
  visibly modified with regard to the equivalence test @b{equal}.
  See @ref{Modifying Hash Table Keys}.

@item 4.  
The @i{hash-code} is intended for hashing.  This places no verifiable
  constraint on a @i{conforming implementation}, but the intent is that
  an @i{implementation} should make a good-faith effort to produce
  @i{hash-codes} that are well distributed within the range of
  non-negative @i{fixnums}.

@item 5.  
Computation of the @i{hash-code} must terminate, 
  even if the @i{object} contains circularities.  
@end table

@subsubheading  Examples::

@example
 (= (sxhash (list 'list "ab")) (sxhash (list 'list "ab"))) @result{}  @i{true}
 (= (sxhash "a") (sxhash (make-string 1 :initial-element #\a))) @result{}  @i{true}
 (let ((r (make-random-state)))
   (= (sxhash r) (sxhash (make-random-state r))))
@result{}  @i{implementation-dependent}
@end example

@subsubheading  Affected By::

The @i{implementation}.

@subsubheading  Notes::

Many common hashing needs are satisfied by @b{make-hash-table} and the
related functions on @i{hash tables}.  @b{sxhash} is intended for use
where the pre-defined abstractions are insufficient.  Its main intent is to
allow the user a convenient means of implementing more complicated hashing
paradigms than are provided through @i{hash tables}.

The hash codes returned by @b{sxhash} are not necessarily related to 
any hashing strategy used by any other @i{function} in @r{Common Lisp}.

For @i{objects} of @i{types} that @b{equal} compares 
with @b{eq}, item 3 requires that the @i{hash-code} be
based on some immutable quality of the identity of the object.
Another legitimate implementation technique would be to have 
@b{sxhash} assign (and cache) a random hash code for these
@i{objects}, since there is no requirement that @i{similar} but
non-@b{eq} objects have the same hash code.

Although @i{similarity} is defined for @i{symbols} in terms
of both the @i{symbol}'s @i{name} and the @i{packages} in which 
the @i{symbol} is @i{accessible}, item 3 disallows using @i{package}
information to compute the hash code, since changes to the package status 
of a symbol are not visible to @i{equal}.

@c end of including dict-hash-tables

@c %**end of chapter