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