I'm currently trying to understand the mechanism behind the hash function defined for Python's built-in frozenset data type. The implementation is shown at the bottom for reference. What I'm interested in particular is the rationale for the choice of this scattering operation: lambda h: (h ^ (h << 16) ^ 89869747) * 3644798167 where h is the hash of each element. Does anyone know where these came from? (That is, was there any particular reason to pick these numbers?) Or were they simply chosen arbitrarily? Here is the snippet from the official CPython implementation, static Py_hash_t frozenset_hash(PyObject *self) { PySetObject *so = (PySetObject *)self; Py_uhash_t h, hash = 1927868237UL; setentry *entry; Py_ssize_t pos = 0; if (so->hash != -1) return so->hash; hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1; while (set_next(so, &pos, &entry)) { /* Work to increase the bit dispersion for closely spaced hash values. The is important because some use cases have many combinations of a small number of elements with nearby hashes so that many distinct combinations collapse to only a handful of distinct hash values. */ h = entry->hash; hash ^= (h ^ (h << 16) ^ 89869747UL) * 3644798167UL; } hash = hash * 69069U + 907133923UL; if (hash == -1) hash = 590923713UL; so->hash = hash; return hash; } and an equivalent implementation in Python: def _hash(self): MAX = sys.maxint MASK = 2 * MAX + 1 n = len(self) h = 1927868237 * (n + 1) h &= MASK for x in self: hx = hash(x) h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 h &= MASK h = h * 69069 + 907133923 h &= MASK if h > MAX: h -= MASK + 1 if h == -1: h = 590923713 return h Continue reading...
