Re: hash table access time

[Robert Kasper <kasper@vaxa.isi.edu>]

> Date: Tue, 25 Aug 87 13:04 EDT
> From: Daniel L. Weinreb <DLW@ALDERAAN.SCRC.Symbolics.COM>
> Subject: hash table access time
> 
> I don't think 35 is very high.  We all learn in school that hash table
> lookup or binary search are "faster than linear search", but statements
> like that are only true when the size of the search set becomes
> sufficiently large.  Many people underestimate just how speedy linear
> searches can be.

I certainly agree.  I was just surprised how high the constant
factor was for hash tables.
 
> The table system in Genera 7 takes care of all of this for you, anyway.
> It knows where all those break-point numbers are, and uses the
> appropriate representation to get the fastest search.

Although the ability to dynamically change table representations 
provides a significant improvement over previous versions,
there is still a significant amount of overhead connected
with using the Genera 7 table system for small tables.
Finding the last element of association lists of length 1-18
is faster than gethash on a (EQL) table with only one element.
Thus, it is still better to use alists when the expected size
of the table is less than about 35.

 -- Bob Kasper