node universal hash function

Function universelle-hash

Stabilité: 1 - expérimental

Fonction de hachage universel.

Installation

 npm install universal-hash-function

Aperçu

Si un adversaire malveillant choisit les clés à hacher par une fonction de hachage fixe, alors l'adversaire peut choisir N ​​les clés que tous les hachages à la même fente, ce qui donne un temps de récupération moyen de O (n) . Toute fonction de hachage fixe est vulnérable à un comportement aussi terrible du pire des cas; Le seul moyen efficace d'améliorer la situation est de choisir la fonction de hachage au hasard d'une manière indépendante des clés qui seront réellement stockées. Cette approche, appelée hachage universel, peut produire des performances prouvées en moyenne, quelles que soient les clés que l'adversaire choisit. http://mitpress.mit.edu/books/introduction-algorithms

Usage

prime , numberOfHashSlots et someKey sont tous des entiers .

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