[Top][All Lists]

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

Re: hash resizing bug

From: Jim Meyering
Subject: Re: hash resizing bug
Date: Wed, 17 Jun 2009 21:21:23 +0200

Eric Blake wrote:
> the table is certainly exceeding the requested threshold of 20% empty buckets.
> Ouch.

Ouch, indeed!

> In other words, this statement in hash_rehash:
>   /* If the growth threshold of the buckets in use has been reached, increase
>      the table size and rehash.  There's no point in checking the number of
>      entries:  if the hashing function is ill-conditioned, rehashing is not
>      likely to improve it.  */
> is not quite right.  A hashing function may be somewhat ill-conditioned for 
> one
> bucket size, but much better conditioned for another size.  At any rate, it
> looks like the correct fix is to check for rehashing thresholds based on 
> number
> of entries, not number of buckets, and that this check needs to happen on 
> every
> insertion, not just insertions that land in an empty bucket.  Or, at the very
> least, check for threshold PRIOR to insertion, rather than after, such that in
> the above case with m4, the very next call to hash_insert would notice the
> table was at 100%, and force another resize above 907 buckets.
> Thoughts, before I implement something along these lines?

Sounds good.

reply via email to

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