The "Self Organizing List" is a poor man's hash
table. More precisely,
<self-organizing-list>
is a
subclass of
<mutable-explicit-key-collection>
and <stretchy-collection>
for
which addition and retrieval are both linear in the worst
case, but which use a probabilistic strategy which yields
nearly constant time in the best case.
Because they have a very low overhead, self-organizing lists may provide better peformance than hash tables in cases where references have a high degree of temporal locality. They may also be useful in situations where it is difficult to create a proper hash function.
Instantiate
<self-organizing-list>
s with
make(<self-organizing-list>, test: test)
Test
is expected to be an equality function. In
particular, it is expected to satisfy the identity and
transitivity requirements as described in the
Dylan Reference Manual
. If not
specified, test
defaults to
\==
.