lispref/hash.texi

   1 @c -*-texinfo-*-
   2 @c This is part of the GNU Emacs Lisp Reference Manual.
   3 @c Copyright (C) 1999 Free Software Foundation, Inc.
   4 @c See the file elisp.texi for copying conditions.
   5 @setfilename ../info/hash
   6 @node Hash Tables, Symbols, Sequences Arrays Vectors, Top
   7 @chapter Hash Tables
   8 @cindex hash tables
   9
  10   A hash table is a very fast kind of lookup table, somewhat like
  11 an alist in that it maps keys to corresponding values.  It differs
  12 from an alist in these ways:
  13
  14 @itemize @bullet
  15 @item
  16 Lookup in a hash table is extremely fast for large tables---in fact, the
  17 time required is essentially @emph{independent} of how many elements are
  18 stored in the table.  For smaller tables (a few tens of elements)
  19 alists may still be faster because hash tables have a more-or-less
  20 constant overhead.
  21
  22 @item
  23 The correspondences in a hash table are in no particular order.
  24
  25 @item
  26 There is no way to share structure between two hash tables,
  27 the way two alists can share a common tail.
  28 @end itemize
  29
  30   Emacs Lisp (starting with Emacs 21) provides a general-purpose hash
  31 table data type, along with a series of functions for operating on them.
  32 Hash tables have no read syntax, and print in hash notation, like this:
  33
  34 @example
  35 (make-hash-table)
  36      @result{} #<hash-table 'eql nil 0/65 0x83af980>
  37 @end example
  38
  39 @noindent
  40 (The term ``hash notation'' refers to the initial @samp{#}
  41 character---@pxref{Printed Representation}---and has nothing to do with
  42 the term ``hash table.'')
  43
  44   Obarrays are also a kind of hash table, but they are a different type
  45 of object and are used only for recording interned symbols
  46 (@pxref{Creating Symbols}).
  47
  48 @menu
  49 * Creating Hash::
  50 * Hash Access::
  51 * Defining Hash::
  52 * Other Hash::
  53 @end menu
  54
  55 @node Creating Hash
  56 @section Creating Hash Tables
  57
  58   The principal function for creating a hash table is
  59 @code{make-hash-table}.
  60
  61 @tindex make-hash-table
  62 @defun make-hash-table &rest keyword-args
  63 This function creates a new hash table according to the specified
  64 arguments.  The arguments should consist of alternating keywords
  65 (particular symbols recognized specially) and values corresponding to
  66 them.
  67
  68 Several keywords make sense in @code{make-hash-table}, but the only two
  69 that you really need to know about are @code{:test} and @code{:weakness}.
  70
  71 @table @code
  72 @item :test @var{test}
  73 This specifies the method of key lookup for this hash table.  The
  74 default is @code{eql}; @code{eq} and @code{equal} are other
  75 alternatives:
  76
  77 @table @code
  78 @item eql
  79 Keys which are numbers are ``the same'' if they are equal in value;
  80 otherwise, two distinct objects are never ``the same''.
  81
  82 @item eq
  83 Any two distinct Lisp objects are ``different'' as keys.
  84
  85 @item equal
  86 Two Lisp objects are ``the same'', as keys, if they are equal
  87 according to @code{equal}.
  88 @end table
  89
  90 You can use @code{define-hash-table-test} (@pxref{Defining Hash}) to
  91 define additional possibilities for @var{test}.
  92
  93 @item :weakness @var{weak}
  94 The weakness of a hash table specifies whether the presence of a key or
  95 value in the hash table preserves it from garbage collection.
  96
  97 The value, @var{weak}, must be one of @code{nil}, @code{key},
  98 @code{value}, @code{key-or-value}, @code{key-and-value}, or @code{t}
  99 which is an alias for @code{key-and-value}.  If @var{weak} is @code{key}
 100 then the hash table does not prevent its keys from being collected as
 101 garbage (if they are not referenced anywhere else); if a particular key
 102 does get collected, the corresponding association is removed from the
 103 hash table.
 104
 105 If @var{weak} is @code{value}, then the hash table does not prevent
 106 values from being collected as garbage (if they are not referenced
 107 anywhere else); if a particular value does get collected, the
 108 corresponding association is removed from the hash table.
 109
 110 If @var{weak} is @code{key-or-value} or @code{t}, the hash table does
 111 not protect either keys or values from garbage collection; if either
 112 one is collected as garbage, the association is removed.
 113
 114 If @var{weak} is @code{key-and-value}, associations are removed from
 115 the hash table when both their key and value would be collected as
 116 garbage, again not considering references to the key and value from
 117 weak hash tables.
 118
 119 The default for @var{weak} is @code{nil}, so that all keys and values
 120 referenced in the hash table are preserved from garbage collection.  If
 121 @var{weak} is @code{t}, neither keys nor values are protected (that is,
 122 both are weak).
 123
 124 @item :size @var{size}
 125 This specifies a hint for how many associations you plan to store in the
 126 hash table.  If you know the approximate number, you can make things a
 127 little more efficient by specifying it this way.  If you specify too
 128 small a size, the hash table will grow automatically when necessary, but
 129 doing that takes some extra time.
 130
 131 The default size is 65.
 132
 133 @item :rehash-size @var{rehash-size}
 134 When you add an association to a hash table and the table is ``full,''
 135 it grows automatically.  This value specifies how to make the hash table
 136 larger, at that time.
 137
 138 If @var{rehash-size} is an integer, it should be positive, and the hash
 139 table grows by adding that much to the nominal size.  If
 140 @var{rehash-size} is a floating point number, it had better be greater
 141 than 1, and the hash table grows by multiplying the old size by that
 142 number.
 143
 144 The default value is 1.5.
 145
 146 @item :rehash-threshold @var{threshold}
 147 This specifies the criterion for when the hash table is ``full.''  The
 148 value, @var{threshold}, should be a positive floating point number, no
 149 greater than 1.  The hash table is ``full'' whenever the actual number of
 150 entries exceeds this fraction of the nominal size.  The default for
 151 @var{threshold} is 0.8.
 152 @end table
 153 @end defun
 154
 155 @tindex makehash
 156 @defun makehash &optional test
 157 This is equivalent to @code{make-hash-table}, but with a different style
 158 argument list.  The argument @var{test} specifies the method
 159 of key lookup.
 160
 161 If you want to specify other parameters, you should use
 162 @code{make-hash-table}.
 163 @end defun
 164
 165 @node Hash Access
 166 @section Hash Table Access
 167
 168   This section describes the functions for accessing and storing
 169 associations in a hash table.
 170
 171 @tindex gethash
 172 @defun gethash key table &optional default
 173 This function looks up @var{key} in @var{table}, and returns its
 174 associated @var{value}---or @var{default}, if @var{key} has no
 175 association in @var{table}.
 176 @end defun
 177
 178 @tindex puthash
 179 @defun puthash key value table
 180 This function enters an association for @var{key} in @var{table}, with
 181 value @var{value}.  If @var{key} already has an association in
 182 @var{table}, @var{value} replaces the old associated value.
 183 @end defun
 184
 185 @tindex remhash
 186 @defun remhash key table
 187 This function removes the association for @var{key} from @var{table}, if
 188 there is one.  If @var{key} has no association, @code{remhash} does
 189 nothing.
 190 @end defun
 191
 192 @tindex clrhash
 193 @defun clrhash table
 194 This function removes all the associations from hash table @var{table},
 195 so that it becomes empty.  This is also called @dfn{clearing} the hash
 196 table.
 197 @end defun
 198
 199 @tindex maphash
 200 @defun maphash function table
 201 This function calls @var{function} once for each of the associations in
 202 @var{table}.  The function @var{function} should accept two
 203 arguments---a @var{key} listed in @var{table}, and its associated
 204 @var{value}.
 205 @end defun
 206
 207 @node Defining Hash
 208 @section Defining Hash Comparisons
 209 @cindex hash code
 210
 211   You can define new methods of key lookup by means of
 212 @code{define-hash-table-test}.  In order to use this feature, you need
 213 to understand how hash tables work, and what a @dfn{hash code} means.
 214
 215   You can think of a hash table conceptually as a large array of many
 216 slots, each capable of holding one association.  To look up a key,
 217 @code{gethash} first computes an integer, the hash code, from the key.
 218 It reduces this integer modulo the length of the array, to produce an
 219 index in the array.  Then it looks in that slot, and if necessary in
 220 other nearby slots, to see if it has found the key being sought.
 221
 222   Thus, to define a new method of key lookup, you need to specify both a
 223 function to compute the hash code from a key, and a function to compare
 224 two keys directly.
 225
 226 @tindex define-hash-table-test
 227 @defun define-hash-table-test name test-fn hash-fn
 228 This function defines a new hash table test, named @var{name}.
 229
 230 After defining @var{name} in this way, you can use it as the @var{test}
 231 argument in @code{make-hash-table}.  When you do that, the hash table
 232 will use @var{test-fn} to compare key values, and @var{hash-fn} to compute
 233 a ``hash code'' from a key value.
 234
 235 The function @var{test-fn} should accept two arguments, two keys, and
 236 return non-@code{nil} if they are considered ``the same.''
 237
 238 The function @var{hash-fn} should accept one argument, a key, and return
 239 an integer that is the ``hash code'' of that key.  For good results, the
 240 function should use the whole range of integer values for hash codes,
 241 including negative integers.
 242
 243 The specified functions are stored in the property list of @var{name}
 244 under the property @code{hash-table-test}; the property value's form is
 245 @code{(@var{test-fn} @var{hash-fn})}.
 246 @end defun
 247
 248 @tindex sxhash
 249 @defun sxhash obj
 250 This function returns a hash code for Lisp object @var{obj}.
 251 This is an integer which reflects the contents of @var{obj}
 252 and the other Lisp objects it points to.
 253
 254 If two objects @var{obj1} and @var{obj2} are equal, then @code{(sxhash
 255 @var{obj1})} and @code{(sxhash @var{obj2})} are the same integer.
 256
 257 If the two objects are not equal, the values returned by @code{sxhash}
 258 are usually different, but not always; but once in a rare while, by
 259 luck, you will encounter two distinct-looking objects that give the same
 260 result from @code{sxhash}.
 261 @end defun
 262
 263   This example creates a hash table whose keys are strings that are
 264 compared case-insensitively.
 265
 266 @example
 267 (defun case-fold-string= (a b)
 268   (compare-strings a nil nil b nil nil t))
 269
 270 (defun case-fold-string-hash (a)
 271   (sxhash (upcase a)))
 272
 273 (define-hash-table-test 'case-fold 'case-fold-string=
 274                         'case-fold-string-hash))
 275
 276 (make-hash-table :test 'case-fold)
 277 @end example
 278
 279   Here is how you could define a hash table test equivalent to the
 280 predefined test value @code{equal}.  The keys can be any Lisp object,
 281 and equal-looking objects are considered the same key.
 282
 283 @example
 284 (define-hash-table-test 'contents-hash 'equal 'sxhash)
 285
 286 (make-hash-table :test 'contents-hash)
 287 @end example
 288
 289 @node Other Hash
 290 @section Other Hash Table Functions
 291
 292   Here are some other functions for working with hash tables.
 293
 294 @tindex hash-table-p
 295 @defun hash-table-p table
 296 This returns non-@code{nil} if @var{table} is a hash table object.
 297 @end defun
 298
 299 @tindex copy-hash-table
 300 @defun copy-hash-table table
 301 This function creates and returns a copy of @var{table}.  Only the table
 302 itself is copied---the keys and values are shared.
 303 @end defun
 304
 305 @tindex hash-table-count
 306 @defun hash-table-count table
 307 This function returns the actual number of entries in @var{table}.
 308 @end defun
 309
 310 @tindex hash-table-test
 311 @defun hash-table-test table
 312 This returns the @var{test} value that was given when @var{table} was
 313 created, to specify how to hash and compare keys.  See
 314 @code{make-hash-table} (@pxref{Creating Hash}).
 315 @end defun
 316
 317 @tindex hash-table-weakness
 318 @defun hash-table-weakness table
 319 This function returns the @var{weak} value that was specified for hash
 320 table @var{table}.
 321 @end defun
 322
 323 @tindex hash-table-rehash-size
 324 @defun hash-table-rehash-size table
 325 This returns the rehash size of @var{table}.
 326 @end defun
 327
 328 @tindex hash-table-rehash-threshold
 329 @defun hash-table-rehash-threshold table
 330 This returns the rehash threshold of @var{table}.
 331 @end defun
 332
 333 @tindex hash-table-size
 334 @defun hash-table-size table
 335 This returns the current nominal size of @var{table}.
 336 @end defun