node package manager


Universal hash function


Stability: 1 - Experimental

Universal hash function.


npm install universal-hash-function


If a malicious adversary chooses the keys to be hashed by some fixed hash function, then the adversary can choose n keys that all hash to the same slot, yielding an average retrieval time of O(n). Any fixed hash function is vulnerable to such terrible worst-case behavior; the only effective way to improve the situation is to choose the hash function randomly in a way that is independent of the keys that are actually going to be stored. This approach, called universal hashing, can yield provably good performance on average, no matter which keys the adversary chooses.


prime, numberOfHashSlots, and someKey are all Integers.

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