node universal hash function

универсальная функция

Стабильность: 1 - экспериментальный

Универсальная хэш -функция.

Установка

 npm install universal-hash-function

Обзор

Если злонамеренный противник выбирает ключи, которые будут хэшироваться с помощью какой -либо фиксированной функции хэш, то противник может выбрать N клавиш, которые все хешируют к одному слоту, что дает среднее время поиска O (n) . Любая фиксированная функция хэш уязвима к такому ужасному поведению в худшем случае; Единственный эффективный способ улучшить ситуацию - это выбрать функцию хэш случайным образом таким образом, чтобы она не зависела от ключей, которые фактически будут храниться. Этот подход, называемый Universal Hashing, может дать в среднем хорошие результаты, независимо от того, какие ключи выбирают противник. http://mitpress.mit.edu/books/introduction-algorithms

Использование

prime , numberOfHashSlots и someKey - все целые числа .

 var uhf = require ( 'universal-hash-function' ) ;

// prime should be such that the greatest integer value of someKey should be
// less than prime
// uhf(prime, numberOfHashSlots);
var hashFunc1 = uhf ( 17 , 6 ) ;
var hashFunc2 = uhf ( 17 , 6 ) ;
var hashFunc3 = uhf ( 17 , 6 ) ;

// hashFunc(someKey)
hashFunc1 ( 0 ) ; // -> 2
hashFunc2 ( 0 ) ; // -> 1
hashFunc3 ( 0 ) ; // -> 5

hashFunc1 ( 1 ) ; // -> 3
hashFunc2 ( 1 ) ; // -> 5
hashFunc3 ( 1 ) ; // -> 1

hashFunc1 ( 2 ) ; // -> 5
hashFunc2 ( 2 ) ; // -> 2
hashFunc3 ( 2 ) ; // -> 3
// etc...