Previous: Hash Table Examples, Up: Hash Tables

5.6.12.2 Hash Table Reference

Like the association list functions, the hash table functions come in several varieties, according to the equality test used for the keys. Plain hash- functions use equal?, hashq- functions use eq?, hashv- functions use eqv?, and the hashx- functions use an application supplied test.

A single make-hash-table creates a hash table suitable for use with any set of functions, but it's imperative that just one set is then used consistently, or results will be unpredictable.

Hash tables are implemented as a vector indexed by a hash value formed from the key, with an association list of key/value pairs for each bucket in case distinct keys hash together. Direct access to the pairs in those lists is provided by the -handle- functions. The abstract kind of hash tables hide the vector in an opaque object that represents the hash table, while for the concrete kind the vector is the hashtable.

When the number of table entries in an abstract hash table goes above a threshold, the vector is made larger and the entries are rehashed, to prevent the bucket lists from becoming too long and slowing down accesses. When the number of entries goes below a threshold, the vector is shrunk to save space.

A abstract hash table is created with make-hash-table. To create a vector that is suitable as a hash table, use (make-vector size '()), for example.

For the hashx- “extended” routines, an application supplies a hash function producing an integer index like hashq etc below, and an assoc alist search function like assq etc (see Retrieving Alist Entries). Here's an example of such functions implementing case-insensitive hashing of string keys, 

     (use-modules (srfi srfi-1)
                  (srfi srfi-13))
     
     (define (my-hash str size)
       (remainder (string-hash-ci str) size))
     (define (my-assoc str alist)
       (find (lambda (pair) (string-ci=? str (car pair))) alist))
     
     (define my-table (make-hash-table))
     (hashx-set! my-hash my-assoc my-table "foo" 123)
     
     (hashx-ref my-hash my-assoc my-table "FOO")
     => 123

In a hashx- hash function the aim is to spread keys across the vector, so bucket lists don't become long. But the actual values are arbitrary as long as they're in the range 0 to size-1. Helpful functions for forming a hash value, in addition to hashq etc below, include symbol-hash (see Symbol Keys), string-hash and string-hash-ci (see String Comparison), and char-set-hash (see Character Set Predicates/Comparison).
— Scheme Procedure: make-hash-table [size]

Create a new abstract hash table object, with an optional minimum vector size.

When size is given, the table vector will still grow and shrink automatically, as described above, but with size as a minimum. If an application knows roughly how many entries the table will hold then it can use size to avoid rehashing when initial entries are added.

— Scheme Procedure: hash-table? obj
— C Function: scm_hash_table_p (obj)

Return #t if obj is a abstract hash table object.

— Scheme Procedure: hash-clear! table
— C Function: scm_hash_clear_x (table)

Remove all items from table (without triggering a resize).

— Scheme Procedure: hash-ref table key [dflt]
— Scheme Procedure: hashq-ref table key [dflt]
— Scheme Procedure: hashv-ref table key [dflt]
— Scheme Procedure: hashx-ref hash assoc table key [dflt]
— C Function: scm_hash_ref (table, key, dflt)
— C Function: scm_hashq_ref (table, key, dflt)
— C Function: scm_hashv_ref (table, key, dflt)
— C Function: scm_hashx_ref (hash, assoc, table, key, dflt)

Lookup key in the given hash table, and return the associated value. If key is not found, return dflt, or #f if dflt is not given.

— Scheme Procedure: hash-set! table key val
— Scheme Procedure: hashq-set! table key val
— Scheme Procedure: hashv-set! table key val
— Scheme Procedure: hashx-set! hash assoc table key val
— C Function: scm_hash_set_x (table, key, val)
— C Function: scm_hashq_set_x (table, key, val)
— C Function: scm_hashv_set_x (table, key, val)
— C Function: scm_hashx_set_x (hash, assoc, table, key, val)

Associate val with key in the given hash table. If key is already present then it's associated value is changed. If it's not present then a new entry is created.

— Scheme Procedure: hash-remove! table key
— Scheme Procedure: hashq-remove! table key
— Scheme Procedure: hashv-remove! table key
— Scheme Procedure: hashx-remove! hash assoc table key
— C Function: scm_hash_remove_x (table, key)
— C Function: scm_hashq_remove_x (table, key)
— C Function: scm_hashv_remove_x (table, key)
— C Function: scm_hashx_remove_x (hash, assoc, table, key)

Remove any association for key in the given hash table. If key is not in table then nothing is done.

— Scheme Procedure: hash key size
— Scheme Procedure: hashq key size
— Scheme Procedure: hashv key size
— C Function: scm_hash (key, size)
— C Function: scm_hashq (key, size)
— C Function: scm_hashv (key, size)

Return a hash value for key. This is a number in the range 0 to size-1, which is suitable for use in a hash table of the given size.

Note that hashq and hashv may use internal addresses of objects, so if an object is garbage collected and re-created it can have a different hash value, even when the two are notionally eq?. For instance with symbols, 

          (hashq 'something 123)   => 19
          (gc)
          (hashq 'something 123)   => 62

In normal use this is not a problem, since an object entered into a hash table won't be garbage collected until removed. It's only if hashing calculations are somehow separated from normal references that its lifetime needs to be considered.

— Scheme Procedure: hash-get-handle table key
— Scheme Procedure: hashq-get-handle table key
— Scheme Procedure: hashv-get-handle table key
— Scheme Procedure: hashx-get-handle hash assoc table key
— C Function: scm_hash_get_handle (table, key)
— C Function: scm_hashq_get_handle (table, key)
— C Function: scm_hashv_get_handle (table, key)
— C Function: scm_hashx_get_handle (hash, assoc, table, key)

Return the (key . value) pair for key in the given hash table, or #f if key is not in table.

— Scheme Procedure: hash-create-handle! table key init
— Scheme Procedure: hashq-create-handle! table key init
— Scheme Procedure: hashv-create-handle! table key init
— Scheme Procedure: hashx-create-handle! hash assoc table key init
— C Function: scm_hash_create_handle_x (table, key, init)
— C Function: scm_hashq_create_handle_x (table, key, init)
— C Function: scm_hashv_create_handle_x (table, key, init)
— C Function: scm_hashx_create_handle_x (hash, assoc, table, key, init)

Return the (key . value) pair for key in the given hash table. If key is not in table then create an entry for it with init as the value, and return that pair.

— Scheme Procedure: hash-map->list proc table
— Scheme Procedure: hash-for-each proc table
— C Function: scm_hash_map_to_list (proc, table)
— C Function: scm_hash_for_each (proc, table)

Apply proc to the entries in the given hash table. Each call is (proc key value). hash-map->list returns a list of the results from these calls, hash-for-each discards the results and returns an unspecified value.

Calls are made over the table entries in an unspecified order, and for hash-map->list the order of the values in the returned list is unspecified. Results will be unpredictable if table is modified while iterating.

For example the following returns a new alist comprising all the entries from mytable, in no particular order. 

          (hash-map->list cons mytable)
— Scheme Procedure: hash-for-each-handle proc table
— C Function: scm_hash_for_each_handle (proc, table)

Apply proc to the entries in the given hash table. Each call is (proc handle), where handle is a (key . value) pair. Return an unspecified value.

hash-for-each-handle differs from hash-for-each only in the argument list of proc.

— Scheme Procedure: hash-fold proc init table
— C Function: scm_hash_fold (proc, init, table)

Accumulate a result by applying proc to the elements of the given hash table. Each call is (proc key value prior-result), where key and value are from the table and prior-result is the return from the previous proc call. For the first call, prior-result is the given init value.

Calls are made over the table entries in an unspecified order. Results will be unpredictable if table is modified while hash-fold is running.

For example, the following returns a count of how many keys in mytable are strings. 

          (hash-fold (lambda (key value prior)
                       (if (string? key) (1+ prior) prior))
                     0 mytable)