Re: Hash Table Collisions (n.runs-SA-2011.004)

[William Ahern <william@...>]

On Tue, Jan 03, 2012 at 10:43:07PM -0800, William Ahern wrote:
<snip>
> 	h0 = h ^ ((h<<5) + (h>>2) + src[0]);
> 	h1 = h ^ ((h<<5) + (h>>2) + src[1]);
> 	h2 = h ^ ((h<<5) + (h>>2) + src[2]);
> 	h3 = h ^ ((h<<5) + (h>>2) + src[3]);
> 	h4 = h ^ ((h<<5) + (h>>2) + src[4]);
> 	h5 = h ^ ((h<<5) + (h>>2) + src[5]);
> 	h6 = h ^ ((h<<5) + (h>>2) + src[6]);
> 	h7 = h ^ ((h<<5) + (h>>2) + src[7]);
> 	h = h0 | h1 | h2 | h3 | h4 | h5 | h6 | h7;

Oops. Those were intended to be ^s, not |s. It's faster with xor, anyhow.
Well within factor of 2 runtime. Which isn't surprising because even with
the Lua algorithm doing a fixed 32 hash operations, string interning is
still O(N) overall because of memcpy().