ユニバーサルハッシングはモジュロハッシュよりも悪いですが、何が問題なのですか？

Question

universal hashingに慣れていない場合は、主に、乱数を含む簡単な数式を使用して、少ない数の衝突を保証しようとしています（反対に普通のモジュロを使用しています）。

size_t get_max_chain_length(int input[TABLE_SIZE], size_t (*hash_function)(const int)) { 
    HashTable *hash_table = hash_table_create(hash_function); 
    if (!hash_table) { 
     return 0; 
    } 

    for (size_t i = 0; i < TABLE_SIZE; ++i) { 
     hash_table_add(hash_table, input[i]); 
    } 

    size_t maximum_chain_length = 0; 
    for (int j = 0; j < TABLE_SIZE; ++j) { 
     const size_t length = length_of_(hash_table->rows[j]); 
     maximum_chain_length = (length > maximum_chain_length) ? length : maximum_chain_length; 
    } 

    //hash_table_print(hash_table); 
    hash_table_destroy(hash_table); 

    return maximum_chain_length; 
} 

は、Iのいずれかを選ぶ：（鎖長は、ハッシュバケットサイズを意味する）

size_t hash_modulo(const int value) { 
    return (size_t) (value % TABLE_SIZE); 
} 

// prime 491 is used because its > 128, which is the size of the hash table 
size_t hash_universal(const int value) { 
    const size_t a = (size_t) (rand() % 491 + 1); 
    const size_t b = (size_t) (rand() % 491); 
    //printf("a: %zu, b:%zu\n", a, b); 
    return ((a * value + b) % 491) % TABLE_SIZE; 
} 

私は最初のハッシングモジュロをテストし、最長チェーンの長さを決定します。問題は、それが私のために動作しませんです本当に大きなチェーンにつながった入力（普通のモジュロを使って悪い結果を出すもの）を作り、普遍的なハッシュに対してこれを投げます。ユニバーサルハッシュはランダム性を使用するので、一定の入力を受けてもさまざまな結果が得られます。

ここに問題があります。私は100個のランダムな入力配列をそれぞれサイズ128で試し、平均最長鎖と最長鎖の平均を計算しますが、どちらのアルゴリズムも同様に動作します。

あなたのrepoで私のメインをチェックすることができます。

私の質問です：その結果は期待されますか？ユニバーサルハッシングは、モジュロを使用して既に貧弱に実行された入力ではそれほど良く機能しませんか？それとも、私の実装を台無しにしたのでしょうか？

ありがとうございます！

Answer 1

なぜ、モジュロが悪いと思いますか？入力がランダムで十分に大きい場合、モジュロは均一に分布した結果をもたらすはずです。ユニフォームハッシュ（リンク状態として）は、非ランダム（すなわち、悪意のある）入力に対する保護を提供するが、ここではそうではない。