[559513]: impnotes / hash-dict.html Maximize Restore History

Download this file

hash-dict.html    134 lines (133 with data), 31.4 kB

  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
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>18.1. The Hash Tables Dictionary
[CLHS-18.2]</title><link rel="stylesheet" href="impnotes.css" type="text/css" /><link rev="made" href="mailto:clisp-list@lists.sourceforge.net" /><meta name="generator" content="DocBook XSL Stylesheets V2005-10-07_10:16_snapshot" /><link rel="start" href="index.html" title="Implementation Notes for GNU CLISP" /><link rel="up" href="hash.html" title="Chapter 18. Hash Tables&#10; [CLHS-18]" /><link rel="prev" href="hash.html" title="Chapter 18. Hash Tables&#10; [CLHS-18]" /><link rel="next" href="filenames.html" title="Chapter 19. Filenames&#10; [CLHS-19]" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">18.1. The Hash Tables Dictionary
[CLHS-18.2]</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="hash.html">Prev</a> </td><th width="60%" align="center">Chapter 18. Hash Tables
[CLHS-18]</th><td width="20%" align="right"> <a accesskey="n" href="filenames.html">Next</a></td></tr></table><hr /></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="hash-dict"></a>18.1. The Hash Tables Dictionary
<a href="http://www.lisp.org/HyperSpec/Body/sec_the_hash__s_dictionary.html" target="_top">[CLHS-18.2]</a></h2></div></div></div><div class="toc"><dl><dt><span class="section"><a href="hash-dict.html#make-hash">18.1.1. Function <code class="function">MAKE-HASH-TABLE</code></a></span></dt><dd><dl><dt><span class="section"><a href="hash-dict.html#hashtable-gc-rehash">18.1.1.1. Interaction between <code class="classname">HASH-TABLE</code>s and garbage-collection</a></span></dt></dl></dd><dt><span class="section"><a href="hash-dict.html#defhash">18.1.2. Macro <code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a></span></dt><dt><span class="section"><a href="hash-dict.html#ht-test">18.1.3. Function <code class="function">HASH-TABLE-TEST</code></a></span></dt><dt><span class="section"><a href="hash-dict.html#dohash">18.1.4. Macro <code class="function">EXT:DOHASH</code></a></span></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="make-hash"></a>18.1.1. Function <a href="http://www.lisp.org/HyperSpec/Body/fun_make-hash-table.html" target="_top"><code class="function">MAKE-HASH-TABLE</code></a></h3></div></div></div><div class="toc"><dl><dt><span class="section"><a href="hash-dict.html#hashtable-gc-rehash">18.1.1.1. Interaction between <code class="classname">HASH-TABLE</code>s and garbage-collection</a></span></dt></dl></div><p><a href="http://www.lisp.org/HyperSpec/Body/fun_make-hash-table.html" target="_top"><code class="function">MAKE-HASH-TABLE</code></a> accepts two additional keyword arguments
<code class="constant">:INITIAL-CONTENTS</code> and <code class="constant">:WEAK</code>:</p><pre class="programlisting">
(<a href="http://www.lisp.org/HyperSpec/Body/fun_make-hash-table.html" target="_top"><code class="function">MAKE-HASH-TABLE</code></a> <a href="http://www.lisp.org/HyperSpec/Body/sec_3-4-1.html" target="_top"><code class="literal">&amp;KEY</code></a> :TEST :INITIAL-CONTENTS :SIZE
:REHASH-SIZE :REHASH-THRESHOLD
:WARN-IF-NEEDS-REHASH-AFTER-GC :WEAK)
</pre><p>The <code class="constant">:TEST</code> argument can be, other than one of the symbols <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a>,
<a href="http://www.lisp.org/HyperSpec/Body/fun_eql.html" target="_top"><code class="function">EQL</code></a>, <a href="http://www.lisp.org/HyperSpec/Body/fun_equal.html" target="_top"><code class="function">EQUAL</code></a>, <a href="http://www.lisp.org/HyperSpec/Body/fun_equalp.html" target="_top"><code class="function">EQUALP</code></a>, one of the symbols <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a> and
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>. Both of these tests use <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a> as the comparison
function; they differ in their performance characteristics.
</p><div class="variablelist"><dl><dt><span class="term"><a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a></span></dt><dd>This uses the fastest possible hash function.
Its drawback is that its hash codes become invalid at every <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion
(except if all keys are <a href="lisp-obj-in-c.html#immediate-o">immediate object</a>s),
thus requiring a reorganization of the hash table at the first
access after each <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion. Especially when generational <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion is used,
which leads to frequent small <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ions, large hash table with this test
can lead to scalability problems.</dd><dt><span class="term"><a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a></span></dt><dd>This uses a slower hash function that has the
property that its hash codes for instances of the classes <a href="http://www.lisp.org/HyperSpec/Body/syscla_symbol.html" target="_top"><code class="classname">SYMBOL</code></a>,
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STANDARD-STABLEHASH</code></a> (subclass of <a href="http://www.lisp.org/HyperSpec/Body/cla_standard-object.html" target="_top"><code class="classname">STANDARD-OBJECT</code></a>) and
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STRUCTURE-STABLEHASH</code></a> (subclass of <a href="http://www.lisp.org/HyperSpec/Body/cla_structure-object.html" target="_top"><code class="classname">STRUCTURE-OBJECT</code></a>) are
stable across GCs.
This test can thus avoid the scalability problems if all keys,
other than <a href="lisp-obj-in-c.html#immediate-o">immediate object</a>s, are <a href="http://www.lisp.org/HyperSpec/Body/syscla_symbol.html" target="_top"><code class="classname">SYMBOL</code></a>, <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STANDARD-STABLEHASH</code></a> or
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STRUCTURE-STABLEHASH</code></a> instances.</dd></dl></div><p>
One can recommend to use <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a> for short-lived hash tables.
For tables with a longer lifespan which can be big or accessed
frequently, it is recommended to use <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>, and to modify the
objects that are used as its keys to become instances of
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STANDARD-STABLEHASH</code></a> or <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STRUCTURE-STABLEHASH</code></a>.
</p><p>When the symbol <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a> or the function <code class="literal">#'eq</code> is
used as a <code class="constant">:TEST</code> argument, the value of the variable
<code class="varname">EXT:*EQ-HASHFUNCTION*</code> is used instead. This value must
be one of <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a>, <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>.</p><p>Similarly, the <code class="constant">:TEST</code> argument can also be one
of the symbols <code class="constant">EXT:FASTHASH-EQL</code>,
<code class="constant">EXT:STABLEHASH-EQL</code>,
<code class="constant">EXT:FASTHASH-EQUAL</code>,
<code class="constant">EXT:STABLEHASH-EQUAL</code>.
The same remarks apply as for <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a> and <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>.
When the symbol <a href="http://www.lisp.org/HyperSpec/Body/fun_eql.html" target="_top"><code class="function">EQL</code></a> or the function <code class="literal">#'eql</code> is used
as a <code class="constant">:TEST</code> argument, the value of the variable
<code class="varname">EXT:*EQL-HASHFUNCTION*</code> is used instead; this value must
be one of <code class="constant">EXT:FASTHASH-EQL</code>,
<code class="constant">EXT:STABLEHASH-EQL</code>.
Similarly, when the symbol <a href="http://www.lisp.org/HyperSpec/Body/fun_equal.html" target="_top"><code class="function">EQUAL</code></a> or the function <code class="literal">#'equal</code>
is used as a <code class="constant">:TEST</code> argument, the value of the variable
<code class="varname">EXT:*EQUAL-HASHFUNCTION*</code> is used instead; this value
must be one of <code class="constant">EXT:FASTHASH-EQUAL</code>,
<code class="constant">EXT:STABLEHASH-EQUAL</code>.</p><p>The <code class="constant">:WARN-IF-NEEDS-REHASH-AFTER-GC</code> argument,
if true, causes a <a href="http://www.lisp.org/HyperSpec/Body/contyp_warning.html" target="_top"><code class="classname">WARNING</code></a> to be <a href="http://www.lisp.org/HyperSpec/Body/fun_signal.html" target="_top"><code class="function">SIGNAL</code></a>ed when an object is stored
into the table which will force table reorganizations at the first
access of the table after each <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion.
This keyword argument can be used to check whether <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>
should be preferred over <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a> for a particular table.
Use <code class="function">HASH-TABLE-WARN-IF-NEEDS-REHASH-AFTER-GC</code>
to check and <a href="http://www.lisp.org/HyperSpec/Body/mac_setfcm_psetf.html" target="_top"><code class="function">SETF</code></a> this parameter after the table has been created.</p><p>The <code class="constant">:INITIAL-CONTENTS</code> argument is an
<a href="http://www.lisp.org/HyperSpec/Body/glo_a.html#association_list" target="_top">alist</a> that is used to initialize the new hash table.</p><p>The <code class="constant">:REHASH-THRESHOLD</code> argument is ignored.</p><p>The <code class="constant">:WEAK</code> argument can take the following values:
</p><table class="simplelist" border="0" summary="Simple list"><tr><td><a href="http://www.lisp.org/HyperSpec/Body/convar_nil.html" target="_top"><code class="constant">NIL</code></a> (default)</td></tr><tr><td><code class="constant">:KEY</code></td></tr><tr><td><code class="constant">:VALUE</code></td></tr><tr><td><code class="constant">:KEY-AND-VALUE</code></td></tr><tr><td><code class="constant">:KEY-OR-VALUE</code></td></tr></table><p>
and specifies whether the <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a> is <span class="emphasis"><em>weak</em></span>:
if the key, value, either or both are not accessible for the <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion
purposes, i.e., if they are only accessible via weak <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>s
and <a href="weak.html#weak-pointer" title="30.7.1. Weak Pointers"><code class="classname">EXT:WEAK-POINTER</code></a>s, it is <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ed and removed from the weak
<a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>.</p><p>The <a href="http://www.lisp.org/HyperSpec/Body/mac_setfcm_psetf.html" target="_top"><code class="function">SETF</code></a>able predicate <code class="function">EXT:HASH-TABLE-WEAK-P</code>
checks whether the <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a> is weak.</p><p>Note that the only test that makes sense for weak hash tables are
<a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a> and its variants <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a> and <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>.</p><p>Just like all other <a href="weak.html" title="30.7. Weak Objects">weak objects</a>, weak
<a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>s cannot be printed readably.</p><p>See also <a href="weak.html#weak-ht" title="30.7.9. Weak Hash Tables">Section 30.7.9, “Weak Hash Tables”</a>.</p><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="hashtable-gc-rehash"></a>18.1.1.1. Interaction between <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>s and <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion</h4></div></div></div><p>When a hash table contains keys to be compared by identity - such
as <a href="http://www.lisp.org/HyperSpec/Body/syscla_number.html" target="_top"><code class="classname">NUMBER</code></a>s in <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>s with the <a href="http://www.lisp.org/HyperSpec/Body/fun_hash-table-test.html" target="_top"><code class="function">HASH-TABLE-TEST</code></a> <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a>;
or <a href="http://www.lisp.org/HyperSpec/Body/syscla_cons.html" target="_top"><code class="classname">CONS</code></a>es in tables which test with <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a> or <a href="http://www.lisp.org/HyperSpec/Body/fun_eql.html" target="_top"><code class="function">EQL</code></a>;
or <a href="http://www.lisp.org/HyperSpec/Body/syscla_vector.html" target="_top"><code class="classname">VECTOR</code></a>s in tables which test with <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a>, <a href="http://www.lisp.org/HyperSpec/Body/fun_eql.html" target="_top"><code class="function">EQL</code></a> or <a href="http://www.lisp.org/HyperSpec/Body/fun_equal.html" target="_top"><code class="function">EQUAL</code></a>;
or <a href="http://www.lisp.org/HyperSpec/Body/cla_standard-object.html" target="_top"><code class="classname">STANDARD-OBJECT</code></a> or <a href="http://www.lisp.org/HyperSpec/Body/cla_structure-object.html" target="_top"><code class="classname">STRUCTURE-OBJECT</code></a> instances in tables which
test with <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a>, <a href="http://www.lisp.org/HyperSpec/Body/fun_eql.html" target="_top"><code class="function">EQL</code></a>, <a href="http://www.lisp.org/HyperSpec/Body/fun_equal.html" target="_top"><code class="function">EQUAL</code></a> or <a href="http://www.lisp.org/HyperSpec/Body/fun_equalp.html" target="_top"><code class="function">EQUALP</code></a>;
- the hash code will in general depend on the object's address in
memory. Therefore it will in general be invalidated after a <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion,
and the hash table's internal structure must be recomputed at the next
table access.</p><p>While <code class="constant">:WARN-IF-NEEDS-REHASH-AFTER-GC</code> can help
checking the efficiency of a particular <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>, the variable
<strong class="first"><em class="firstterm"><a href="hash-dict.html#hashtable-gc-rehash-warn"><code class="varname">CUSTOM:*WARN-ON-HASHTABLE-NEEDING-REHASH-AFTER-GC*</code></a>
<a id="hashtable-gc-rehash-warn" class="indexterm"></a></em></strong>
achieves the same effect for all <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>s in the system at once:
when <a href="hash-dict.html#hashtable-gc-rehash-warn"><code class="varname">CUSTOM:*WARN-ON-HASHTABLE-NEEDING-REHASH-AFTER-GC*</code></a> is true and a
<a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a> needs to be rehashed after a <a href="gc.html" title="Chapter 34. Overview of CLISP's Garbage Collection">garbage-collect</a>ion, a warning is
issued that shows the inefficient <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>.</p><p>What can be done to avoid the inefficiencies detected by these warnings?
</p><div class="orderedlist"><ol type="1"><li>In many cases you can solve the problem
by using the <code class="function">STABLEHASH</code> variant of the hash
test.</li><li>In other cases, namely <a href="http://www.lisp.org/HyperSpec/Body/cla_standard-object.html" target="_top"><code class="classname">STANDARD-OBJECT</code></a> or
<a href="http://www.lisp.org/HyperSpec/Body/cla_structure-object.html" target="_top"><code class="classname">STRUCTURE-OBJECT</code></a> instances, you can solve the problem by making
the key object classes inherit from <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STANDARD-STABLEHASH</code></a> or
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="classname">EXT:STRUCTURE-STABLEHASH</code></a>, respectively.</li><li>In the remaining cases, you should store a hash key
inside the object, of which you can guarantee uniqueness through
your application (for example the ID of an object in a database, or
the serial number of an object), and use this key as hash key
instead of the original object.</li></ol></div></div></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="defhash"></a>18.1.2. Macro <a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a></h3></div></div></div><p>You can define a new hash table test using the macro
<a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a>: <code class="code">(<a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a> test-name <em class="replaceable"><code>test-function</code></em> <em class="replaceable"><code>hash-function</code></em>)</code>, after
which <em class="replaceable"><code>test-name</code></em> can be passed as the
<code class="constant">:TEST</code> argument to <a href="http://www.lisp.org/HyperSpec/Body/fun_make-hash-table.html" target="_top"><code class="function">MAKE-HASH-TABLE</code></a>.
E.g.: </p><pre class="programlisting">(<a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a> string <a href="http://www.lisp.org/HyperSpec/Body/fun_stringeqc_ng-not-lessp.html" target="_top"><code class="function">STRING=</code></a> <a href="http://www.lisp.org/HyperSpec/Body/fun_sxhash.html" target="_top"><code class="function">SXHASH</code></a>)
(<a href="http://www.lisp.org/HyperSpec/Body/fun_make-hash-table.html" target="_top"><code class="function">MAKE-HASH-TABLE</code></a> :test 'string)</pre><p>
(which is not too useful because it is equivalent to an <a href="http://www.lisp.org/HyperSpec/Body/fun_equal.html" target="_top"><code class="function">EQUAL</code></a>
<a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a> but less efficient).</p><p>The fundamental requirement is that the <em class="replaceable"><code>test-function</code></em> and <em class="replaceable"><code>hash-function</code></em> are
consistent: </p><pre class="programlisting">
(<a href="http://www.lisp.org/HyperSpec/Body/fun_funcall.html" target="_top"><code class="function">FUNCALL</code></a> <em class="replaceable"><code>test-function</code></em> <em class="replaceable"><code>x</code></em> <em class="replaceable"><code>y</code></em>) ⇒
(<a href="http://www.lisp.org/HyperSpec/Body/fun_eqcm_sleq__lteqcm_gteq.html" target="_top"><code class="function">=</code></a> (<a href="http://www.lisp.org/HyperSpec/Body/fun_funcall.html" target="_top"><code class="function">FUNCALL</code></a> <em class="replaceable"><code>hash-function</code></em> <em class="replaceable"><code>x</code></em>) (<a href="http://www.lisp.org/HyperSpec/Body/fun_funcall.html" target="_top"><code class="function">FUNCALL</code></a> <em class="replaceable"><code>hash-function</code></em> <em class="replaceable"><code>y</code></em>))
</pre><p>
This means that the following definition: </p><pre class="programlisting">
(<a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a> number <a href="http://www.lisp.org/HyperSpec/Body/fun_eqcm_sleq__lteqcm_gteq.html" target="_top"><code class="function">=</code></a> <a href="http://www.lisp.org/HyperSpec/Body/fun_sxhash.html" target="_top"><code class="function">SXHASH</code></a>) <em class="lineannotation"><span class="lineannotation">; broken!</span></em>
</pre><p>
is <span class="strong"><strong>not</strong></span> correct because <code class="code">(<a href="http://www.lisp.org/HyperSpec/Body/fun_eqcm_sleq__lteqcm_gteq.html" target="_top"><code class="function">=</code></a> 1 1d0)</code> is
<a href="http://www.lisp.org/HyperSpec/Body/convar_t.html" target="_top"><code class="constant">T</code></a> but <code class="code">(<a href="http://www.lisp.org/HyperSpec/Body/fun_eqcm_sleq__lteqcm_gteq.html" target="_top"><code class="function">=</code></a> (<a href="http://www.lisp.org/HyperSpec/Body/fun_sxhash.html" target="_top"><code class="function">SXHASH</code></a> 1) (<a href="http://www.lisp.org/HyperSpec/Body/fun_sxhash.html" target="_top"><code class="function">SXHASH</code></a> 1d0))</code>
is <a href="http://www.lisp.org/HyperSpec/Body/convar_nil.html" target="_top"><code class="constant">NIL</code></a>. The correct way is, e.g.: </p><pre class="programlisting">
(<a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a> number <a href="http://www.lisp.org/HyperSpec/Body/fun_eqcm_sleq__lteqcm_gteq.html" target="_top"><code class="function">=</code></a> (<a href="http://www.lisp.org/HyperSpec/Body/mac_lambda.html" target="_top"><code class="function">LAMBDA</code></a> (x) (<a href="http://www.lisp.org/HyperSpec/Body/fun_sxhash.html" target="_top"><code class="function">SXHASH</code></a> (<a href="http://www.lisp.org/HyperSpec/Body/fun_coerce.html" target="_top"><code class="function">COERCE</code></a> x '<a href="http://www.lisp.org/HyperSpec/Body/typ_short-flo_m_long-float.html" target="_top"><code class="classname">SHORT-FLOAT</code></a>))))
</pre><p>
(note that <code class="code">(<a href="http://www.lisp.org/HyperSpec/Body/fun_coerce.html" target="_top"><code class="function">COERCE</code></a> <em class="replaceable"><code>x</code></em> <a href="http://www.lisp.org/HyperSpec/Body/typ_short-flo_m_long-float.html" target="_top"><code class="classname">SHORT-FLOAT</code></a>)</code> does <span class="strong"><strong>not</strong></span>
cons up <a href="http://www.lisp.org/HyperSpec/Body/glo_f.html#fresh" target="_top">fresh</a> objects while <code class="code">(<a href="http://www.lisp.org/HyperSpec/Body/fun_coerce.html" target="_top"><code class="function">COERCE</code></a> <em class="replaceable"><code>x</code></em>
<a href="http://www.lisp.org/HyperSpec/Body/typ_short-flo_m_long-float.html" target="_top"><code class="classname">DOUBLE-FLOAT</code></a>)</code> does).</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="ht-test"></a>18.1.3. Function <a href="http://www.lisp.org/HyperSpec/Body/fun_hash-table-test.html" target="_top"><code class="function">HASH-TABLE-TEST</code></a></h3></div></div></div><p>Function <a href="http://www.lisp.org/HyperSpec/Body/fun_hash-table-test.html" target="_top"><code class="function">HASH-TABLE-TEST</code></a> returns either one of <a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:FASTHASH-EQ</code></a>,
<a href="hash-dict.html#make-hash" title="18.1.1. Function MAKE-HASH-TABLE"><code class="constant">EXT:STABLEHASH-EQ</code></a>, <code class="constant">EXT:FASTHASH-EQL</code>,
<code class="constant">EXT:STABLEHASH-EQL</code>,
<code class="constant">EXT:FASTHASH-EQUAL</code>,
<code class="constant">EXT:STABLEHASH-EQUAL</code>, <a href="http://www.lisp.org/HyperSpec/Body/fun_equalp.html" target="_top"><code class="function">EQUALP</code></a> (but not <a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html" target="_top"><code class="function">EQ</code></a>, <a href="http://www.lisp.org/HyperSpec/Body/fun_eql.html" target="_top"><code class="function">EQL</code></a>
nor <a href="http://www.lisp.org/HyperSpec/Body/fun_equal.html" target="_top"><code class="function">EQUAL</code></a> anymore), or, for <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>s
created with a user-defined <a href="http://www.lisp.org/HyperSpec/Body/fun_hash-table-test.html" target="_top"><code class="function">HASH-TABLE-TEST</code></a> (see macro <a href="hash-dict.html#defhash" title="18.1.2. Macro EXT:DEFINE-HASH-TABLE-TEST"><code class="function">EXT:DEFINE-HASH-TABLE-TEST</code></a>),
a <a href="http://www.lisp.org/HyperSpec/Body/syscla_cons.html" target="_top"><code class="classname">CONS</code></a> cell <span class="data"><code class="literal">(<em class="replaceable"><code>test-function</code></em> . <em class="replaceable"><code>hash-function</code></em>)</code></span>.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="dohash"></a>18.1.4. Macro <a href="hash-dict.html#dohash" title="18.1.4. Macro EXT:DOHASH"><code class="function">EXT:DOHASH</code></a></h3></div></div></div><p>For iteration through a <a href="http://www.lisp.org/HyperSpec/Body/syscla_hash-table.html" target="_top"><code class="classname">HASH-TABLE</code></a>, a macro <a href="hash-dict.html#dohash" title="18.1.4. Macro EXT:DOHASH"><code class="function">EXT:DOHASH</code></a>,
similar to <a href="http://www.lisp.org/HyperSpec/Body/mac_dolist.html" target="_top"><code class="function">DOLIST</code></a>, can be used instead of <a href="http://www.lisp.org/HyperSpec/Body/fun_maphash.html" target="_top"><code class="function">MAPHASH</code></a>:</p><pre class="programlisting">
(<a href="hash-dict.html#dohash" title="18.1.4. Macro EXT:DOHASH"><code class="function">EXT:DOHASH</code></a> (<em class="replaceable"><code>key-var</code></em> <em class="replaceable"><code>value-var</code></em> <em class="replaceable"><code>hash-table-form</code></em> [<em class="replaceable"><code>resultform</code></em>])
{<em class="replaceable"><code>declaration</code></em>}*
{<em class="replaceable"><code>tag</code></em>|<em class="replaceable"><code>form</code></em>}*)
</pre><p><a href="hash-dict.html#dohash" title="18.1.4. Macro EXT:DOHASH"><code class="function">EXT:DOHASH</code></a> forms are <a href="http://www.lisp.org/HyperSpec/Body/glo_i.html#iteration_form" target="_top">iteration form</a>s.</p></div></div><div class="bookinfo"><hr width="100%" /><table width="100%" summary="impnotes meta info"><th><td align="left">These notes document <a href="http://clisp.cons.org" target="_top"><span><strong class="command">CLISP</strong></span></a> version 2.37</td><td align="right">Last modified: 2006-01-02</td></th></table></div><div class="custom-footer"><hr width="100%" /><table width="100%"><tr><td align="left"><a href="http://clisp.cons.org"><img src="clisp.png" width="48" height="48" alt="[CLISP home]" /></a></td><td align="center"><a href="http://sourceforge.net/donate/index.php?group_id=1355"><img src="http://images.sourceforge.net/images/project-support.jpg" width="88" height="32" border="0" alt="[Support This Project]" /></a></td><td align="right"><a href="http://sourceforge.net"><img width="125" height="37" alt="[SourceForge]" src="http://sflogo.sourceforge.net/sflogo.php?group_id=1355&amp;type=2&amp;page=hash-dict" /></a></td></tr></table></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="hash.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="hash.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="filenames.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 18. Hash Tables
[CLHS-18] </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 19. Filenames
[CLHS-19]</td></tr></table></div></body></html>