node universal hash function

وظائف شاملة

الاستقرار: 1 - تجريبي

وظيفة التجزئة العالمية.

تثبيت

 npm install universal-hash-function

ملخص

إذا اختار الخصم الخبيث المفاتيح التي يجب تجزئها بواسطة بعض الوظائف الثابتة ، فيمكن للخصم اختيار مفاتيح N التي تجزأها إلى نفس الفتحة ، مما يؤدي إلى متوسط ​​وقت استرجاع من O (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...