title: How to generate a collision with a hash-string-to-int method?
body: <p>I'm in the process of integrating a hash method (farmhash) to our software base. The hashing services seem to work appropriately. Basically, it turns a string of characters into an unique-ish integer value.</p>
  
  <p>I've added an infrastructure to <em>detect</em> collisions (in a case where two input strings would result in the same output integer). Basically, for each string that is hashed, I keep the <code>[hash result] -&gt; [string]</code> in a map, and every time a new string is hashed, I compare it to what's in the map; if the hash is already there, I make sure that it is the same string that has generated it. I am aware that it's potentially slow and it's potentially memory consuming, but I'm performing theses checks only on a "per request" basis: they are not enabled in release mode.</p>
  
  <p>Now I'd like to <em>test</em> that infrastructure (as in <em>get a collision</em>, from a unit test point of view).</p>
  
  <p>I could generate a bunch of strings (random or sequential), spam my hash infrastructure and hope to see a positive collision but I feel I'll waste my time, CPU cycles and fill the memory with a load of data without success. </p>
  
  <p>How would one go about generating collisions?</p>
  
  <p>Not-so-relevant-facts:</p>
  
  <ul>
  <li>I'm using c++; </li>
  <li>I can generate data using python;</li>
  <li>The target int is uint32_t.</li>
  </ul>
  
  <p><strong>Update</strong>:</p>
  
  <p>I have created a small naive program to brute force the detection of collision:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>void
  addToQueue(std::string&amp;&amp; aString)
  {
    //std::cout &lt;&lt; aString &lt;&lt; std::endl;
    hashAndCheck( aString ); // Performs the hash and check if there is a collision
    if ( mCount % 1000000 )
      std::cout &lt;&lt; "Did " &lt;&lt; mCount &lt;&lt; " checks so far" &lt;&lt; std::endl;
    mQueue.emplace( aString );
  }
  
  
  void 
  generateNextRound( const std::string&amp; aBase )
  {
    //48 a 122 incl
    for ( int i = 48; i &lt;= 122; i++ )
    {
      addToQueue( std::move( std::string( aBase ).append( 1, static_cast&lt;char&gt;( 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;
  }
  </code></pre>
  
  <p>I could eventually have added threading and stuff in there but I didn't need it because I found a collision in about 1 second (in debug mode). </p>