SRFI 125: Intermediate hash tables

by John Cowan and Will Clinger

status: final (2016-05-28)

keywords: Data Structure, R7RS Large, R7RS Large: Red Edition

library name: hashtables

• The SRFI Document
• Discussion Archive
• Git repo (on GitHub)
• srfi-125@nospamsrfi.schemers.org (subscribers only)
• Subscribe to srfi-125 mailing list

  daily digest?

• Unsubscribe from srfi-125 mailing list

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.
• 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).