Мне нужна хэш-функция h[n]:[t] из k-независимого семейства хешей, когда k мало (< = 5). Или мне нужны n хэш-значений, выбранных равномерно случайным образом из [1-t], так что они k wise independent. Я пытаюсь реализовать некоторые рандомизированные алгоритмы, где мне это нужно. Я генерировал n случайных чисел из диапазона [1-t], используя scipy.stats.randint(0,self._t).rvs(self._n)
но это кажется слишком медленным для моего приложения. Поскольку мне не нужна полная случайность, но только 4 мудрая независимость, мне было интересно, могу ли я ускорить это. Я знаю, что могу использовать многочленную хэш-семью, чтобы получить независимую независимость, но это лучшее? Если да, есть ли быстрая реализация этого, которую я могу подключить? Если нет альтернативных способов (возможно, библиотек на python)?
Я просмотрел эту цепочку Получение независимой хэш-функции k-wise, но я не уверен, что означает принятый ответ
"если вам нужен k другой хеш, просто повторно используйте один и тот же алгоритм k раз, с k разными семенами"
Любые предложения приветствуются. Благодаря
Самый быстрый способ генерации хеш-функции из k-независимого хэш-семейства при малых k (<= 5)
Ответ 1
В предыдущем ответе рекомендуется использовать xxhash k раз с другим семенем (возможно, лучше иметь случайное семя - даже если вы можете получить одно и то же семя несколько раз):
Секунда (по умолчанию 0) может использоваться для предсказуемого результата.
>>> import xxhash >>> xxhash.xxh64('xxhash').hexdigest() '32dd38952c4bc720' >>> xxhash.xxh64('xxhash', seed=20141025).hexdigest() 'b559b98d844e0635' >>> x = xxhash.xxh64(seed=20141025) >>> x.update('xxhash') >>> x.hexdigest() 'b559b98d844e0635' >>> x.intdigest() 13067679811253438005