`On Sat, Feb 24, 2001 at 10:43:16AM +1300, Ralph Loader wrote:> A while ago I did some experimentation with simple bit-op based string> hash functions.  I.e., no multiplications / divides in the hash loop.> > The best I found was:> > int hash_fn (char * p)> {>   int hash = 0;>   while (*p) {>      hash = hash + *p;>      // Rotate a 31 bit field 7 bits:>      hash = ((hash << 7) | (hash >> 24)) & 0x7fffffff;>   }>   return hash;> }Hmm. This one goes in the "catastrophic" category.For actual names:N=557398, m=51 sz=2048, min 82, max 4002, av 272.17, stddev 45122.99For generated names:N=557398, m=51 sz=2048, min 0, max 44800, av 272.17, stddev 10208445.83A very non-uniform distribution.> The rotate is equivalent to a multiplication by x**7 in Z_2[P=0],> where P is the polynomial x**31 - 1 (over Z_2).> Presumably the "best" P would be irreducible - but that would have more> bits set in the polynomial, making reduction harder.  A compromise is to> choose P in the form x**N - 1 but with relatively few factors.> X**31 - 1 is such a P.It has seven irreducible factors. Hardly "almost irreducible".Shifting the 7-bit ASCII characters over 7 bits makes sure that thereis very little interaction to start with. And the final AND that truncatesto the final size of the hash chain kills the high order bits.No good.Andries-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`