Next: Basic Hash Table Operations, Previous: Hash Tables, Up: Hash Tables [Contents][Index]
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 and 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
strongly and the data are held weakly. Note that if a key holds a
datum strongly, the table will effectively hold that datum 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 by
make-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
strongly and the data are held weakly. Note that if a key holds a
datum strongly, the table will effectively hold that datum 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 by
make-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.
All of the above are highly optimized table implementations. Next are some general constructors that allow for more flexible table definitions.
These are the standard constructors for making hash tables. The behavior of each differs depending on its arguments: if the first argument is a comparator, then it behaves like a SRFI 125 procedure, otherwise it behaves like a SRFI 69 procedure.
For SRFI 125 behavior the comparator must be a comparator
that satisfies comparator-hashable?. The remaining args
are optional, and may include the following symbols:
weak-keysSpecifies that the table will have weak keys.
weak-valuesSpecifies that the table will have weak values.
ephemeral-keysSpecifies that the table will have ephemeral keys.
ephemeral-valuesSpecifies that the table will have ephemeral values.
The symbols weak-keys and weak-values can be specified
together or separately, likewise for ephemeral-keys and
ephemeral-values. But weak and ephemeral symbols can’t be
mixed. If none of these symbols are present, then the keys and values
are strongly held.
Additionally args may contain an exact non-negative integer, which specifies an initial size for the table; otherwise a default size is used.
For SRFI 69 behavior the key=? argument specifies how keys
are compared and defaults to equal?. The hash-function
argument specifies the hash function to use. If hash-function
is not specified, it defaults to a standard value that depends on
key=?; an error is signaled if there’s no standard value. The
arg arguments are allowed but are implementation dependent; do
not provide them.
The procedure alist->hash-table creates a new hash table, as
with make-hash-table, and then fills it with the contents of
alist.
The remaining constructors use hash-table types to encapsulate the hashing parameters.
Constructs a new hash table using the hashing parameters in type.
Returns a procedure that, when called, constructs a new hash table using the specified parameters. The returned procedure accepts an optional initial-size.
If its first argument is a comparator, it uses the comparator
and args as in make-hash-table, except that any initial
size specified in args can be overridden by the
initial-size argument to the returned procedure.
If its first argument is a type, returns a procedure that, when called, constructs a new hash table using the hashing parameters in type. This is equivalent to
(lambda (#!optional initial-size) (make-hash-table* type initial-size))
The next two procedures are used to create hash-table types. The procedures are equivalent in power; they differ only in how the types are described.
This procedure accepts four arguments and returns a hash-table type, which can be used to make hash tables of that type. The key=? argument is an equivalence predicate for the keys of the hash table. The hash-function argument is a procedure that computes a hash number. Specifically, hash-function 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 hash-function 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 hash-function 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 the
entry-type variables described below, which all start with
hash-table-entry-type:.
This procedure’s arguments, except for key=?, are keyword
arguments; that is, each argument is a symbol of the same name
followed by its value. Aside from how they are passed, the arguments
have the same meaning as those for make-hash-table-type. Note
that all of the keyword arguments are optional, while key=? is
required.
The argument entry-type specifies the name of an entry
type. It must be a symbol corresponding to one of the entry-type
variables described below. The name of an entry type is the symbol
composed of the suffix of the corresponding variable; for example the
type hash-table-entry-type:key-weak has the name
key-weak.
The default values for the keyword arguments are as follows. The arguments hash-function and rehash-after-gc? default to standard values that depend on key=?; an error is signaled if key=? has no standard values. The argument entry-type defaults to strong.
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
(make-hash-table-type eq-hash eq? #t
hash-table-entry-type:key-weak)))
(define make-equal-hash-table
(hash-table-constructor
(make-hash-table-type equal-hash equal? #t
hash-table-entry-type:strong)))
(define make-string-hash-table
(hash-table-constructor
(make-hash-table-type string-hash string=? #f
hash-table-entry-type:strong)))
The following procedures are provided only for backward compatibility. They should be considered deprecated and should not be used in new programs.
This procedure is deprecated. Instead use the equivalent
(hash-table-constructor
(make-hash-table-type hash-function key=? rehash-after-gc?
entry-type))
Like hash-table/constructor but always uses
hash-table-entry-type:strong. If rehash-after-gc? is
omitted, it defaults to #f.
Like hash-table/constructor but always uses
hash-table-entry-type:key-weak. If rehash-after-gc? is
omitted, it defaults to #f.
Next: Basic Hash Table Operations, Previous: Hash Tables, Up: Hash Tables [Contents][Index]