SRFI 125: Intermediate hash tables
status: final (2016-05-28)
keywords: Data Structure, R7RS Large, R7RS Large: Red EditionSee also SRFI 69: Basic hash tables and SRFI 126: R6RS-based hashtables.
library name: hashtables
This SRFI defines an interface to hash tables, which are widely recognized as a fundamental data structure for a wide variety of applications. A hash table is a data structure that:
- Is disjoint from all other types.
- Provides a mapping from objects known as keys to corresponding objects known as values.
- Keys may be any Scheme objects in some kinds of hash tables, but are restricted in other kinds.
- Values may be any Scheme objects.
- Has no intrinsic order for the key-value associations it contains.
- Provides an equality predicate which defines when a proposed key is the same as an existing key. No table may contain more than one value for a given key.
- Provides a hash function which maps a candidate key into a non-negative exact integer.
- Supports mutation as the primary means of setting the contents of a table.
- Provides key lookup and destructive update in (expected) amortized constant time, provided a satisfactory hash function is available.
- Does not guarantee that whole-table operations work in the presence of concurrent mutation of the whole hash table (values may be safely mutated).