node universal hash function

función universal

Estabilidad: 1 - Experimental

Función de hash universal.

Instalación

 npm install universal-hash-function

Descripción general

Si un adversario malicioso elige las claves para que la función hash fija, entonces el adversario puede elegir n teclas que todos los hash a la misma ranura, produciendo un tiempo de recuperación promedio de O (n) . Cualquier función de hash fija es vulnerable a un comportamiento tan terrible en el peor de los casos; La única forma efectiva de mejorar la situación es elegir la función hash al azar de una manera que sea independiente de las claves que realmente se almacenan. Este enfoque, llamado Hashing Universal, puede producir un rendimiento demostrablemente bueno en promedio, sin importar qué teclas elija el adversario. http://mitpress.mit.edu/books/introduction-algorithms

Uso

prime , numberOfHashSlots y someKey son todos enteros .

 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...