doc/lispref/hash.texi

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