git.chise.org Git - chise/xemacs-chise.git-/blob - man/lispref/hash-tables.texi

   1 @c -*-texinfo-*-
   2 @c This is part of the XEmacs Lisp Reference Manual.
   3 @c Copyright (C) 1996 Ben Wing.
   4 @c See the file lispref.texi for copying conditions.
   5 @setfilename ../../info/hash-tables.info
   6 @node Hash Tables, Range Tables, Display, top
   7 @chapter Hash Tables
   8 @cindex hash table
   9
  10 @defun hashtablep object
  11 This function returns non-@code{nil} if @var{object} is a hash table.
  12 @end defun
  13
  14 @menu
  15 * Introduction to Hash Tables:: Hash tables are fast data structures for
  16                                 implementing simple tables (i.e. finite
  17                                 mappings from keys to values).
  18 * Working With Hash Tables::    Hash table functions.
  19 * Weak Hash Tables::            Hash tables with special garbage-collection
  20                                 behavior.
  21 @end menu
  22
  23 @node Introduction to Hash Tables
  24 @section Introduction to Hash Tables
  25
  26 A hash table is a data structure that provides mappings from
  27 arbitrary Lisp objects (called @dfn{keys}) to other arbitrary Lisp
  28 objects (called @dfn{values}).  There are many ways other than
  29 hash tables of implementing the same sort of mapping, e.g.
  30 association lists (@pxref{Association Lists}) and property lists
  31 (@pxref{Property Lists}), but hash tables provide much faster lookup.
  32
  33 When you create a hash table, you specify a size, which indicates the
  34 expected number of elements that the table will hold.  You are not
  35 bound by this size, however; hash tables automatically resize themselves
  36 if the number of elements becomes too large.
  37
  38 (Internally, hash tables are hashed using a modification of the
  39 @dfn{linear probing} hash table method.  This method hashes each
  40 key to a particular spot in the hash table, and then scans forward
  41 sequentially until a blank entry is found.  To look up a key, hash
  42 to the appropriate spot, then search forward for the key until either
  43 a key is found or a blank entry stops the search.  The modification
  44 actually used is called @dfn{double hashing} and involves moving forward
  45 by a fixed increment, whose value is computed from the original hash
  46 value, rather than always moving forward by one.  This eliminates
  47 problems with clustering that can arise from the simple linear probing
  48 method.  For more information, see @cite{Algorithms} (second edition)
  49 by Robert Sedgewick, pp. 236-241.)
  50
  51 @defun make-hashtable size &optional test-fun
  52 This function makes a hash table of initial size @var{size}.  Comparison
  53 between keys is normally done with @code{eql}; i.e. two keys must be the
  54 same object to be considered equivalent.  However, you can explicitly
  55 specify the comparison function using @var{test-fun}, which must be
  56 one of @code{eq}, @code{eql}, or @code{equal}.
  57
  58 Note that currently, @code{eq} and @code{eql} are the same.  This will
  59 change when bignums are implemented.
  60 @end defun
  61
  62 @defun copy-hashtable old-table
  63 This function makes a new hash table which contains the same keys and
  64 values as the given table.  The keys and values will not themselves be
  65 copied.
  66 @end defun
  67
  68 @defun hashtable-fullness table
  69 This function returns number of entries in @var{table}.
  70 @end defun
  71
  72 @node Working With Hash Tables
  73 @section Working With Hash Tables
  74
  75 @defun puthash key val table
  76 This function hashes @var{key} to @var{val} in @var{table}.
  77 @end defun
  78
  79 @defun gethash key table &optional default
  80 This function finds the hash value for @var{key} in @var{table}.  If
  81 there is no corresponding value, @var{default} is returned (defaults to
  82 @code{nil}).
  83 @end defun
  84
  85 @defun remhash key table
  86 This function removes the hash value for @var{key} in @var{table}.
  87 @end defun
  88
  89 @defun clrhash table
  90 This function flushes @var{table}.  Afterwards, the hash table will
  91 contain no entries.
  92 @end defun
  93
  94 @defun maphash function table
  95 This function maps @var{function} over entries in @var{table}, calling
  96 it with two args, each key and value in the table.
  97 @end defun
  98
  99 @node Weak Hash Tables
 100 @section Weak Hash Tables
 101 @cindex hash table, weak
 102 @cindex weak hash table
 103
 104 A @dfn{weak hash table} is a special variety of hash table whose
 105 elements do not count as GC referents.  For any key-value pair in such a
 106 hash table, if either the key or value (or in some cases, if one
 107 particular one of the two) has no references to it outside of weak hash
 108 tables (and similar structures such as weak lists), the pair will be
 109 removed from the table, and the key and value collected.  A non-weak
 110 hash table (or any other pointer) would prevent the objects from being
 111 collected.
 112
 113 Weak hash tables are useful for keeping track of information in a
 114 non-obtrusive way, for example to implement caching.  If the cache
 115 contains objects such as buffers, markers, image instances, etc. that
 116 will eventually disappear and get garbage-collected, using a weak hash
 117 table ensures that these objects are collected normally rather than
 118 remaining around forever, long past their actual period of use.
 119 (Otherwise, you'd have to explicitly map over the hash table every so
 120 often and remove unnecessary elements.)
 121
 122 There are three types of weak hash tables:
 123
 124 @table @asis
 125 @item fully weak hash tables
 126 In these hash tables, a pair disappears if either the key or the value
 127 is unreferenced outside of the table.
 128 @item key-weak hash tables
 129 In these hash tables, a pair disappears if the key is unreferenced outside
 130 of the table, regardless of how the value is referenced.
 131 @item value-weak hash tables
 132 In these hash tables, a pair disappears if the value is unreferenced outside
 133 of the table, regardless of how the key is referenced.
 134 @end table
 135
 136 Also see @ref{Weak Lists}.
 137
 138 @defun make-weak-hashtable size &optional test-fun
 139 This function makes a fully weak hash table of initial size @var{size}.
 140 @var{test-fun} is as in @code{make-hashtable}.
 141 @end defun
 142
 143 @defun make-key-weak-hashtable size &optional test-fun
 144 This function makes a key-weak hash table of initial size @var{size}.
 145 @var{test-fun} is as in @code{make-hashtable}.
 146 @end defun
 147
 148 @defun make-value-weak-hashtable size &optional test-fun
 149 This function makes a value-weak hash table of initial size @var{size}.
 150 @var{test-fun} is as in @code{make-hashtable}.
 151 @end defun