c++ - 哈希函数 - 截断和除法

Question

所以我的问题是我试图使用截断哈希函数作为冲突索引递增/递减...我不得不将它用作第一个主函数，并使用更统一的哈希函数作为第二个哈希函数取而代之。

我更正的代码如下:

// ============================ HASH FUNCTIONS ============================ \\


  // Hash function 1 (Base-26)
  int Hash_1(char *key2)
  {
        int index;
        index = (int)((key2[0] - 'A' + 1) * pow(26, 3)) + ((key2[1] - 'A' + 1) * pow(26, 2)) + ((key2[2] - 'A' + 1) * 26) + ((key2[3] - 'A' + 1));
        return (index % TABLESIZE);
  }


  // Hash function 2 (Folding)
  int Hash_2(char *key2)
  {
        int index;
        index = ((key2[0] - 'A' + 1) * (key2[1] - 'A' + 1)) + ((key2[2] - 'A' + 1) * (key2[3] - 'A' + 1));
        return (index % TABLESIZE); 
  }


  // Hash function 3 (Truncation)
  int Hash_3(char *key2)
  {
        int index;
        index = ((key2[1] - 'A' + 1) * (key2[2] - 'A' + 1));
        return (index % TABLESIZE);
  }

// ========================= DOUBLE HASH FUNCTIONS ========================= \\


  // Double hash 1 (Linear Probing)
  int ProbeDec_1(char *key2)
  {
      return 1;
  }


  // Double hash 2 (Middle Squaring)
  int ProbeDec_2(char *key2)
  {
      int index;
      index = (int)pow(((key2[1] - 'A' + 1) + (key2[2] - 'A' + 1)), 2);
      return (index % TABLESIZE);
  }


  // Double hash 3 (Division)
  int ProbeDec_3(char *key2)
  {
      int index;
      int primeNum = 7;
      index = max((key2[3] / primeNum), 1) % primeNum;
      return (index % TABLESIZE);
  }

Answer 1

您可以为 4 个字母 字符串创建一个完美的“散列”。

拉丁字母少于32个，如果区分大小写，拉丁字母少于64个。

为什么要提到32和64？因为他们是二的五次方和六次方。我们可以创建一个 32 位整数来唯一表示一个 4 个字母的单词(区分大小写字母)，如下所示:

• 第 0 到 5 位编码字符串的第一个字母
• 第 6 到 11 位编码第二个
• 第 12 到 17 位编码第三位
• 第 18 到 23 位编码第四位
• 第 24 到 31 位设置为 0

通过编码，我的意思是:

• “A”编码为000000
• “a”编码为000001
• “B”为 000010
• “b”是 000011等等。我们知道我们可以将所有字母放入您想要的任何编码中，因为字母的数量少于可用的位排列。

您甚至可以将每个字母编码为 key - 'A' + 1 ，如您所愿。

我强烈建议您创建一个接受字符并返回其编码值的函数。通常，如果您发现自己在超过 3 个地方编写同一段代码，您应该考虑将其设为一个函数。

同样重要的是，由于编写哈希函数主要是关于位操作，您应该学习如何使用移位运算符 <和 >而不是 pow .

您还应该了解整数运算。你到底是做什么的1 / (1 - (key2[2] - 'A' + 1))可能会回来吗？

您的函数都不能称为“哈希函数”。如果你想使用“截断”或“除法”之类的东西，你应该首先弄清楚那是什么意思。