如何使用 hash-string-to-int 方法产生冲突？

Question

我正在将哈希方法 (farmhash) 集成到我们的软件库中。散列服务似乎工作正常。基本上，它将一串字符转换为一个唯一的整数值。

我添加了一个基础设施来检测冲突（在两个输入字符串会产生相同输出整数的情况下）。基本上，对于每个经过哈希处理的字符串，我将 [hash result] -> [string] 保存在一个映射中，每次对一个新字符串进行哈希处理时，我都会将它与映射中的内容进行比较；如果散列已经存在，我确保它与生成它的字符串相同。我知道它可能很慢并且可能会消耗内存，但我仅在 "per request" 的基础上执行这些检查：它们在发布模式下未启用。

现在我想测试那个基础设施（从单元测试的角度来看，得到一个碰撞）。

我可以生成一堆字符串（随机或顺序），向我的哈希基础设施发送垃圾邮件并希望看到积极的碰撞，但我觉得我会浪费我的时间，CPU 循环并用大量数据没有成功。

如何产生碰撞？

不太相关的事实：

我正在使用 C++；
我可以使用 python;
目标整数是uint32_t。

更新:

我创建了一个简单的小程序来暴力检测碰撞：

void
addToQueue(std::string&& aString)
{
  //std::cout << aString << std::endl;
  hashAndCheck( aString ); // Performs the hash and check if there is a collision
  if ( mCount % 1000000 )
    std::cout << "Did " << mCount << " checks so far" << std::endl;
  mQueue.emplace( aString );
}


void 
generateNextRound( const std::string& aBase )
{
  //48 a 122 incl
  for ( int i = 48; i <= 122; i++ )
  {
    addToQueue( std::move( std::string( aBase ).append( 1, static_cast<char>( i ) ) ) );
  }
}


int main( void )
{

  // These two generate a collision
  //StringId id2 = HASH_SID( "@EF" ); // Hashes only, does not check
  //StringId id1 = HASH_SID( "7\:" ); // Hashes only, does not check

  std::string base = "";
  addToQueue( std::move( base ) );

  while ( true )
  {
    const std::string val = mQueue.front();
    mQueue.pop();
    generateNextRound( val );
  }

  return 0;
}

我最终可以在其中添加线程和其他东西，但我不需要它，因为我在大约 1 秒内发现了冲突（在调试模式下）。

Answer 1

您可以限制哈希函数输出的整数范围；一般来说，您应该能够将一些数字传递给它 (n)，以便结果介于 0 和 n-1 之间。如果你把它限制在 10 说，那么你肯定会以碰撞告终。

Answer 2

对于键k和散列函数h，return常量c:

h(k) = c

无论您使用什么键，这总是会发生冲突。

Answer 3

如果您离线暴力搜索碰撞，您可以将导致碰撞的字符串硬编码到您的测试中，以便您的测试尽可能接近生产代码，但不会遭受暴力破解的性能损失每次都强制工作（或者，就像其他人所说的那样，您可以故意制作一个导致过度冲突的垃圾哈希算法）

如何使用 hash-string-to-int 方法产生冲突？

How to generate a collision with a hash-string-to-int method?

hash

hash-collision