clqr-hash-tables.tex

   1 % Copyright (C) 2008 Bert Burgemeister
   2 %
   3 % Permission is granted to copy, distribute and/or modify this
   4 % document under the terms of the GNU Free Documentation License,
   5 % Version 1.2 or any later version published by the Free Software
   6 % Foundation; with no Invariant Sections, no Front-Cover Texts and
   7 % no Back-Cover Texts. For details see file COPYING.
   8 %
   9
  10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  11 \section{Hash Tables}
  12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  13 Key-value storage similar to hash tables can as well be achieved using
  14 association lists and property lists; see
  15 pages \pageref{section:Association Lists} and \pageref{:property_lists}.
  16
  17
  18 \begin{LIST}{1cm}
  19
  20   \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
  21   {
  22   Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
  23   }
  24
  25   \IT{(\FU*{MAKE-HASH-TABLE}
  26     \orGOO{\kwd{:test}\Goo{\FU{eq}\XOR \FU{eql}\XOR
  27         \FU{equal}}\DF{\kwd{eql}}\\
  28       \kwd{:size} \VAR{ int}\\
  29       \kwd{:rehash-size} \VAR{ int}\\
  30       \kwd{:rehash-threshold} \VAR{ int}}{\}})}
  31   {
  32   Make a \retval{hash table}.
  33   }
  34
  35   \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})}
  36   {
  37   \retval{Test function} used in \VAR{hash-table}.
  38   }
  39
  40   \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}\DF{\NIL}})}
  41   {
  42   Return \retval{object} with \VAR{key} if any or \retval{\VAR{default}}
  43   otherwise; and \retvalii{\T} if found, \retvalii{\NIL}
  44   otherwise. \kwd{setf}able.
  45   }
  46
  47   \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})}
  48   {
  49   \retval{Number of entries} in \VAR{hash-table}.
  50   }
  51
  52   \IT{(\FU*{REMHASH} \VAR{key} \DES{\VAR{hash-table}})}
  53   {
  54   Remove from \VAR{hash-table} entry with \VAR{key} and return
  55   \retval{\T} if it existed. Return \retval{\NIL} otherwise.
  56   }
  57
  58   \IT{(\FU*{CLRHASH} \DES{\VAR{hash-table}})}
  59   {
  60   Empty \retval{\VAR{hash-table}}.
  61   }
  62
  63   \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
  64   {
  65   Iterate over \VAR{hash-table} calling \VAR{function} on key
  66   and value. Return \retval{\NIL}.
  67   }
  68
  69   \IT{(\MC*{WITH-HASH-TABLE-ITERATOR} (\VAR{foo} \VAR{hash-table})
  70     \OPn{(\kwd{declare} \OPn{\NEV{\VAR{decl}}})} \PROGN{\VAR{form}})}
  71   {
  72   Return \retval{values of \VAR{form}s}. In \VAR{form}s,
  73   invocations of  (\VAR{foo}) return: \T\ if an entry is returned;
  74   its key; its value.
  75   }
  76
  77   \IT{\arrGOO{(\FU*{HASH-TABLE-SIZE} \VAR{ hash-table})\\
  78       (\FU*{HASH-TABLE-REHASH-SIZE} \VAR{ hash-table})\\
  79       (\FU*{HASH-TABLE-REHASH-THRESHOLD} \VAR{ hash-table})}{.}}
  80   {
  81   Current \retval{size}, \retval{rehash-size}, or
  82   \retval{rehash-threshold}, respectively, as used in \FU{make-hash-table}.
  83   }
  84
  85   \IT{(\FU*{SXHASH} \VAR{foo})}
  86      {
  87        \retval{Hash code} unique for any argument \FU{equal} \VAR{foo}.
  88      }
  89
  90 \end{LIST}
  91
  92