hash - 我正在使用 ELF Hash 编写经过特殊调整的哈希映射版本。想要产生碰撞

Question

任何人都可以举一个仅由字母字符组成的 2 个字符串的示例，它们将产生与 ELFHash 相同的哈希值吗？

我需要这些来测试我的代码。但它似乎并不容易生产。令我惊讶的是，互联网上有很多各种哈希函数的示例代码，但没有一个提供碰撞字符串的示例。

下面是 ELF 哈希，以备不时之需。

unsigned int ELFHash(const std::string& str)
{
   unsigned int hash = 0;
   unsigned int x    = 0;

   for(std::size_t i = 0; i < str.length(); i++)
   {
      hash = (hash << 4) + str[i];
      if((x = hash & 0xF0000000L) != 0)
      {
         hash ^= (x >> 24);
         hash &= ~x;
      }
   }

   return (hash & 0x7FFFFFFF);
}

Answer 1

您可以使用蛮力方法找到冲突（例如，计算所有可能的长度小于 5 的字符串）。

一些碰撞示例（我以这种方式得到的）：

hash = 23114:
-------------
UMz
SpJ

hash = 4543841:
---------------
AAAAQ
AAABA

hash = 5301994:
---------------
KYQYZ
KYQZJ
KYRIZ
KYRJJ
KZAYZ