Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames

From: Jeff King <peff@peff.net>
Date: Oct 25, 2007, 19:48 UTC
Message-ID: <20071025194859.GB27745@coredump.intra.peff.net>
In-Reply-To: <Pine.LNX.4.64.0710251522190.7345@iabervon.org>

On Thu, Oct 25, 2007 at 03:43:46PM -0400, Daniel Barkalow wrote:

Show 6 quoted lines

> Creating a list of the pointers doesn't work correctly with the grow 
> implementation, because growing the hash may turn a collision into a 
> non-collision, at which point items other than the first cannot be found 
> (since they're listed inside a bucket that's now wrong for them). AFAIK, 
> resizing a hash table requires being able to figure out what happened with 
> collisions.

I thought this at first, too, but there are two types of collisions in this hash implementation: those that come from having the actual 32-bit hash collide, and those that come from not having enough buckets.

The client code gets a pointer kicked back to it when there is a collision on the actual hash value (i.e., two things had the exact same hash value). The number of buckets grows when you simply have more buckets filled than you like. Two different hashes that would be in the same bucket don't actually occupy the same bucket -- the second one to arrive gets shoved into the next available bucket.

-Peff