Re: Resizing hash tables in Guile

[Roland Orre]

On Wed, 2003-02-12 at 18:53, Mikael Djurfeldt wrote:
> I've been thinking that maybe we should continue the move and let the
> resizing tables entirely replace the fixed size ones.  It seems a
> little silly to have to explain to Guile users that there are two
> (sorry, eight) different kinds of hash tables...  Also, I think the
> opacity of the resizing table objects is an advantage rather than a
> disadvantage.  If they are opaque, we can any time modify the
> underlying implementation (the well-known data abstraction argument).
> 
> What do you say?

I think that this is a a good idea, but I would like the optional size
argument to still be there as an initial guess about the number of
items to expect to avoid resizing and to optimize performance when
we have advance information about how many items to expect.

Of course this additional level of abstraction is nice as it also gives
a future option to use trees if the user e.g gives an optional
comparision operator.

By the way, Joris van der Hoeven mentioned that this type of resizing
hash tables are faster than trees, which have a time complexity
of O(log n)+reshuffling time if they are balanced. Do you have any
numbers showing how much faster and if possible if there are any
conditions? The reshuffling time will grow at least O(n) when the
size of our linear tables increases if I have understood right.

        Best regards
        Roland Orre