Hash Tables vs. Alists

[Scott McKay <SWM@SAPSUCKER.SCRC.Symbolics.COM>]

    Date: Wed, 5 Oct 88 14:05:04 EDT
    From: 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


If you are using Genera, you can just use "tables", which dynamically
change from alists to real hash-table based on various parameters which
you can specify.  The point is that the Genera table system chooses the
representation which gives the best performance and uses that, and you
yourself don't have to worry about it.  Unless you want to, of course.