node universal hash function

fungsi universal-hash

Stabilitas: 1 - Eksperimental

Fungsi hash universal.

Instalasi

 npm install universal-hash-function

Ringkasan

Jika musuh jahat memilih kunci yang akan di -hash oleh beberapa fungsi hash tetap, maka musuh dapat memilih tombol N yang semua hash ke slot yang sama, menghasilkan waktu pengambilan rata -rata O (n) . Setiap fungsi hash tetap rentan terhadap perilaku terburuk yang mengerikan; Satu -satunya cara yang efektif untuk memperbaiki situasi adalah dengan memilih fungsi hash secara acak dengan cara yang tidak tergantung pada kunci yang sebenarnya akan disimpan. Pendekatan ini, yang disebut hashing universal, dapat menghasilkan kinerja yang terbukti baik rata -rata, tidak peduli kunci mana yang dipilih musuh. http://mitpress.mit.edu/books/introduction-algorithms

Penggunaan

prime , numberOfHashSlots , dan someKey bilangan bulat .

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