Next: Basic Hash Table Operations, Previous: Hash Tables, Up: 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 how the table allows its keys and data to be reclaimed by the garbage collector. If a table prevents its keys and data from being reclaimed by the garbage collector, it is said to hold its keys and data strongly; other arrangements are possible, where a table may hold keys or data weakly or ephemerally (see Weak References).
Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with
eq?. The keys and data are held strongly. These are the fastest of the standard hash tables.
Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with
eq?. The keys are held weakly, but the data are held strongly. Note that if a datum holds a key strongly, the table will effectively hold that key strongly.
Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with
eq?. The keys are held weakly, even if some of the data should hold some of the keys strongly.
Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with
eqv?. The keys and data are held strongly. These hash tables are a little slower than those made bymake-strong-eq-hash-table.
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, numbers, and interned symbols are held strongly. The data are held strongly. Note that if a datum holds a key strongly, the table will effectively hold that key strongly.
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, numbers, and interned symbols are held strongly. The keys are effectively held weakly even if some of the data should hold some of the keys strongly.
Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with
equal?. The keys and data are held strongly. These hash tables are quite a bit slower than those made bymake-strong-eq-hash-table.
Returns a newly allocated hash table that accepts character strings as keys, and compares them with
string=?. The keys and data are held strongly.
The next procedure is used to create new hash-table constructors. All of the above hash table constructors could have been created by calls to this “constructor-constructor”; see the examples below.
This procedure accepts four 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 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 argument entry-type determines the strength with which the hash table will hold its keys and values. It must be one of
hash-table-entry-type:strong,hash-table-entry-type:key-weak,hash-table-entry-type:datum-weak,hash-table-entry-type:key/datum-weak,hash-table-entry-type:key-ephemeral,hash-table-entry-type:datum-ephemeral, orhash-table-entry-type:key&datum-ephemeral.
The entry type for hash tables that hold both keys and data strongly.
An entry type for hash tables that hold keys weakly and data strongly. An entry of this type is a weak pair (see Weak Pairs) whose weak (car) slot holds the key of the entry and whose strong (cdr) slot holds the datum of the entry. If a key of such a hash table is garbage collected, the corresponding entry will be removed. Note that if some datum holds some key strongly, the table will effectively hold that key strongly.
An entry type for hash tables that hold keys strongly and data weakly. An entry of this type is a weak pair (see Weak Pairs) whose weak (car) slot holds the datum of the entry and whose strong (cdr) slot holds the key of the entry. If a datum of such a hash table is garbage collected, all corresponding entries will be removed. Note that if some key holds some datum strongly, the table will effectively hold that datum strongly.
The entry type for hash tables that hold both keys and data weakly. An entry of this type is a weak list, holding both the key and the datum in the weak (car) slot of weak pairs (see Weak Pairs). If either a key or datum of such a hash table is garbage collected, all corresponding entries will be removed.
An entry type for hash tables that hold data ephemerally, keyed by the keys. An entry of this type is an ephemeron (see Ephemerons) whose key is the key of the entry and whose datum is the datum of the entry. If a key of such a hash table is garbage collected, the corresponding entry will be removed. Note that the table holds all its keys weakly even if some data should hold some keys strongly.
An entry type for hash tables that hold keys ephemerally, keyed by the data. An entry of this type is an ephemeron (see Ephemerons) whose key is the datum of the entry and whose datum is the key of the entry. If a datum of such a hash table is garbage collected, all corresponding entries will be removed. Note that the table holds all its data weakly even if some keys should hold some data strongly.
The entry type for hash tables that hold both keys and data ephemerally keyed on each other. An entry of this type is a pair of ephemerons (see Ephemerons), one holding the datum keyed by the key and the other holding the key keyed by the datum. If both the key and the datum of any entry of such a hash table are garbage collected, the entry will be removed. The table holds all its keys and data weakly itself, but will prevent any key or datum from being garbage collected if there are strong references to its datum or key, respectively.
Some examples showing how some standard hash-table constructors could have been defined:
(define make-weak-eq-hash-table
(hash-table/constructor eq-hash-mod eq? #t
hash-table-entry-type:key-weak))
(define make-equal-hash-table
(hash-table/constructor equal-hash-mod equal? #t
hash-table-entry-type:strong))
(define make-string-hash-table
(hash-table/constructor string-hash-mod string=? #f
hash-table-entry-type:strong))
The following procedure is sometimes useful in conjunction with weak and ephemeral hash tables. Normally it is not needed, because such hash tables clean themselves automatically as they are used.
If hash-table is a type of hash table that holds its keys or data weakly or ephemerally, 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.
The following procedures are provided only for backward compatibility. They should be considered deprecated and should not be used in new programs.