通用哈希執行比模哈希差，有什麼不對？

如果你不熟悉universal hashing，它主要是試圖保證少量的碰撞（相反，使用普通的舊模），使用一些相當簡單的數學涉及隨機性。問題是，它並沒有爲我工作：通用哈希執行比模哈希差，有什麼不對？

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; 
}

我試模第一哈希和確定的最長鏈長（鏈長是指一個散列桶的大小）：

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; 
}

我挑一個這些輸入導致了一個真正的大鏈（id est一個使用普通模的方式執行不好），並且拋出這個反對通用散列。通用哈希使用隨機性，所以我可以採取不變的輸入，並仍然得到不同的結果。

問題來了。我嘗試了100個隨機輸入數組，每個大小爲128，並計算平均最長鏈和最長鏈，但兩種算法執行類似。

你可以在我的repo檢查我的主。

我的問題是：結果是預期的嗎？通用哈希表現不是更好的輸入已使用模數執行差嗎？或者我只是搞砸了我的實現（更可能）。

非常感謝！

來源

2016-12-23 AdHominem

等待，您爲每個單獨的哈希訪問重新計算'a'和'b'？這有什麼意義？在這種嘗試中， – melpomene

是'a'和'b'應該是'靜態'？ – WhozCraig

@melpomene：如果它們是靜態的，那麼函數總是會將相同的輸入散列到同一個桶中？ – AdHominem

那麼，爲什麼你認爲模數是壞的？如果輸入是隨機的並且足夠大，則模數應該產生均勻分佈的結果。統一哈希（如鏈接狀態）可防止非隨機（即惡意）輸入，這種情況並非如此。

來源

2016-12-23 10:01:19 SomeWittyUsername

那麼這就是爲什麼我採用模數最糟糕的分佈來檢查使用通用哈希算法是否會更好。這種方法有缺陷嗎？ – AdHominem

什麼是最糟糕的分佈？如果輸入足夠大，那麼隨機輸入應該收斂到統一。 – SomeWittyUsername

嗯，也許只是運行一次代碼。我生成隨機輸入並選擇一個導致使用模的大桶。然後，我使用與通用相同的輸入來檢查結果是否改善。根據規範，最大鏈長應至少減少一點。 – AdHominem

通用哈希執行比模哈希差，有什麼不對？

回答

相關問題