`Hi,I while ago I did some experimentation with simple bit-op based stringhashfunctions.  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;}[I haven't kept my test program / data set - if anyone compares theabove to the others functions mentioned on the list, let me know.]The 31 and 7 were determined experimentally.  But the 31 has atheoreticalexplanation (which might even be valid):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 morebits set in the polynomial, making reduction harder.  A compromise is tochoose P in the form x**N - 1 but with relatively few factors.X**31 - 1 is such a P.Also, a 32 bit rotate (modulo X**32 - 1, which is equalto (X - 1) ** 32 over Z_2), came out pretty badly.One thing that shouldn't be forgotten about hashing for hash tablesis that you have to reduce the hash value to the required range - doingthat well greatly reduces the difference between various hash functions.Ralph.-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/`