Go to the previous, next section.

Low-Level Hash Table Operations

The procedures in this section allow the programmer to control some of the internal structure of a hash table. Normally, hash tables maintain associations between keys and datums using pairs or weak pairs. These procedures allow the programmer to specify the use of some other data structure to maintain the association. In this section, the data structure that represents an association in a hash table is called an entry.

procedure+: hash-table/constructor key-hash key=? make-entry entry-valid? entry-key entry-datum set-entry-datum! [rehash-after-gc?]

Creates and returns a hash-table constructor procedure (see section Construction of Hash Tables). The arguments to hash-table/constructor define the characteristics of the hash table as follows:

key-hash

The hashing procedure. A procedure that accepts two arguments, a key and an exact positive integer (the modulus), and returns an exact non-negative integer that is less than the modulus.

key=?

A equivalence predicate that accepts two keys and is true iff they are the same key. If this predicate is true of two keys, then key-hash must return the same value for each of these keys (given the same modulus in both cases).

make-entry

A procedure that accepts a key and a datum as arguments and returns a newly allocated entry.

entry-valid?

A procedure that accepts an entry and returns #f iff the entry's key has been reclaimed by the garbage collector. Instead of a procedure, this may be #t, which is equivalent to (lambda (entry) #t).

entry-key

A procedure that accepts an entry as an argument and returns the entry's key.

entry-datum

A procedure that accepts an entry as an argument and returns the entry's datum.

set-entry-datum!

A procedure that accepts an entry and an object as arguments, modifies the entry's datum to be the object, and returns an unspecified result.

rehash-after-gc?

An optional argument that, if true, says the values returned by key-hash might change after a garbage collection. If so, the hash-table implementation arranges for the table to be rehashed when necessary. (See section Address Hashing, for information about hash procedures that have this property.) Otherwise, it is assumed that key-hash always returns the same value for the same arguments. The default value of this argument is #f.

For example, here is how the constructors for ordinary hash tables could be defined:

(define (strong-hash-table/constructor key-hash key=?
                                       #!optional rehash-after-gc?)
  (hash-table/constructor key-hash key=? cons #t car cdr set-cdr!
                          (if (default-object? rehash-after-gc?)
                              #f
                              rehash-after-gc?)))

(define (weak-hash-table/constructor key-hash key=?
                                     #!optional rehash-after-gc?)
  (hash-table/constructor key-hash key=? weak-cons weak-pair/car?
                          weak-car weak-cdr weak-set-cdr!
                          (if (default-object? rehash-after-gc?)
                              #f
                              rehash-after-gc?)))

procedure+: hash-table/key-hash hash-table

procedure+: hash-table/key=? hash-table

procedure+: hash-table/make-entry hash-table

procedure+: hash-table/entry-valid? hash-table

procedure+: hash-table/entry-key hash-table

procedure+: hash-table/entry-datum hash-table

procedure+: hash-table/set-entry-datum! hash-table

Each of these procedures corresponds to an argument of hash-table/constructor. When called, each procedure returns the value of the corresponding argument that was used to construct hash-table.

The following procedures return the contents of a hash table as a collection of entries. While the data structure holding the entries is newly allocated, the entries themselves are not copied. Since hash table operations can modify these entries, the entries should be copied if it is desired to keep them while continuing to modify the table.

procedure+: hash-table/entries-list hash-table

Returns a newly allocated list of the entries in hash-table.

procedure+: hash-table/entries-vector hash-table

Returns a newly allocated vector of the entries in hash-table. Equivalent to

(list->vector (hash-table/entries-list hash-table))

Go to the previous, next section.