Work in progress, do not use
This WG2 proposal 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:
I have added equivalences to SRFI 69 and R6RS facilities. Systems supporting either should be able to support these hash tables trivially; it will be necessary to write hash-table-fold for R6RS systems. I have adopted SRFI 69's term hash-table rather than R6RS's hashtable because of our decision in #40. Besides, the word hashtable obviously means something that can be ... hashted.
The main annoyances of this proposal for SRFI 69 programmers will be remembering to supply a third argument to hash-table-ref, and for R6RS programmers will be remembering to insert a hyphen in hashtable. Both will have to get used to the new constructors.
make-hash-table hash-table hash-table? hash-table-ref/default hash-table-ref hash-table-ref!/default hash-table-ref! hash-table-exists? hash-table-set! hash-table-set*! hash-table-delete! hash-table-delete hash-table-update!/default hash-table-update! hash-table-update, hash-table-update/default hash-table-clear! hash-table-length hash-table-keys hash-table-values hash-table-map->list hash-table-for-each hash-table-copy hash-table->alist alist->hash-table eq? support eqv? support equal? support string=? support string-ci=? support hash-table-push!, hash-table-pop! hash-table-find hash-table-accessor, hash-table-mutator, hash-table-deleter, hash-table-updater hash-table-union(!), hash-table-intersection(!), hash-table-difference(!) hash-table=?
These constructors provide suitable hash functions for the equivalence function specified as part of the constructor name. This proposal does not allow (semi-)arbitrary equivalence and hash functions to be specified.
(make-eq-hash-table)
Returns a newly allocated table with no associations whose equivalence function is eq?. (SRFI-69 (make-hash-table eq? hash-by-identity); R6RS (make-eq-hashtable))
(make-equal-hash-table)
Returns a newly allocated with no associations whose equivalence function is equal?. (SRFI-69 (make-hash-table equal? hash); R6RS (make-hashtable equal? equal-hash))
(make-string-hash-table)
Returns a newly allocated table with no associations whose equivalence function is string=?. (SRFI-69 (make-hash-table string=? string-hash); R6RS (make-hashtable string=? string-hash))
(make-string-ci-hash-table)
Returns a newly allocated table with no associations whose equivalence function is string-ci=?. (SRFI-69 (make-hash-table string-ci=? string-ci-hash); R6RS (make-hashtable string-ci=? string-ci-hash))
Note that there are no hash tables whose equivalence function is eqv?, because SRFI 69 does not support them. Users will have to live with eq? or equal? hash tables as the case may be.
Issue: add (hash-table-unfold ''p f g key-seed value-seed'')? Or possibly just one seed and let f generate the two values from a single value.
(hash-table-copy hash-table)
Returns a newly allocated hash table with the same equivalence predicate and associations as hash-table. (SRFI-69 hash-table-copy; R6RS (hashtable-copy hash-table #t))
(hash-table? obj)
Returns #t if obj is a hash table. (SRFI-69 hash-table?; R6RS hashtable?)
(hash-table-contains? hash-table key)
Returns #t if there is any association to key in hash-table. Must execute in amortized O(1) time. (SRFI-69 hash-table-exists?; R6RS hashtable-contains?)
(hash-table-ref hash-table key default-proc)
Returns the value associated to key in table. If no value is associated to key, default-proc is applied to no arguments and the result is returned. Must execute in amortized O(1) time, not counting the time to call default-proc if necessary. (SRFI-69 hash-table-ref/default; R6RS hashtable-ref)
(hash-table-size table)
Returns the number of associations in hash-table. Must execute in amortized O(1) time. (SRFI-69 hash-table-size; R6RS hashtable-size)
(hash-table-set! hash-table key value)
Creates a new association in hash-table that associates key with value. The previous association (if any) is removed. It is an error if hash-table is a string or string-ci hash table and key is not a string. Must execute in amortized O(1) time. Returns an unspecified value. (SRFI-69 hash-table-set!; R6RS hashtable-set!)
(hash-table-delete! hash-table key)
Removes any association to key in hash-table. It is not an error if no association for that key exists. Must execute in amortized O(1) time. Returns an unspecified value. (SRFI-69 hash-table-delete!; R6RS hashtable-delete!)
(hash-table-update! hash-table key procedure default-proc ])
Semantically equivalent to, but may be implemented more efficiently than, the following code:
(hash-table-set! hash-table key (procedure (hash-table-ref hash-table key default-proc)))
Must execute in amortized O(1) time. Returns an unspecified value. (SRFI-69 hash-table-update!/default; R6RS hashtable-update!)
Issue: add hash-table-clear?
(hash-table-fold procedure init hash-table)
Calls procedure for every association in hash-table with three arguments: the key of the association, the value of the association, and an accumulated value val. Val is init for the first invocation of procedure, and for subsequent invocations of procedure, the return value of the previous invocation. The value returned by hash-table-fold is the return value of the last invocation of f. The order in which procedure is called for different associations is unspecified. (SRFI-69 hash-table-fold; not in R6RS but trivially implemented: see below.)
The following features are not part of this proposal for various reasons.
Hash-table-keys is present in both SRFI 69 and R6RS, but returns a list of keys in the first, a vector of keys in the second.
Hash-table-values returns a list of values in SRFI 69; hashtable-entries returns two values, a vector of keys and a vector of values in R6RS.
Hash-table-hash-function always returns the hash function of a hash table in SRFI 69, but returns #f in the case of eq? (and eqv?) hash tables in R6RS.
Hash-table-equivalence-function returns the equivalence function, but in R6/R7RS you can't reliably check functions for identity, so you don't know what you've got.
Hashtable-clear!, which removes all associations from a hash table.
Specifying the initial capacity of a hash table.
Immutable hash tables.
Hash tables based on eqv?.
Hash-table-walk, which is the analogue of for-each for hash tables.
Conversion from a-lists to hash tables and back.
Hash-table-merge, which destructively adds all associations in a source hash table to a destination hash table.
Default values specified in the form of a thunk to call.
The current capacity (as opposed to size) of a hash table.
Rehash size and threshold.
Hash tables based on equalp (which is not in Scheme).
With-hash-table-iterator, a hash table external iterator implemented as a local macro.
Sxhash, a stable hash function.