双哈希与线性哈希

Question

我正在写双哈希 table，它只接受整数。

unsigned int DoubleHashTable::HashFunction1(unsigned int const data)
{
   return (data % GetTableSize());
}

unsigned int DoubleHashTable::HashFunction2(unsigned int const data, unsigned int count)
{
   return ((HashFunction1(data) + count * (5 - (data % 5)) % GetTableSize()));
}

并尝试使用 SetData()

将数据插入 table

void DoubleHashTable::SetData(unsigned int const data)
{
   unsigned int probe = HashFunction1(data);

   if (m_table[probe].GetStatus())
   {
      unsigned int count = 1;
      while (m_table[probe].GetStatus() && count <= GetTableSize())
      {
         probe = HashFunction2(data, count);
         count++;
      }
   }

   m_table[probe].Insert(data);
}

将 100 个整数项放入大小为 100 的 table 后，table 显示一些索引留空。我知道，最坏情况需要 O(N)。我的问题是，项目应该被插入到 table 中并且没有空 space 即使它需要最坏的搜索时间，对吗？我找不到我的功能的问题。

补充问题。哈希算法有很多著名的算法，双重哈希的目的是尽可能减少冲突，H2(T) 是 H1(T) 的备份。但是，如果众所周知的哈希算法（如 MD5、SHA 等，我不是在谈论安全性，只是众所周知的算法）更快且分布良好，为什么我们需要双重哈希？

谢谢！

Answer 1

测试哈希函数时，可能会与某些病态输入（=那些破坏哈希函数的输入）发生高度冲突。这些输入可以通过反转哈希函数来发现，这可能导致某些 attacks (this is a real concern，因为互联网路由器限制了 space 用于哈希 tables）。即使没有对手，在某些输入后这种哈希的查找时间 table 可能会增长，甚至在最坏的情况下变为线性。

双重哈希是一种解决哈希冲突的方法尝试来解决病态输入的线性增长问题。 Linear probing or open addressing 是受欢迎的选择。但是，在这些情况下，输入的数量必须远低于 table 大小，除非您的散列 table 可以动态增长。

回答你的第二个问题（现在你已经自己修复了代码），简而言之，双重哈希更适合小哈希 tables，单哈希更适合对于大哈希 tables.

双哈希与线性哈希

Double Hashing vs Linear Hashing

hash

hashtable

linear-probing

double-hashing