Subject: bug#28876: 26.0; (elisp) `Hash Tables': hash table vs alist

From: Drew Adams <[email-masked]>
Date: Wed, 9 Oct 2019 07:47:50 -0700 (PDT)

> > 1. Please consider saying explicitly that an Elisp hash table is not a
> > multimap.
> >
> > This is another way in which it differs from an alist.  An alist can
> > have multiple entries that have exactly the same key (even `eq').  An
> > Elisp hash table cannot - it realizes a mathematical function: one key
> > gives you only one value.
> >
> > (The fact that `assoc' and `assq' ignore entries past the first is
> > irrelevant here.  An alist is a list; it can be used in many ways.)
> 
> An alist is a list that associates keys with value.  There may be
> several identical keys in the list, but that is not how an alist is
> meant to be used, which is reflected in how the common operators on
> alists work -- they only return the first match.

That is _exactly_ how an alist is meant to be used.

And not understanding that is precisely the problem here.

The point of using an alist is that you can, and you
typically will, have multiple entries with the same
key, AND that only the first one is returned by the
specifically-alist access functions.

An alist is not a hash table, and this is one of the
most important differences.

> So I don't think this is a difference that needs to be pointed out here.

That's unfortunate.

> > 2. Wrt the difference between an alist and a hash table, the emphasis in
> > this node seems to be on the performance characteristics.  I think that
> > functional/structural differences should be distinguished here from
> > performance differences, instead of just lumping them together in the
> > same bulleted list.
> 
> The primary difference is in the performance characteristics, so I don't
> see anything that needs changing in that node.

No, the primary difference is not in the performance
characteristics.  And even those can be more complex
that what is presented here.

Users used to other languages too often assume that
an Emacs-Lisp hash table will be more performant than
an alist, at least for a large set.  Things are not
so simple.

The primary difference is structural.  It is especially
that an alist is a Lisp _list_.

> Closing.

That's too bad.