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 hash-table-p object
  11 This function returns @code{t} if @var{object} is a hash table, else @code{nil}.
  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 @dfn{hash table} is a data structure that provides mappings from
  27 arbitrary Lisp objects called @dfn{keys} to other arbitrary Lisp objects
  28 called @dfn{values}.  A key/value pair is sometimes called an
  29 @dfn{entry} in the hash table.  There are many ways other than hash
  30 tables of implementing the same sort of mapping, e.g.  association lists
  31 (@pxref{Association Lists}) and property lists (@pxref{Property Lists}),
  32 but hash tables provide much faster lookup when there are many entries
  33 in the mapping.  Hash tables are an implementation of the abstract data
  34 type @dfn{dictionary}, also known as @dfn{associative array}.
  35
  36 Internally, hash tables are hashed using the @dfn{linear probing} hash
  37 table implementation method.  This method hashes each key to a
  38 particular spot in the hash table, and then scans forward sequentially
  39 until a blank entry is found.  To look up a key, hash to the appropriate
  40 spot, then search forward for the key until either a key is found or a
  41 blank entry stops the search.  This method is used in preference to
  42 double hashing because of changes in recent hardware.  The penalty for
  43 non-sequential access to memory has been increasing, and this
  44 compensates for the problem of clustering that linear probing entails.
  45
  46 When hash tables are created, the user may (but is not required to)
  47 specify initial properties that influence performance.
  48
  49 Use the @code{:size} parameter to specify the number of entries that are
  50 likely to be stored in the hash table, to avoid the overhead of resizing
  51 the table.  But if the pre-allocated space for the entries is never
  52 used, it is simply wasted and makes XEmacs slower.  Excess unused hash
  53 table entries exact a small continuous performance penalty, since they
  54 must be scanned at every garbage collection.  If the number of entries
  55 in the hash table is unknown, simply avoid using the @code{:size}
  56 keyword.
  57
  58 Use the @code{:rehash-size} and @code{:rehash-threshold} keywords to
  59 adjust the algorithm for deciding when to rehash the hash table.  For
  60 temporary hash tables that are going to be very heavily used, use a
  61 small rehash threshold, for example, 0.4 and a large rehash size, for
  62 example 2.0.  For permanent hash tables that will be infrequently used,
  63 specify a large rehash threshold, for example 0.8.
  64
  65 Hash tables can also be created by the lisp reader using structure
  66 syntax, for example:
  67 @example
  68 #s(hash-table size 20 data (foo 1 bar 2))
  69 @end example
  70
  71 The structure syntax accepts the same keywords as @code{make-hash-table}
  72 (without the @code{:} character), as well as the additional keyword
  73 @code{data}, which specifies the initial hash table contents.
  74
  75 @defun make-hash-table &key @code{test} @code{size} @code{rehash-size} @code{rehash-threshold} @code{weakness}
  76 This function returns a new empty hash table object.
  77
  78 Keyword @code{:test} can be @code{eq}, @code{eql} (default) or @code{equal}.
  79 Comparison between keys is done using this function.
  80 If speed is important, consider using @code{eq}.
  81 When storing strings in the hash table, you will likely need to use @code{equal}.
  82
  83 Keyword @code{:size} specifies the number of keys likely to be inserted.
  84 This number of entries can be inserted without enlarging the hash table.
  85
  86 Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies
  87 the factor by which to increase the size of the hash table when enlarging.
  88
  89 Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0,
  90 and specifies the load factor of the hash table which triggers enlarging.
  91
  92 Non-standard keyword @code{:weakness} can be @code{nil} (default),
  93 @code{t}, @code{key-and-value}, @code{key}, @code{value} or
  94 @code{key-or-value}.  @code{t} is an alias for @code{key-and-value}.
  95
  96 A key-and-value-weak hash table, also known as a fully-weak or simply
  97 as a weak hash table, is one whose pointers do not count as GC
  98 referents: for any key-value pair in the hash table, if the only
  99 remaining pointer to either the key or the value is in a weak hash
 100 table, then the pair will be removed from the hash table, and the key
 101 and value collected.  A non-weak hash table (or any other pointer)
 102 would prevent the object from being collected.
 103
 104 A key-weak hash table is similar to a fully-weak hash table except that
 105 a key-value pair will be removed only if the key remains unmarked
 106 outside of weak hash tables.  The pair will remain in the hash table if
 107 the key is pointed to by something other than a weak hash table, even
 108 if the value is not.
 109
 110 A value-weak hash table is similar to a fully-weak hash table except
 111 that a key-value pair will be removed only if the value remains
 112 unmarked outside of weak hash tables.  The pair will remain in the
 113 hash table if the value is pointed to by something other than a weak
 114 hash table, even if the key is not.
 115
 116 A key-or-value-weak hash table is similar to a fully-weak hash table except
 117 that a key-value pair will be removed only if the value and the key remain
 118 unmarked outside of weak hash tables.  The pair will remain in the
 119 hash table if the value or key are pointed to by something other than a weak
 120 hash table, even if the other is not.
 121 @end defun
 122
 123 @defun copy-hash-table hash-table
 124 This function returns a new hash table which contains the same keys and
 125 values as @var{hash-table}.  The keys and values will not themselves be
 126 copied.
 127 @end defun
 128
 129 @defun hash-table-count hash-table
 130 This function returns the number of entries in @var{hash-table}.
 131 @end defun
 132
 133 @defun hash-table-test hash-table
 134 This function returns the test function of @var{hash-table}.
 135 This can be one of @code{eq}, @code{eql} or @code{equal}.
 136 @end defun
 137
 138 @defun hash-table-size hash-table
 139 This function returns the current number of slots in @var{hash-table},
 140 whether occupied or not.
 141 @end defun
 142
 143 @defun hash-table-rehash-size hash-table
 144 This function returns the current rehash size of @var{hash-table}.
 145 This is a float greater than 1.0; the factor by which @var{hash-table}
 146 is enlarged when the rehash threshold is exceeded.
 147 @end defun
 148
 149 @defun hash-table-rehash-threshold hash-table
 150 This function returns the current rehash threshold of @var{hash-table}.
 151 This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of
 152 @var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing.
 153 @end defun
 154
 155 @defun hash-table-weakness hash-table
 156 This function returns the weakness of @var{hash-table}.
 157 This can be one of @code{nil}, @code{t}, @code{key} or @code{value}.
 158 @end defun
 159
 160 @node Working With Hash Tables
 161 @section Working With Hash Tables
 162
 163 @defun puthash key value hash-table
 164 This function hashes @var{key} to @var{value} in @var{hash-table}.
 165 @end defun
 166
 167 @defun gethash key hash-table &optional default
 168 This function finds the hash value for @var{key} in @var{hash-table}.
 169 If there is no entry for @var{key} in @var{hash-table}, @var{default} is
 170 returned (which in turn defaults to @code{nil}).
 171 @end defun
 172
 173 @defun remhash key hash-table
 174 This function removes the entry for @var{key} from @var{hash-table}.
 175 Does nothing if there is no entry for @var{key} in @var{hash-table}.
 176 @end defun
 177
 178 @defun clrhash hash-table
 179 This function removes all entries from @var{hash-table}, leaving it empty.
 180 @end defun
 181
 182 @defun maphash function hash-table
 183 This function maps @var{function} over entries in @var{hash-table},
 184 calling it with two args, each key and value in the hash table.
 185
 186 @var{function} may not modify @var{hash-table}, with the one exception
 187 that @var{function} may remhash or puthash the entry currently being
 188 processed by @var{function}.
 189 @end defun
 190
 191
 192 @node Weak Hash Tables
 193 @section Weak Hash Tables
 194 @cindex hash table, weak
 195 @cindex weak hash table
 196
 197 A @dfn{weak hash table} is a special variety of hash table whose
 198 elements do not count as GC referents.  For any key-value pair in such a
 199 hash table, if either the key or value (or in some cases, if one
 200 particular one of the two) has no references to it outside of weak hash
 201 tables (and similar structures such as weak lists), the pair will be
 202 removed from the table, and the key and value collected.  A non-weak
 203 hash table (or any other pointer) would prevent the objects from being
 204 collected.
 205
 206 Weak hash tables are useful for keeping track of information in a
 207 non-obtrusive way, for example to implement caching.  If the cache
 208 contains objects such as buffers, markers, image instances, etc. that
 209 will eventually disappear and get garbage-collected, using a weak hash
 210 table ensures that these objects are collected normally rather than
 211 remaining around forever, long past their actual period of use.
 212 (Otherwise, you'd have to explicitly map over the hash table every so
 213 often and remove unnecessary elements.)
 214
 215 There are four types of weak hash tables:
 216
 217 @table @asis
 218 @item key-and-value-weak hash tables
 219 In these hash tables, also known as fully weak or simply as weak hash
 220 tables, a pair disappears if either the key or the value is unreferenced
 221 outside of the table.
 222 @item key-weak hash tables
 223 In these hash tables, a pair disappears if the key is unreferenced outside
 224 of the table, regardless of how the value is referenced.
 225 @item value-weak hash tables
 226 In these hash tables, a pair disappears if the value is unreferenced outside
 227 of the table, regardless of how the key is referenced.
 228 @item key-or-value-weak hash tables
 229 In these hash tables, a pair disappears if both the key and the value
 230 are unreferenced outside of the table.
 231 @end table
 232
 233 Also see @ref{Weak Lists}.
 234
 235 Weak hash tables are created by specifying the @code{:weakness} keyword to
 236 @code{make-hash-table}.