Re: Efficiency and flexibility of hash-tables

[Roland Orre]

On Sat, 2003-02-08 at 15:14, Joris van der Hoeven wrote:
> Hi,
> 
> Thanks for your reply. Unfortunately, I think that
> you did not fully understand my question.

Yes, I misunderstood it.

> 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.

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.

        Best regards
        Roland