node universal hash function

สากล-แฮช-ฟังก์ชั่น

ความเสถียร: 1 - การทดลอง

ฟังก์ชั่นแฮชสากล

การติดตั้ง

 npm install universal-hash-function

ภาพรวม

หากศัตรูที่เป็นอันตรายเลือกปุ่มที่จะถูกแฮชโดยฟังก์ชั่นแฮชคงที่บางคน ฝ่าย ตรงข้ามสามารถเลือกคีย์ N ที่แฮชทั้งหมดไปยังสล็อตเดียวกัน ฟังก์ชั่นแฮชคงที่ใด ๆ ที่มีความเสี่ยงต่อพฤติกรรมกรณีที่เลวร้ายที่สุด วิธีเดียวที่มีประสิทธิภาพในการปรับปรุงสถานการณ์คือการเลือกฟังก์ชั่นแฮชแบบสุ่มในลักษณะที่เป็นอิสระจากกุญแจที่จะเก็บไว้จริง วิธีการนี้เรียกว่า Universal Hashing สามารถให้ผลการดำเนินงานที่ดีโดยเฉลี่ยไม่ว่าจะเป็นกุญแจที่ฝ่ายตรงข้ามเลือก http://mitpress.mit.edu/books/introduction-algorithms

การใช้งาน

prime , numberOfHashSlots และ someKey เป็น จำนวนเต็ม ทั้งหมด

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