node universal hash function

Universal-Hash-Funktion

Stabilität: 1 - experimentell

Universelle Hash -Funktion.

Installation

 npm install universal-hash-function

Überblick

Wenn ein böswilliger Gegner die Schlüssel aus wählt, die von einer festen Hash -Funktion gehasht werden, kann der Gegner n Tasten auswählen, die alle Hashs zum gleichen Steckplatz haben und eine durchschnittliche Abrufzeit von O (n) ergeben. Jede feste Hash-Funktion ist anfällig für ein so schreckliches Verhalten von Worst-Case. Der einzig effektive Weg, um die Situation zu verbessern, besteht darin, die Hash -Funktion zufällig auf eine Weise zu wählen, die unabhängig von den Schlüssel ist, die tatsächlich gespeichert werden werden. Dieser Ansatz, der als Universal -Hashing bezeichnet wird, kann im Durchschnitt nachweislich gute Leistung erbringen, unabhängig davon, welche Schlüssel der Gegner wählt. http://mitpress.mit.edu/books/Introduction-algorithmen

Verwendung

prime , numberOfHashSlots und someKey sind alle Ganzzahlen .

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