One of the data-structures that even early LISP implementations possessed, were ‘
plists‘. It was only by reading up on LISP lately, that I discovered that many LISP implementations maintained a hidden
plist, in which certain Properties of Symbols were stored. This could easily have been found in the
CIR of the Atom, the naming of which was later simplified to
CDR. Alternatively, this
plist could have been the only datum of the Symbol, hence stored at its
In short, this was an early associative list, consisting of Key:Value pairs, where the Key was supplied by the programmer, in order to retrieve the Value from the
Plists were later superseded by ‘
alist has a better storage format, but again stores Key:Value associations. One big advantage of an
alist, is the ability to perform a reverse look-up, in which a sought Value is supplied, and the List of Keys returned, that point to this Value.
I think it is agreed, that Hash Tables eventually manage forward-look-ups better than either a
plist or an
alist, especially if large numbers of Keys are stored. Yet, it is written that for short collections of data, the simplicity with which an
alist is stored, actually allows it to work more quickly than a Hash Table, in LISP.
Now, if it was necessary to perform reverse look-ups, yet the large number of objects require a Hash Table, then the most sensible approach might be to create two Hash Tables, one for the forward look-up, and another for the reverse look-up? In that case, if a Hash Table is predicted to serve a one-to-many relationship, then the care should also be taken from the beginning, to encapsulate all the value-sets that result from one Key, into Sets, even if in many cases, there may be only one element in the Set.
Alternatively a system could be devised, so that only one result from the reverse look-up is the correct one.