SRFI 250: Insertion-ordered hash tables
by John Cowan
status: draft (2023-11-14)
keywords: Data Structure
See also SRFI 69: Basic hash tables, SRFI 125: Intermediate hash tables, SRFI 126: R6RS-based hashtables, and SRFI 128: Comparators (reduced).
Abstract
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.
- 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 that 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.)
Unlike the hash tables of SRFI 125, which is the direct ancestor of this specification, the hash tables described here are ordered by insertion: that is, associations inserted earlier in the history of the hash table appear earlier in the ordering. Advances in the implementations of hash tables, as provided by C++, Python, JavaScript, etc., make the provision of this new facility practical. As a result, the hash tables of this SRFI do not interoperate with the hash tables of SRFI 125, SRFI 126, or existing R6RS implementations.