Алгоритм хеширования замороженного питона / реализация замороженного ⇐ Python

[Anonymous]

В настоящее время я пытаюсь понять механизм хэш-функции, определенный для встроенного типа данных Python . Реализация показана внизу для справки. Что меня интересует, так это обоснование выбора этой операции рассеяния: < /p>

lambda h: (h ^ (h

где h < /code> - хэш каждого элемента. Кто -нибудь знает, откуда они взялись? (То есть была ли какая-то конкретная причина выбрать эти числа?) Или они были просто выбраны произвольно?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 hash = hash;
return hash;
}
< /code>

и эквивалентная реализация в Python: < /p>

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 MAX:
h -= MASK + 1
if h == -1:
h = 590923713
return h


Подробнее здесь: https://stackoverflow.com/questions/208 ... ementation