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

> On Thu, Oct 25, 2007 at 03:43:46PM -0400, Daniel Barkalow wrote:
> 
> > 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.