C 语言中的哈希数组技巧

Question

我需要一些想法来为我的作业开发一个好的哈希函数。我有一份世界上所有国家（大约 190 个）的列表。每个国家的名称是哈希函数的关键。是否有人会推荐一种特定类型的哈希函数来将这些数据存储在哈希函数中而不会产生很多冲突？另外，您能否举一个如何实现它的例子？

Answer 1

使用GNU gperf。对于像您这样的输入，它将为您生成 C 代码，该代码实现完美的哈希函数（对于给定的输入）。没有碰撞，不用担心。

Answer 2

您可以使用生成的完美哈希（GNU perf）。

如果字符串集是动态的，那么您可以使用三元特里树。
对于 N 个唯一的字符串，它将为您提供唯一的数字 [1..N]。对于您的情况，它会比哈希表更快。
这是我对此类事情的实现：
http://code.google.com/p/tiscript /source/browse/trunk/tool/tl_ternary_tree.h

Answer 3

我能想到的最简单的方法是对每个国家/地区的名称计算其表示形式中 ASCII 值的总和，并将其用作哈希值：

int hash(const char *s)
{
    int h = 0;

    while (s && *s)
          h += *s++;

    return h;
}

如果您的哈希映射的大小为 N，则可以使用 map[hash 存储国家/地区名称（我的国家/地区）% N] = 我的国家/地区。从概念上讲。

只需尝试这种方法，看看生成的哈希值是否足够均匀分布。请注意，分布的质量也可能取决于 N。