|3.11. Hash Tables
They are so convenient that you will be quickly tempted to use them everywhere. However, keep in mind that a simple array requires less memory (about five times less) and less processor cycles than a hash table.
|3.11.0. Representing Associations with Hash Tables
A hash table maintains a set of associations between two lisp objects, namely a key and a value. This set is organized in a way that allows fast retrieval of the value associated to a given key.
Hash table queries search an association whose key is equal to the queried key. Since there are two ways to test equality (i.e. functions = and == ), there are two kinds of hash tables.
The most useful hash tables use the logical equality, as implemented by function = . Two objects are logically equal if they convey the same useful information. These hash table work properly as long as you do not modify the objects used as keys by the hash table. This can happen if you used arrays or custom objects as keys in your hash table. See the description of function htable-rehash for more information about this point.
Hash tables can also rely on pointer equality, as implemented by function == . These hash tables are useful to associate a piece of information with a particular lisp object. Functions getp and putp , for instance, make use of pointer-equality hash tables. The associations of a pointer-equality hash table are automatically removed when the key object is deallocated.
|126.96.36.199. (htable [nelem [flag]])
Argument nelem specifies an estimate of the number of elements in the hash table. This estimate is useful for saving a few processor cycles when filling the table.
Argument flag is a boolean value specifying whether the hash table will use logical equality (the default) or pointer equality (when argument flag is not nil.)
|188.8.131.52. (htable key)
|184.108.40.206. (htable key value)
This operation is performed in two logical steps: (a) any existing association matching key key is first deleted, and (b) a new association is created if argument value is not the empty list.
? (setq a (htable)) = ::HTABLE:6f3cac ? (a 'hello "hi") = ::HTABLE:6f3cac ? (a '(3 4) "ho") = ::HTABLE:6f3cac ? (a 'hello) = "hi" ? (a '(3 4 5)) = () ? (a '(3 4)) = "ho"
|220.127.116.11. (htable-size htable)
|18.104.22.168. (htable-keys htable)
? (setq a (htable)) = ::HTABLE:6f43c ? (for (i 0 10) (a i (sqrt i)) = ::HTABLE:6f43c ? (htable-keys a) = (7 6 3 10 5 9 8 4 2 0 1)
|22.214.171.124. (htable-alist htable)
? (setq a (htable)) = ::HTABLE:6f43c ? (for (i 0 10) (a i (sqrt i)) = ::HTABLE:6f43c ? (each (((key . value) (htable-alist a))) (printf "%4d %6.4f\n" key value)))) 7 2.6458 6 2.4495 3 1.7321 10 3.1623 5 2.2361 9 3.0000 8 2.8284 4 2.0000 2 1.4142 0 0.0000 1 1.0000 = ()
|126.96.36.199. (htable-rehash htable)
Hash table queries search an association whose key is logically equal to the queried key (unless pointer equality was specified when creating the hash table). The hash table works by storing each association in locations depending on the information conveyed by the key objects.
Modifying the object used as a key creates a lot of problems. The corresponding association is no longer stored in a location corresponding to the new information conveyed by the key objects. The hash table state is no longer consistent.
Function htable-rehash triggers the
relocation of all associations of the hash table
htable to the location corresponding to the new values of the
key objects. You can then reliably use the hash table again.
? (setq a (htable)) = ::HTABLE:6f32c ? (setq m [1 2]) = [1 2] ? (a m 3) = ::HTABLE:6f32c ? (a [1 2]) = 3 ? (m 0 0) = [ 0.00 2.00 ] ? (a [1 2]) = () ;; we lost it ? (a [0 2]) = () ;; result is undefined ? (htable-rehash a) = 1 ? (a [0 2]) = 3 ;; entry is no longer lost ? (a [1 2]) = () ;; this key no longer existsThe relocation of the hash table entries actually happens when you first access the hash table after calling htable-rehash . You can call function htable-rehash several times in a row. The cost of relocating all the hash table entries will be only incurred once when you will access the hash table again.
|188.8.131.52. (htable-info htable)
((size . 1294) (buckets . 3841) (hits 1132 145 14 3))In this example, the hash table contains 1294 associations. Associations are stored into 3841 buckets. Out of the 1294 associations, 1132 canbe retrieved directly, 145 require one extra search iteration, 14 require two extra search iteration, etc.
|3.11.1. Representing Sets with Hash Tables
Other functions given in this section perform additional operations on sets represented by hash tables.
|184.108.40.206. (hset eltlist [flag])
Argument flag is a boolean value specifying whether or not the hash table will maintain a count as the value of the same elements encountered when building the hash table (as opposed to t when flag is nil ). By default, flag is nil .
These counts can be useful for performing statistics or other
? (setq a (hset '(1 2 3 4 5 4 3 2 1 5 4 2 6) t )) = ::HTABLE:6f43c ? (each (((elem . value) (htable-alist a))) (printf "%4d %4d\n" elem value)))) 4 3 2 3 1 2 6 1 3 2 5 2 = ()
|220.127.116.11. (hset-and htable1 htable2)
? (htable-keys (hset-and (hset '(1 2 3 4)) (hset '(2 4 5 6)))) = (4 2)
|18.104.22.168. (hset-or htable1 htable2)
? (htable-keys (hset-or (hset '(1 2 3 4)) (hset '(2 4 5 6)))) = (4 2 1 6 3 5)