SRFI 69: Basic hash tables

by Panu Kalliokoski

status: final (2005-09-14)

keywords: Data Structure

See also SRFI 125: Intermediate hash tables and SRFI 126: R6RS-based hashtables.

library name: basic-hash-tables

Abstract

This SRFI 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:

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

This SRFI aims to accomplish these goals:

  1. to provide a consistent, generic and widely applicable API for hash tables
  2. to improve code portability by providing a standard hash table facility with guaranteed behaviour
  3. to help the programmer by defining utility routines that account for the most common situations of using hash tables.