title: Hash attack: find strings of length 2^N with same hashCode()
body: <p>Reading algorithms fourth edition by Robert Sedgewick and Kevin Wayne I found the following question:</p>
  
  <blockquote>
    <p>Hash attack: find 2^N strings, each of length 2^N, that have the same hashCode() value, supposing that the hashCode() implementation for String is the following:</p>
  </blockquote>
  
  <pre><code>public int hashCode() {
     int hash = 0;
     for (int i = 0; i &lt; length(); i++)
        hash = (hash * 31) + charAt(i);
     return hash;
  }
  </code></pre>
  
  <blockquote>
    <p>Strong hint: Aa and BB have the same value.</p>
  </blockquote>
  
  <p>What comes on my mind is generating all possible strings of length 2^N and compare their hashCodes. This, however, is very expensive for large N and I doubt it's the correct solution. 
  Can you give me hints what I miss in the whole picture?</p>