SRFI 69 - Basic hash tables

The (srfi 69) library defines basic hash tables.

Hash tables are widely recognised as a fundamental data structure for a wide variety of applications. A hash table is a data structure that:

See the SRFI document for more information.

Limitations

Hash table size must be strictly less than 536,870,909.

The default implementation of record hashing is severely suboptimal - if you want to store records in a hash table, use a custom hashing function.

This implementation does not distinguish hash and hash-by-identity. Additionally, symbol hashing is done by string-hashing the result of symbol->string on the symbol, making symbols identical to strings for the purpose of hash table key performance.

Type constructors and predicate

make-hash-table hash-table? alist->hash-table

Reflective queries

hash-table-equivalence-function hash-table-hash-function

Dealing with single elements

hash-table-ref hash-table-ref/default hash-table-set! hash-table-delete! hash-table-exists? hash-table-update! hash-table-update!/default

Dealing with the whole contents

hash-table-size hash-table-keys hash-table-values hash-table-walk hash-table-fold hash-table->alist hash-table-copy hash-table-merge!

Hashing

hash string-hash string-ci-hash hash-by-identity

make-hash-table

(make-hash-table)

(make-hash-table equal?)

(make-hash-table equal? hash)

(make-hash-table equal? hash size)

Create a new hash table.

hash-table?

(hash-table? obj)

Determine if the given object is a hash table.

alist->hash-table

(alist->hash-table alist)

(alist->hash-table alist equal?)

(alist->hash-table alist equal? hash)

Convert given association list to a hash table.

hash-table-equivalence-function

(hash-table-equivalence-function hash-table)

Returns the equivalence predicate used for keys of hash-table.

hash-table-hash-function

(hash-table-hash-function hash-table)

Returns the hash function used for keys of hash-table.

hash-table-ref

(hash-table-ref hash-table key)

(hash-table-ref hash-table key thunk)

This procedure returns the value associated to key in hash-table. If no value is associated to key and thunk is given, it is called with no arguments and its value is returned.

hash-table-ref/default

(hash-table-ref/default hash-table key default)

Return the value associated to key in the hash table, or default if the key is not found.

hash-table-set!

(hash-table-set! hash-table key value)

Sets the value associated to key in the given hash table.

hash-table-delete!

(hash-table-delete! hash-table key)

Removes any value association for key in the given hash table.

hash-table-exists?

(hash-table-exists? hash-table key)

Determines if the given key exists in the hash table.

hash-table-update!

(hash-table-update! hash-table key function)

(hash-table-update! hash-table key function thunk)

hash-table-update!/default

(hash-table-update!/default hash-table key function default)

hash-table-size

(hash-table-size hash-table)

Return the number of associations in the hash table.

hash-table-keys

(hash-table-keys hash-table)

Return a list of keys in the hash table.

hash-table-values

(hash-table-values hash-table)

Return a list of values in the hash table.

hash-table-walk

(hash-table-walk hash-table proc)

proc should be a function taking two arguments, a key and a value. This procedure calls proc for each association in hash-table, giving the key of the association as key and the value of the association as value. The results of proc are discarded.

hash-table-fold

(hash-table-fold hash-table f init-value)

This procedure calls f for every association in hash-table with three arguments: the key of the association key, the value of the association value, and an accumulated value, val. val is init-value for the first invocation of f, and for subsequent invocations of f, the return value of the previous invocation of f. The value final-value returned by hash-table-fold is the return value of the last invocation of f.

hash-table->alist

(hash-table->alist hash-table)

Return an association list using the keys and values from the hash table.

hash-table-copy

(hash-table-copy hash-table)

Return a new hash table with the same data as the original.

hash-table-merge!

(hash-table-merge! hash-table1 hash-table2)

Adds all mappings in hash-table2 into hash-table1 and returns the resulting hash table.

hash

(hash object)

(hash object bound)

Return a hash value for object in the range 0 to bound.

string-hash

(string-hash string)

(string-hash string bound)

Same as hash except the argument must be a string.

string-ci-hash

(string-ci-hash string)

(string-ci-hash string bound)

Case insensitive version of string-hash.

hash-by-identity

(hash-by-identity object)

(hash-by-identity object bound)

The same as hash, except that this function is only guaranteed to be acceptable for eq?.