0

如果您不熟悉通用散列，它主要是尝试使用一些涉及随机性的相当简单的数学来保证少量的冲突（相反，例如使用普通的旧模数）。问题是它对我不起作用：

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中查看我的 main 。

我的问题是：这个结果可以预期吗？对于使用模数已经表现不佳的输入，通用散列是否表现得更好？还是我只是搞砸了我的实施（更有可能）。

提前非常感谢！

4

2 回答 2

1

好吧，你为什么认为模数不好？如果输入是随机的并且足够大，则模应该产生均匀分布的结果。统一散列（如您的链接状态）提供对非随机（即恶意）输入的保护，这不是这里的情况。

于 2016-12-23T10:01:19.637 回答
0

如果您不熟悉通用哈希，这主要是为了保证少量的冲突......</p>

“试图保证”不是保证。

…（相反，使用普通的旧模数）…</p>

链接的文章说，甚至更简单的哈希函数 [使用模] 是近似通用的。

我生成随机输入并选择一个使用模数导致大桶的输入。然后我使用与 Universal 完全相同的输入来检查结果是否有所改善。而且根据规范，最大链长至少应该减少一点。

100 个大小为 128 的随机输入数组并不是特别大的输入。我从你的回购中运行了八次程序；在其中五次运行中，您的通用哈希将“平均最大链长度”减少了约 10%；在三轮运行中，您的通用哈希将“平均最大链长度”增加了相似的数量。我注意到使用通用散列的最大链长度在每次运行中都是恒定的。

总而言之，不能保证一种散列方法总是比另一种更好，并且您的通用散列似乎通过经常更好而不是更好来保持其性能承诺。

于 2019-01-17T09:33:17.613 回答