Next: , Previous: Hash Tables, Up: Hash Tables

11.4.1 Construction of Hash Tables

The next few procedures are hash-table constructors. All hash table constructors are procedures that accept one optional argument, initial-size, and return a newly allocated hash table. If initial-size is given, it must be an exact non-negative integer or #f. The meaning of initial-size is discussed below (see Resizing of Hash Tables).

Hash tables are normally characterized by two things: the equivalence predicate that is used to compare keys, and whether or not the table allows its keys to be reclaimed by the garbage collector. If a table prevents its keys from being reclaimed by the garbage collector, it is said to hold its keys strongly; otherwise it holds its keys weakly (see Weak Pairs).

— procedure: make-eq-hash-table [initial-size]

Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with eq?. The keys are held weakly. These are the fastest of the standard hash tables.

— procedure: make-eqv-hash-table [initial-size]

Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with eqv?. The keys are held weakly, except that booleans, characters, and numbers are held strongly. These hash tables are a little slower than those made by make-eq-hash-table.

— procedure: make-equal-hash-table [initial-size]

Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with equal?. The keys are held strongly. These hash tables are quite a bit slower than those made by make-eq-hash-table.

— procedure: make-string-hash-table [initial-size]

Returns a newly allocated hash table that accepts character strings as keys, and compares them with string=?. The keys are held strongly.

The next two procedures are used to create new hash-table constructors. All of the above hash table constructors, with the exception of make-eqv-hash-table, could have been created by calls to these “constructor-constructors”; see the examples below.

— procedure: strong-hash-table/constructor key-hash key=? [rehash-after-gc?]
— procedure: weak-hash-table/constructor key-hash key=? [rehash-after-gc?]

Each of these procedures accepts two arguments and returns a hash-table constructor. The key=? argument is an equivalence predicate for the keys of the hash table. The key-hash argument is a procedure that computes a hash number. Specifically, key-hash 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.

The optional argument rehash-after-gc?, if true, says that 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 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.

The constructors returned by strong-hash-table/constructor make hash tables that hold their keys strongly. The constructors returned by weak-hash-table/constructor make hash tables that hold their keys weakly.

Some examples showing how some standard hash-table constructors could have been defined: 

     (define make-eq-hash-table
       (weak-hash-table/constructor eq-hash-mod eq? #t))
     
     (define make-equal-hash-table
       (strong-hash-table/constructor equal-hash-mod equal? #t))
     
     (define make-string-hash-table
       (strong-hash-table/constructor string-hash-mod string=? #f))

The following procedure is sometimes useful in conjunction with weak hash tables. Normally it is not needed, because such hash tables clean themselves automatically as they are used.

— procedure: hash-table/clean! hash-table

If hash-table is a type of hash table that holds its keys weakly, this procedure recovers any space that was being used to record associations for objects that have been reclaimed by the garbage collector. Otherwise, this procedure does nothing. In either case, it returns an unspecified result.