I'm using ELF Hash to write a specially tweaked version of hash map. Wanting to produce collisions

Question

Can any one give an example of 2 strings, consisting of alphabetical characters only, that will produce the same hash value with ELFHash?

I need these to test my codes. But it doesn't seem like easy to produce. And to my surprise there there are a lot of example codes of various hash function on the internet but none of them provides examples of collided strings.

Below is the ELF Hash, in case you need it.

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);
}

Mcnully

Answer 1

You can find collisions using a brute force method (e.g. compute all possible strings with length lower than 5).

Some example of collisions (that I got in that way):

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

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

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

Cowgirl

Oh. I never believed that this could happen in strings of length lower than five. Thank you so much for your help! – Mcnully

@Gene: Those are just a couple of collsions, but I assure you that there are really a lot of them in strings < 5 (unfortunately I made the code to generate collisions in C# otherwise I'd have posted it...) This makes me think that maybe this hash is not so strong... – Cowgirl

This hash is indeed very weak. Almost 1% collisions for a list of 466K English words. – Carnotite