Re: Hashtables in guile.

[Jim Blandy <jimb@red-bean.com>]

> >  2. Do they grow dynamically or does their size remain fixed?  If they
> >     remain of fixed size, are there any particular sizes that are most
> >     efficient for the default hashing fcns?  Also, if they remain of
> >     fixed size, why?!?!  I've always found the STk hash tables (based
> >     on the TCL code) that grow dynamically to be extremely efficient &
> >     convenient to use.
> 
> they are fixed because they are implemented in user space as arrays.
> anyone is free to write `rehash'.

Well, this isn't the best answer possible.  Table expansion should
happen transparently, but you can't really change the size of an
existing vector, so you need to construct a new one.  So anyone
holding a pointer to the original vector gets left behind.

(Actually, I think you used to be able to resize vectors in Guile, but
we either removed that, or have discouraged people from doing it.)

The current implementation has the following nice properties:
a) it's an ordinary Scheme data structure, just a vector of lists
b) you can choose your equality predicate
c) you can choose weak or double-weak references

It would be nice to have something which added:
d) tables are automatically resized
e) equality predicate is stored with the table, so you can just use
   generic hash-ref/hash-set!/... functions

One might want to sacrifice a) and define a new opaque type to provide
better type-checking, and ensure consistency, but you'd need to be
sure to provide a full suite of accessors, so the opacity doesn't get
in people's way too much.

Volunteers are welcome.  Go dust off that copy of Knuth and post your
best hash table implementation!