Debian Codegraph @

docsrc/xlisp/xlisp-doc/examples/hash-tables.htm

raw
1 <html><head>
2
3 <title>Hash Tables</title>
4
5 <style type="text/css">
6 .example {
7 color: #000000;
8 background-color: #F5F5F5;
9 padding: 8px;
10 border: #808080;
11 border-style: solid;
12 border-width: 1px;
13 width:auto;
14 }
15 .button {
16 color: #000000;
17 background-color: #F5F5F5;
18 padding-top: 1px;
19 padding-bottom: 1px;
20 padding-left: 4px;
21 padding-right: 8px;
22 border: #808080;
23 border-style: solid;
24 border-width: 1px;
25 }
26 .box {
27 color: #000000;
28 padding-top: 4px;
29 padding-bottom: 4px;
30 padding-left: 16px;
31 padding-right: 16px;
32 border: #808080;
33 border-style: solid;
34 border-width: 1px;
35 }
36 </style>
37
38 </head>
39
40 <body>
41
42 <a href="../start.htm">Nyquist / XLISP 2.0</a>&nbsp; -&nbsp;
43 <a href="../manual/contents.htm">Contents</a> |
44 <a href="../tutorials/tutorials.htm">Tutorials</a> |
45 <a href="examples.htm">Examples</a> |
46 <a href="../reference/reference-index.htm">Reference</a>
47
48 <hr>
49
50 <h1>Hash Tables</h1>
51
52 <hr>
53
54 <p>The internal XLISP 'hash' function from 'xlsym.c':</p>
55
56 <pre class="example">
57 <font color="#008844">/* hash - hash a symbol name string */</font>
58 int <font color="#0000CC">hash</font>(char *str, int len)
59 {
60 int i;
61 for (i = 0; *str; )
62 i = (i &lt;&lt; 2) ^ *str++;
63 i %= len;
64 return (i &lt; 0 ? -i : i);
65 }
66 </pre>
67
68 <p>In XLISP this would look like:</p>
69
70 <pre class="example">
71 (defun <font color="#0000CC">lisp-hash</font> (string table-size)
72 (let ((i 0))
73 (dotimes (index (length string))
74 (setq i (logxor (bsh i 2) (char-code (char string index)))))
75 (setq i (rem i table-size))
76 (if (minusp i) (- i) i)))
77 </pre>
78
79 <p>A <a href="../reference/hash.htm">hash</a> function is a kind of random
80 number generator, where the same input always produces the same output
81 number. <nobr>The XLISP</nobr> <a href="../reference/hash.htm">hash</a>
82 function computes equally distributed integer numbers in a given range from
83 the characters of an input string.</p>
84
85 <p>A very simple example:</p>
86
87 <ol>
88
89 <li><p>We want to store <nobr>4 strings</nobr> in <nobr>2 lists</nobr>,
90 stored in <nobr>2 array</nobr> elements:</p>
91
92 <pre class="example">
93 &gt; (setq my-array (make-array 2))
94 #(NIL NIL) <font color="#008844">; NIL NIL = two empty lists</font>
95 </pre>
96
97 <p>If the array index is computed by the
98 <a href="../reference/hash.htm">hash</a> function, then the equally
99 distributed numbers make sure that every list will contain approximately
100 the same number of strings:</p>
101
102 <pre class="example">
103 &gt; (dolist (string '("a" "b" "c" "d") my-array)
104 (push string (aref my-array (<font color="#AA0000">hash</font> string (length my-array)))))
105 #(("d" "b") ("c" "a"))
106 </pre>
107
108 <p>The order of the strings in the array was computed by the
109 <a href="../reference/hash.htm">hash</a> function, it is not the same order
110 as given to <a href="../reference/dolist.htm">dolist</a>.</p></li>
111
112 <li><p><nobr>If we</nobr> now search for a string in the lists then the
113 <a href="../reference/hash.htm">hash</a> function will tell us the number of
114 the array element with the list containing the string because the same input
115 string to the <a href="../reference/hash.htm">hash</a> function always
116 produces the same output number, as long as the same
117 '<nobr>table-size</nobr>' [the same number of array elements] is used:</p>
118
119 <pre class="example">
120 &gt; (dolist (string '("a" "b" "c" "d"))
121 (format t "~s = ~s~%" string
122 (aref my-array (<font color="#AA0000">hash</font> string (length my-array)))))
123 "a" = ("c" "a")
124 "b" = ("d" "b")
125 "c" = ("c" "a")
126 "d" = ("d" "b")
127 NIL
128 </pre>
129
130 <p>The <a href="../reference/hash.htm">hash</a> function will always find
131 the correct list as long as the number of array elements has not
132 changed.</p> </li>
133
134 </ol>
135
136 <p>The two main tasks of the <a href="../reference/hash.htm">hash</a>
137 <nobr>function are</nobr>:</p>
138
139 <ol>
140
141 <li><p>Make sure that all lists contain approximately the same number of
142 elements, independent from the characters in the input strings, no matter if
143 the strings are very similar or completely different. With the
144 <a href="../reference/hash.htm">hash</a> function it will nearly never
145 happen that one list contains all strings while all other lists are
146 empty.</p></li>
147
148 <li><p>With the same 'name' and '<nobr>table-size</nobr>' arguments the
149 <a href="../reference/hash.htm">hash</a> function will always return exactly
150 the same integer number, so a string can always be found no matter in what
151 order the strings are stored in the lists of the array.</p></li>
152
153 </ol>
154
155 <p>Now we can find strings stored in lists, but we want to store and find
156 arbitrary things. Therefore we replace the ordinary lists with association
157 lists:</p>
158
159 <pre class="example">
160 &gt; (setq my-array (make-array 2))
161 #(() ())
162
163 &gt; (dolist (a-cons '(("a" . 1) ("b" . 2) ("c" . 3) ("d" . 4)) my-array)
164 (push a-cons (aref my-array (<font color="#AA0000">hash</font> (car a-cons) (length my-array)))))
165 #((("d" . 4) ("b" . 2)) (("c" . 3) ("a" . 1)))
166 </pre>
167
168 <p>We now have an array like this:</p>
169
170 <p><table cellpadding="0" cellspacing="0"><tbody>
171 <tr>
172 <td></td>
173 <td align="center"><nobr>Array&nbsp;</nobr></td>
174 </tr>
175 <tr>
176 <td height="2px"></td>
177 </tr>
178 <tr>
179 <td align="right"><nobr><code>&nbsp;&nbsp;</code>0<code>&nbsp;</code></nobr></td>
180 <td class="button"><nobr>Association List 1</nobr></td>
181 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
182 <td class="button"><nobr><code>(("d" . 4) ("b" . 2))</code></nobr></td>
183 </tr>
184 <tr>
185 <td height="2px"></td>
186 </tr>
187 <tr>
188 <td align="right"><nobr><code>&nbsp;&nbsp;</code>1<code>&nbsp;</code></nobr></td>
189 <td class="button"><nobr>Association List 2</nobr></td>
190 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
191 <td class="button"><nobr><code>(("c" . 3) ("a" . 1))</code></nobr></td>
192 </tr>
193 </tbody></table></p>
194
195 <p>The association lists give the flexibility to store an arbitrary number
196 of <nobr>key/value</nobr> pairs, we are not limited by the fixed number of
197 array elements, while the array together with the
198 <a href="../reference/hash.htm">hash</a> function gives much more speed than
199 a single association list if we want to manage a big number of
200 <nobr>key/value pairs</nobr>.</p>
201
202 <p>With a big number of key/value pairs it is faster to keep them in many
203 small association lists than in one single <nobr>big list</nobr>. Arrays
204 provide random access, where every element can be accessed in the same time,
205 while a list can only be searched from the beginning up to the matching
206 element. <nobr>The longer</nobr> the list, the slower the search
207 becomes.</p>
208
209 <p>With the <a href="../reference/hash.htm">hash</a> function we find the
210 association list containing <nobr>the key</nobr>:</p>
211
212 <pre class="example">
213 &gt; (dolist (key '("a" "b" "c" "d"))
214 (format t "~s = ~s~%" key
215 (aref my-array (<font color="#AA0000">hash</font> key (length my-array)))))
216 "a" = (("c" . 3) ("a" . 1))
217 "b" = (("d" . 4) ("b" . 2))
218 "c" = (("c" . 3) ("a" . 1))
219 "d" = (("d" . 4) ("b" . 2))
220 NIL
221 </pre>
222
223 <p>With the <a href="../reference/assoc.htm">assoc</a> function we find the
224 <nobr>key/value pair</nobr>:</p>
225
226 <pre class="example">
227 &gt; (dolist (key '("a" "b" "c" "d"))
228 (format t "~s = ~s~%" key
229 (<font color="#AA0000">assoc</font> key (aref my-array (<font color="#AA0000">hash</font> key (length my-array)))
230 :test #'equal)))
231 "a" = ("a" . 1)
232 "b" = ("b" . 2)
233 "c" = ("c" . 3)
234 "d" = ("d" . 4)
235 NIL
236 </pre>
237
238 <p>With the <a href="../reference/cdr.htm">cdr</a> function we get the
239 value:</p>
240
241 <pre class="example">
242 &gt; (dolist (key '("a" "b" "c" "d"))
243 (format t "~s = ~s~%" key
244 (<font color="#AA0000">cdr</font> (<font color="#AA0000">assoc</font> key (aref my-array (<font color="#AA0000">hash</font> key (length my-array)))
245 :test #'equal))))
246 "a" = 1
247 "b" = 2
248 "c" = 3
249 "d" = 4
250 NIL
251 </pre>
252
253 <p>And now we have our first working <nobr>hash-table</nobr>.</p>
254
255 <p>But we still have one problem. <nobr>The
256 <a href="../reference/hash.htm">hash</a></nobr> function works only with
257 symbols or strings, while <a href="../reference/assoc.htm">assoc</a> can
258 also work with numbers, strings and even lists as 'key' argument. <nobr>To
259 make</nobr> our <nobr>hash-table</nobr> work with all types
260 <a href="../reference/assoc.htm">assoc</a> can handle, we must make the
261 <a href="../reference/hash.htm">hash</a> function happy and convert the
262 'key' argument with <a href="../reference/format.htm">format</a> into a
263 string before computing the <nobr>hash index:</nobr></p>
264
265 <pre class="example">
266 &gt; (setq my-array (make-array 2))
267 #(() ())
268
269 &gt; (dolist (a-cons '((#\x . 1) ((y z) . 2) (12 . 3) (6.5 . 4)) my-array)
270 (push a-cons (aref my-array (<font color="#AA0000">hash</font> (<font color="#AA0000">format</font> nil "~s" (car a-cons))
271 (length my-array)))))
272 #(((12 . 3) (#\x . 1)) ((6.5 . 4) ((Y Z) . 2)))
273
274 &gt; (dolist (key '(#\x (y z) 12 6.5))
275 (format t "~s = ~s~%" key
276 (<font color="#AA0000">cdr</font> (<font color="#AA0000">assoc</font> key (aref my-array (<font color="#AA0000">hash</font> (<font color="#AA0000">format</font> nil "~s" key)
277 (length my-array)))
278 :test #'equal))))
279 #\x = 1
280 (Y Z) = 2
281 12 = 3
282 6.5 = 4
283 NIL
284 </pre>
285
286 <p>Wonderful.</p>
287
288 <p>A final quirk still needs to be solved. Maybe you have noticed the :test
289 argument to <a href="../reference/assoc.htm">assoc</a>. Like with all Lisp
290 functions providing :test arguments, the
291 <a href="../reference/assoc.htm">assoc</a> :test defaults to
292 <a href="../reference/eql.htm">eql</a> [because
293 <a href="../reference/eq.htm">eq</a> is unreliable with numbers, and
294 <a href="../reference/eql.htm">eql</a> is faster
295 <nobr>than <a href="../reference/equal.htm">equal</a>]</nobr>, but
296 <a href="../reference/eql.htm">eql</a> doesn't work with
297 <nobr>floating-point</nobr> numbers, strings and lists, so we had to
298 <nobr>use <a href="../reference/equal.htm">equal</a></nobr>.</p>
299
300 <p>The typical Lisp solution is to provide a :test argument to the
301 'make-hash-table' function, so the programmer can choose which function to
302 use. <nobr>The :test</nobr> argument to 'make-hash-table' becomes a property
303 of the <nobr>hash-table</nobr> itself, so the :test only needs to be given
304 once, at the time when the <nobr>hash-table</nobr> is created, and not every
305 time the <nobr>hash-table</nobr> is accessed afterwards.</p>
306
307 <p>We have the problem that <nobr>hash-tables</nobr> are no
308 <nobr>built-in</nobr> XLISP data type and we want use
309 <nobr>make-hash-table</nobr> in the same way
310 <nobr>as <a href="../reference/make-array.htm">make-array</a></nobr>:</p>
311
312 <pre class="example">
313 (setq my-hash-table (make-hash-table <font color="#0000CC">size</font> :test #'equal))
314 </pre>
315
316 <p>Here the make-hash-table function has no access to the property list of
317 the '<nobr>my-hash-table</nobr>' symbol, so the only solution is to make the
318 :test function become part of the <nobr>hash-table</nobr> itself:</p>
319
320 <p><table cellpadding="0" cellspacing="0"><tbody>
321 <tr>
322 <td></td>
323 <td align="center"><nobr>Array&nbsp;</nobr></td>
324 </tr>
325 <tr>
326 <td height="2px"></td>
327 </tr>
328 <tr>
329 <td align="right"><nobr><code>&nbsp;&nbsp;</code>0<code>&nbsp;</code></nobr></td>
330 <td class="button"><nobr>Test Function</nobr></td>
331 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
332 <td width="100%"><nobr>the :test argument to
333 <a href="../reference/assoc.htm">assoc</a></nobr></td>
334 </tr>
335 <tr>
336 <td height="2px"></td>
337 </tr>
338 <tr>
339 <td align="right"><nobr><code>&nbsp;&nbsp;</code>1<code>&nbsp;</code></nobr></td>
340 <td class="button"><nobr>Association List 1</nobr></td>
341 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
342 <td width="100%"><nobr>((<i>key1</i> . <i>value1</i>)
343 ... (<i>keyN</i> . <i>valueN</i>))</nobr></td>
344 </tr>
345 <tr>
346 <td height="2px"></td>
347 </tr>
348 <tr>
349 <td align="right"><nobr><code>&nbsp;&nbsp;</code>2<code>&nbsp;</code></nobr></td>
350 <td class="button"><nobr>Association List 2</nobr></td>
351 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
352 <td width="100%"><nobr>((<i>key1</i> . <i>value1</i>)
353 ... (<i>keyN</i> . <i>valueN</i>))</nobr></td>
354 </tr>
355 <tr>
356 <td height="2px"></td>
357 </tr>
358 <tr>
359 <td align="right"><nobr><code>&nbsp;&nbsp;</code>3<code>&nbsp;</code></nobr></td>
360 <td class="button"><nobr>Association List 3</nobr></td>
361 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
362 <td width="100%"><nobr>((<i>key1</i> . <i>value1</i>)
363 ... (<i>keyN</i> . <i>valueN</i>))</nobr></td>
364 </tr>
365 <tr>
366 <td></td>
367 <td align="center"><nobr>...<code>&nbsp;</code></nobr></td>
368 </tr>
369 <tr>
370 <td height="2px"></td>
371 </tr>
372 <tr>
373 <td align="right"><nobr><code>&nbsp;&nbsp;</code><i>n</i><code>&nbsp;</code></nobr></td>
374 <td class="button"><nobr>Association List <i>n</i></nobr></td>
375 <td><nobr>&nbsp;&rarr;&nbsp;</nobr></td>
376 <td width="100%"><nobr>((<i>key1</i> . <i>value1</i>)
377 ... (<i>keyN</i> . <i>valueN</i>))</nobr></td>
378 </tr>
379 </tbody></table></p>
380
381 <p>This is the final layout of our <nobr>hash-tables</nobr>, so we can start
382 to implement the <nobr>hash-table</nobr> functions.</p>
383
384 <p><nobr>&nbsp;&nbsp;<a href="#top">Back to top</a></nobr></p>
385
386 <a name="make-hash-table"></a>
387
388 <hr>
389
390 <h2>make-hash-table</h2>
391
392 <hr>
393
394 <pre class="example">
395 (defun <font color="#0000CC">make-hash-table</font> (size &amp;optional (test #'eql))
396 (and (&lt; size 1) (error <font color="#880000">"hash-table minimum size is 1"</font> size))
397 (let ((hash-table (make-array (1+ size))))
398 (setf (aref hash-table 0) test)
399 hash-table))
400
401 (defun <font color="#0000CC">gethash</font> (key hash-table)
402 (let* ((size (1- (length hash-table)))
403 (index (1+ (hash (format nil "~s" key) size)))
404 (a-list (aref hash-table index))
405 (test (aref hash-table 0)))
406 (cdr (assoc key a-list :test test))))
407
408 (defun <font color="#0000CC">puthash</font> (key value hash-table)
409 (let* ((size (1- (length hash-table)))
410 (index (1+ (hash (format nil "~s" key) size)))
411 (a-list (aref hash-table index))
412 (test (aref hash-table 0))
413 (a-cons (assoc key a-list :test test)))
414 (setf (aref hash-table index)
415 (cons (cons key value)
416 (if a-cons
417 (remove-if #'(lambda (x)
418 (funcall test key (car x)))
419 a-list)
420 a-list)))))
421
422 (defun <font color="#0000CC">remhash</font> (key hash-table)
423 (let* ((size (1- (length hash-table)))
424 (index (1+ (hash (format nil "~s" key) size)))
425 (a-list (aref hash-table index))
426 (test (aref hash-table 0))
427 (a-cons (assoc key a-list :test test)))
428 (and a-cons
429 (setf (aref hash-table index)
430 (remove-if #'(lambda (x)
431 (funcall test key (car x)))
432 a-list)))
433 a-cons))
434
435 (defun <font color="#0000CC">clrhash</font> (hash-table)
436 (let ((size (1- (length hash-table))))
437 (do ((index 1 (1+ index)))
438 ((&gt; index size))
439 (setf (aref hash-table index) nil))
440 hash-table))
441
442 (defun <font color="#0000CC">hash-table-p</font> (expr)
443 (and (arrayp expr) <font color="#008844">; expression is an array</font>
444 (&gt; (length expr) 1) <font color="#008844">; with more than one elements</font>
445 (fboundp (aref expr 0)) <font color="#008844">; first element is a function</font>
446 (let ((size (1- (length expr)))) <font color="#008844">; all other</font>
447 (do ((index 1 (1+ index))) <font color="#008844">; elements are lists</font>
448 ((or (&gt; index size)
449 (not (listp (aref expr index))))
450 (&gt; index size))))))
451
452 (defun <font color="#0000CC">hash-table-count</font> (hash-table)
453 (let ((size (1- (length hash-table)))
454 (entries 0))
455 (do ((index 1 (1+ index)))
456 ((&gt; index size))
457 (setf entries (+ entries (length (aref hash-table index)))))
458 entries))
459
460 (defun <font color="#0000CC">hash-table-size</font> (hash-table)
461 (1- (length hash-table)))
462
463 (defun <font color="#0000CC">hash-table-test</font> (hash-table)
464 (aref hash-table 0))
465
466 (defun <font color="#0000CC">print-hash-table</font> (hash-table)
467 (if (not (arrayp hash-table))
468 (format t <font color="#880000">";; Not an array: ~s~%"</font> hash-table)
469 (dotimes (index (length hash-table))
470 (let ((element (aref hash-table index)))
471 (cond ((not (listp element))
472 (format t <font color="#880000">";; array element ~a: ~s~%"</font> index element))
473 ((null element)
474 (format t <font color="#880000">";; bucket ~a: ()~%"</font> index))
475 (t
476 (format t <font color="#880000">";; bucket ~a:~%"</font> index)
477 (let ((entry-counter 1))
478 (dolist (entry element)
479 (format t <font color="#880000">";; ~a.~a: ~s~%"</font> index entry-counter entry)
480 (incf entry-counter)))))))))
481 </pre>
482
483
484
485 <p><nobr>&nbsp;&nbsp;<a href="#top">Back to top</a></nobr></p>
486
487 <hr>
488
489 <a href="../start.htm">Nyquist / XLISP 2.0</a>&nbsp; -&nbsp;
490 <a href="../manual/contents.htm">Contents</a> |
491 <a href="../tutorials/tutorials.htm">Tutorials</a> |
492 <a href="examples.htm">Examples</a> |
493 <a href="../reference/reference-index.htm">Reference</a>
494
495 </body></html>
496