c++ - 哈希函数/代码

Question

所以我只是在学习(或尝试)一些关于散列的知识。我正在尝试制作一个散列函数，但是我对将数据保存到哪里感到困惑。我正在尝试计算碰撞次数并将其打印出来。我制作了 3 个不同的文件，一个有 10,000 字，20,000 字和 30,000 字。每个单词只是 10 个随机数字/字母。

long hash(char* s]){
    long h;
    for(int i = 0; i < 10; i++){
      h = h + (int)s[i];
    }
     //A lot of examples then mod h by the table size
     //I'm a bit confused what this table is... Is it an array of
     //10,000 (or however many words)?

    //h % TABLE_SIZE
    return h
  }

  int main (int argc, char* argv[]){
    fstream input(argv[1]);
    char* nextWord;
    while(!input.eof()){
      input >> nextWord;
      hash(nextWord);
    }
  }

所以这就是我目前拥有的，但我无法弄清楚该表到底是什么，正如我在上面的评论中所说的那样......它是我的 main 中的预定义数组，其中包含单词数吗？例如，如果我有一个包含 10 个单词的文件，我是否在 main 中创建一个大小为 10 的数组 a？然后，如果/当我返回 h 时，假设顺序为:3、7、2、3

第 4 个词是碰撞，对吗？发生这种情况时，我将碰撞加 1，然后加 1，然后检查插槽 4 是否也已满？

感谢您的帮助!

Answer 1

散列的要点是对您存储的每个元素进行恒定时间访问。我将尝试在下面的简单示例中进行解释。

首先，您需要知道必须存储多少数据。例如，如果你想存储数字并且你知道你不会存储大于 10 的数字。最简单的解决方案是创建一个包含 10 个元素的数组。该数组是您的“表”，您可以在其中存储数字。那么我如何实现惊人的恒定时间访问呢？哈希函数!关键是要返回数组的索引。让我们创建一个简单的:如果你想存储 7，你只需将它保存到位置 7 的数组中。每次，你想要查找元素 7，你只需将它传递给你的 hasning 函数和 bzaah!你在固定时间内找到了你的元素的位置!但是，如果您想存储更多值为 7 的元素怎么办？您的简单哈希函数为每个元素返回 7，现在我已经占据了它的位置!如何解决？好吧，解决方案不多，最简单的是:

1:链接 - 您只需将元素保存在第一个空闲位置。这具有显着的缺点。想象一下，您想删除一些元素...(这就是您描述的方法)

2:链表 - 如果您在某些链表上创建一个指针数组，您可以轻松地将新元素添加到链表的末尾，即位置 7!

这两种简单的解决方案都有其缺点。我想你可以看到他们。正如@rwols 所说，您不必使用数组。您也可以使用树或成为真正的 C++ 高手，并使用带有自定义哈希函数的 unordered_map 和 unordered_set，这非常酷。还有一个名为 trie 的结构，这很有用，当你想创建某种字典时(很难知道在哪里，你需要存储多少单词)

总结一下。你必须知道，有多少东西你不想存储，然后创建理想的散列函数，覆盖适当大小的数组，在完美的世界中，它必须具有统一的索引分布，没有碰撞。 (实现这一点非常困难，我想在现实世界中，这是不可能的，所以冲突越少越好。)

您的散列函数非常糟糕。它会有很多碰撞(比如字符串“ab”和“ba”)，而且你需要mod m it with m是你数组的大小(又名。表)，所以你可以将它保存到某个数组中，你就可以从中获利。 modus 是一种简化 has 函数的方法，因为 has 函数必须 “适合”表格，您在开始时指定，因为您不能将元素保存在位置 11、12、.. . 如果你有 10 个数组。

好的散列函数应该是什么样的？好吧，有比我更好的消息来源。一些example (警告!它是用 Java 编写的)

以您的示例为例:您根本无法将 10k 或更多的单词保存到大小为 10 的表中。这会产生很多冲突，并且您失去了散列函数的主要好处 - 不断访问您保存的元素。

您的代码看起来如何？像这样:

int main (int argc, char* argv[]){
    fstream input(argv[1]);
    char* nextWord;

    TypeOfElement table[size_of_table];
    while(!input.eof()){
      input >> nextWord;
      table[hash(nextWord)] = // desired element which you want to save
    }
  }

但我想，您的目标不是在某处保存某些东西，而是计算碰撞次数。另请注意，上面的代码不能解决冲突。如果您想计算碰撞次数，请创建整数数组 table 并将其初始化为零。然后，只需增加存储在哈希函数返回的索引中的值，如下所示:

table[hash(nextWord)]++;

希望对您有所帮助。请说明您还想知道什么。