[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Efficiency and flexibility of hash-tables

From: Roland Orre
Subject: Re: Efficiency and flexibility of hash-tables
Date: 10 Feb 2003 18:09:30 +0100

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]