On Thu, 25 Oct 2007, Jeff King wrote: > 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. Ah, right, nevermind. The comment might be a bit misleading in that case, if we both missed this at first. -Daniel *This .sig left intentionally blank* - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
