6.7.14.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.

When the number of entries in a 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.

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 section 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 section Symbols as Lookup Keys), string-hash and string-hash-ci (see section String Comparison), and char-set-hash (see section Character Set Predicates/Comparison).

Scheme Procedure: make-hash-table [size]

Create a new 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)

Scheme Procedure: hash-count pred table

C Function: scm_hash_count (pred, table)

Return the number of elements in the given hash table that cause (pred key value) to return true. To quickly determine the total number of elements, use (const #t) for pred.

This document was generated on April 20, 2013 using texi2html 5.0.