• Subject: Re: Hash Table Collisions (n.runs-SA-2011.004)
• From: Gé Weijers <ge@...>
• Date: Wed, 4 Jan 2012 11:22:05 -0800

On Wed, Jan 4, 2012 at 10:04 AM, William Ahern wrote:
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;

Note that h0, h1, h2 etc all get the same value of the _expression_ '(h << 5) + (h >> 2)', which may not be what you want......

Gé

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().

--