11 Associations
MIT/GNU Scheme provides several mechanisms for associating objects with
one another. Each of these mechanisms creates a link between one or
more objects, called keys, and some other object, called a
datum. Beyond this common idea, however, each of the mechanisms
has various different properties that make it appropriate in different
situations:
- Association lists are one of Lisp’s oldest association mechanisms.
Because they are made from ordinary pairs, they are easy to build and
manipulate, and very flexible in use. However, the average lookup time
for an association list is linear in the number of associations.
- 1D tables have a very simple interface, making them easy to use,
and offer the feature that they do not prevent their keys from being
reclaimed by the garbage collector. Like association lists, their
average lookup time is linear in the number of associations; but 1D
tables aren’t as flexible.
-
The association table is MIT/GNU Scheme’s equivalent to the
property lists of Lisp. It has the advantages that the keys may
be any type of object and that it does not prevent the keys from being
reclaimed by the garbage collector. However, two linear-time lookups
must be performed, one for each key, whereas for traditional property
lists only one lookup is required for both keys.
- Hash tables are a powerful mechanism with constant-time access to
large amounts of data. Hash tables are not as flexible as association
lists, but because their access times are independent of the number of
associations in the table, for most applications they are the mechanism
of choice.
- Balanced binary trees are another association mechanism that is
useful for applications in which the keys are ordered. Binary trees
have access times that are proportional to the logarithm of the number
of associations in the tree. While they aren’t as fast as hash tables,
they offer the advantage that the contents of the tree can be converted
to a sorted alist in linear time. Additionally, two trees can be
compared for equality in worst-case linear time.
- Red-Black trees are a kind of balanced binary tree. The
implementation supports destructive insertion and deletion operations
with a good constant factor.
- Weight-Balanced trees are a kind of balanced binary tree. The
implementation provides non-destructive operations. There is a
comprehensive set of operations, including: a constant-time size
operation; many high-level operations such as the set operations union,
intersection and difference; and indexing of elements by position.