Hash Tables vs. Alists

[welch@tut.cis.ohio-state.edu (Arun Welch)]

Someone over here asked me today "At what point do hash tables get
more efficient than alists?". It seems to me that there are a number
of issues in this question, namely:

1) How well the implementation computes hash keys.

2) How well the implementation rehashes the table.

3) Whether all the memory elements in the hash table are allocated all
at once. 

4) How the implementation walked the alist. I seem to remember seeing
somewhere that Zetalisp machines were efficient for fairly large
alists due to harware support for walking the list, but I can't
remember where, of if I'm just remembering wrong. 

Has anyone actually done a study of this, or even have some pretty
good rules-of-thumb other than "if it's big, use a hash table"?

...arun



----------------------------------------------------------------------------
Arun Welch
Lisp Systems Programmer, Lab for AI Research, Ohio State University
welch@tut.cis.ohio-state.edu