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:
- provides a mapping from some set of keys to some set of values associated to those keys
- has no intrinsic order for the (key, value) associations it contains
- supports in-place modification as the primary means of setting the contents of a hash table
- provides key lookup and destructive update in amortised constant time, provided that a good hash function is used
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?.