[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Hash Tables vs. Alists

In Symbolics Genera 7.0 and later, the make-hash-table/gethash family
of functions choose an appropriate internal representation (hash table,
alist, linearly searched array) based on the test function and the size
of the table, and automatically switch representations when the table
grows or shrinks.  Thus the application programmer doesn't have to
think about it.  The tradeoff point between linear search and hash table
is based on measurements and is surprisingly high when the test function
is EQ or EQL, since a linear search with those test functions can be
very fast.

I don't know if any other Common Lisp implementations do this, although
I don't see any reason why they couldn't.  Just because the function
is named make-hash-table doesn't mean it actually has to be implemented
with a hash-table.