通用哈希执行比模哈希差，有什么不对？

如果你不熟悉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

通用哈希执行比模哈希差，有什么不对？

回答

相关问题