Find a collision string with a given hash function

Question

I have a string anna, where values of chars in the string are a = 1, n = 14 ( You can compute the value of other chars like ( char - 96 ) and hash function which looks like :

int hashCode( string s ) // s = "anna";
{
    k = 0;
    for ( int i = 0; i < s.length(); i++ )
      k = ( 7 * k + 3 * s[i] ) % 61;
    return k;
}

How do I find a string of length 3 where collision happens ( something smart )? The only way that comes to my mind is to calculate k of anna which is 29 and then somehow think of another string of length 3 which gives 29.

Answer 1

Why don't you simply generate all strings of length 3 and compute their hashes (in fact, you can stop when all 61 possible values of hash functions can were reached)? The number of options is not too large.

One possible optimization: if you need to answer multiple queries (like given a string, find a string of length 3 with the same value of the hash function), you can generate all strings of length 3 and compute their hashes once to build a map hash -> a string of length 3 with this hash. Once you have this map, finding a string of length 3 with the same hash as the given one is just one map lookup.