Re: Efficiency and flexibility of hash-tables

[Roland Orre]

On Mon, 2003-02-10 at 17:52, Mikael Djurfeldt wrote:
> The idea of having an upper threshold comes from the idea of
> maintaining the load factor of the hash table in a reasonable
> interval.  But the purpose of the load factor is to prevent to large
> clusters forming in the same hash bucket.  What about simply counting
> the pairs in a bucket during insertion and rehashing when we reach a
> threshold?  Then no extra data needs to be stored in the table.  (We
> would need to globally serialize rehashing with an external mutex,
> though.)

The risk with this is that if the hash function in a specific situation
is bad, not spreading enough, we may form clusters anyway. With a 
risk that we will reallocate hash tables much too often.

> Another disadvantage is that the tables wouldn't shrink.  Is this an
> issue?

For most of our applications it isn't because we will reallocate all
hash tables after each run.

In all my code over the years hash-remove! is very very rare.

        Best regards
        Rolan