mirror of
https://github.com/justinethier/cyclone.git
synced 2025-05-18 21:29:18 +02:00
221 lines
6 KiB
Markdown
221 lines
6 KiB
Markdown
# 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](http://srfi.schemers.org/srfi-69/srfi-69.html) 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`](#make-hash-table)
|
|
[`hash-table?`](#hash-table)
|
|
[`alist->hash-table`](#alist-hash-table)
|
|
|
|
## Reflective queries
|
|
[`hash-table-equivalence-function`](#hash-table-equivalence-function)
|
|
[`hash-table-hash-function`](#hash-table-hash-function)
|
|
|
|
## Dealing with single elements
|
|
[`hash-table-ref`](#hash-table-ref)
|
|
[`hash-table-ref/default`](#hash-table-refdefault)
|
|
[`hash-table-set!`](#hash-table-set)
|
|
[`hash-table-delete!`](#hash-table-delete)
|
|
[`hash-table-exists?`](#hash-table-exists)
|
|
[`hash-table-update!`](#hash-table-update)
|
|
[`hash-table-update!/default`](#hash-table-updatedefault)
|
|
|
|
## Dealing with the whole contents
|
|
[`hash-table-size`](#hash-table-size)
|
|
[`hash-table-keys`](#hash-table-keys)
|
|
[`hash-table-values`](#hash-table-values)
|
|
[`hash-table-walk`](#hash-table-walk)
|
|
[`hash-table-fold`](#hash-table-fold)
|
|
[`hash-table->alist`](#hash-table-alist)
|
|
[`hash-table-copy`](#hash-table-copy)
|
|
[`hash-table-merge!`](#hash-table-merge)
|
|
|
|
## Hashing
|
|
[`hash`](#hash)
|
|
[`string-hash`](#string-hash)
|
|
[`string-ci-hash`](#string-ci-hash)
|
|
[`hash-by-identity`](#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?`.
|
|
|