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(X,X) must be true.
F(X,Y) must be true if and only if F(Y,X) is true.
If both F(X,Y) and F(Y,Z) are true then F(X,Z) must be true.

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.