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 pp.\ \pageref{section:Association Lists} and \pageref{:property_lists}.
  16
  17
  18 \begin{LIST}{1cm}
  19
  20   \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
  21   Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
  22
  23   \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})} \retval{Test function}
  24   used in \VAR{hash-table}.
  25
  26   \IT{(\FU*{MAKE-HASH-TABLE}
  27     \orGOO{\kwd{:test}\Goo{\kwd{\#'eq}\XOR \kwd{\#'eql}\XOR
  28         \kwd{\#'equal}}\DF{\kwd{eql}}\\
  29       \kwd{:size} \VAR{ size}\\
  30       \kwd{:rehash-size} \VAR{ rehash-size}\\
  31       \kwd{:rehash-threshold} \VAR{ rehash-threshold}}{\}})}
  32   Make a \retval{hash table}.
  33
  34   \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}})} Get
  35   Return \retval{object} with key \VAR{key} if any or \retval{\VAR{default}}
  36   otherwise; and \retvalii{\T} if found, \retvalii{\NIL}
  37   otherwise. \kwd{setf}able.
  38
  39   \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})}
  40   \retval{Number of entries} in \VAR{hash-table}.
  41
  42   \IT{(\FU*{REMHASH} \VAR{key} \VAR{hash-table})}
  43   Remove from \VAR{hash-table} entry with \VAR{key} and return
  44   \retval{\T} if it existed. Return \retval{\NIL} otherwise.
  45
  46   \IT{(\FU*{CLRHASH} \VAR{hash-table})}
  47   Empty \retval{\VAR{hash-table}}.
  48
  49   \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
  50   Iterate over \VAR{hash-table} calling \VAR{function} on \VAR{key}
  51   and \VAR{value}. Return \retval{\NIL}.
  52
  53   \IT{(\SF*{WITH-HASH-TABLE-ITERATOR} \VAR{name} \VAR{hash-table}
  54     \OPn{(\kwd{declare} \OPn{\VAR{decl}})} \OPn{form})}
  55   Return \retval{values of \VAR{form}s}. In the body, successive
  56   invocations of  (\VAR{name}) return: \T\ if an entry is returned;
  57   its key; its value.
  58
  59   \IT{\arrGOO{(\FU*{HASH-TABLE-SIZE} \VAR{ hash-table})\\
  60       (\FU*{HASH-TABLE-REHASH-SIZE} \VAR{ hash-table})\\
  61       (\FU*{HASH-TABLE-REHASH-THRESHOLD} \VAR{ hash-table})}{\}}}
  62   Current \retval{size}, \retval{rehash-size}, or
  63   \retval{rehash-threshold}, resp., as used in \FU{make-hash-table}.
  64
  65   \IT{(\FU*{SXHASH} \VAR{foo})} \retval{Hash code} of \VAR{foo}.
  66
  67 \end{LIST}
  68
  69