Chapter 8

Collections

# Tables

Tables map arbitrary keys to elements. Table keys may be any object, including complex
objects such as strings. All tables are instances
of `<table>`

. `<table>`

is the only
instantiable subclass of `<explicit-key-collection>`

defined by
Dylan. Tables are unstable under iteration.

The iteration protocol for tables is implemented in terms of the
function `table-protocol`

. Every concrete subclass
of `<table>`

must provide or inherit a method
for `table-protocol`

. This function accepts a table as an argument, and returns
an equivalence predicate and hash-function, as described below.

The equivalence predicate of a table is used to compare keys. (It
is the table's key test.) The table maps keys that are equivalent
under the predicate to the same table element. An equivalence predicate is a boolean
function of two arguments that returns true if and only if the arguments are considered to
be the same according to some specified criteria. For a function to be used as an
equivalence predicate, it must be reflexive, commutative, and transitive. That is, for a
function `F` and any arguments `X`, `Y`, and `Z` in the
domain of `F`, the following must be true:

`F``(`

must be true.`X`,`X`)`F``(`

must be true if and only if`X`,`Y`)`F``(`

is true.`Y`,`X`)- If both
`F``(`

and`X`,`Y`)`F``(`

are true then`Y`,`Z`)`F``(`

must be true.`X`,`Z`)

An equivalence class (for an equivalence predicate) is a set
of objects, or potential objects, that are all the same under the specified equivalence
predicate and different from all objects not in the class. (This use of the
term class

does not refer to Dylan classes.)

An object is said to be visibly modified with respect to an equivalence predicate if the modification changes the equivalence class of the object. The modifications that are visible to an equivalence predicate are determined by the definition of the predicate. (For example, changing a character in a string would be a visible modification with respect to an equivalence predicate that compared strings character by character, but it would not be a visible modification with respect to an equivalence predicate that compared objects by identity, without regard for their contents.)

If an object `X` is a key in a table `T` and is visibly modified with
regard to the test function of `T`, then the consequences are unspecified if any of
the following objects are used as a key in any subsequent operations on `T`:

- The original object,
`X`. - Some object
`Y`that is in the same equivalence class (as determined by the test function) as`X`prior to the modification of`X`. - Some object
`Z`that is in the same equivalence class (as determined by the test function) as`X`after the modification of`X`.

Each table also has an associated hash function, which is a function that relates table keys and table elements by computing hash codes. A hash code is a conceptual object consisting of a hash id and its associated hash state. (It is not an actual Dylan object.) A hash id is an integer encoding of an object. A hash state is an object of implementation-dependent type that is associated with a particular hash id and can be used by the implementation to determine whether the hash id has been invalidated. A hash function accepts one argument, a key, and returns two values, a hash id and a hash state, which together represent the hash code.

Each hash function is associated with a specific equivalence predicate, and must obey the following constraints:

- The domain of the hash function must include the domain of valid arguments to the corresponding equivalence predicate. A hash function need not be defined for all Dylan objects, only those that are acceptable as arguments to the equivalence predicate.
- All objects in a given equivalence class have the same
(
`=`

) valid hash id, where validity is determined from the associated hash state.

In addition, a hash function should have the property that the hash ids computed by it are well distributed over the range of possible values. That is, it should be unlikely that two randomly chosen equivalence classes have the same valid hash id.