Re: Efficiency and flexibility of hash-tables

[Joris van der Hoeven]

> > My question was: is the number of slots automatically adapted
> > as a function of the number or entries, or is it not?
> > If you cannot have a good estimate for the number of entries,
> > then this auto-adaptation may be important.
> > In fact, I think that a good low level implementation of
> > general purpose hash tables should have this feature.
> 
> I agree. I once developed (in Ada) for a debugging system, a hash
> table where the hash entries were balanced trees instead of lists.
> This could maybe be a good approach to reach good performance as
> balanced trees are quite good from this point of view. (like the
> new Reiser file system in Linux is using)
> 
> Your idea, about adaptive hash table length, could easily be made into
> guile but from my opinion not as a general solution, as there will be
> a lot of reshuffling of every item each time the vector length changes.

That is not really true: the reshuffling only takes place
when the number of entries changes in an important way.
Also, shuffling is linear in time. So if it only occurs
after adding or removing a proportional number of entries,
then the overall running time remains linear.
This is better than using a O(log n) overhead for all operations.
However, the price to pay is rather that the shuffling can occur
at arbitrary moments. But this is already the case for garbage
collection anyway. In fact, I implemented this kind of
hash tables in TeXmacs.

> I guess somewhere out there, a balanced tree solution may exist for guile,
> otherwise I could try to find my old ada-source and give it a try. The
> disadvantage with the balanced tree solution though is that it's not
> enough with a hash function (and equal?), it also needs a comparision
> (<) function.

So does there exist an adaptive-number-of-slots solution in guile?
If I understand you well, this is certainly not the case for
the standard implementation... :^(((