perfect hash function

gregghz picture gregghz · Nov 9, 2010 · Viewed 12.5k times · Source

I'm attempting to hash the values

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

I need a function that will map them to an array that has a size of 13 without causing any collisions.

I've spent several hours thinking this over and googling and can't figure this out. I haven't come close to a viable solution.

How would I go about finding a hash function of this sort? I've played with gperf, but I don't really understand it and I couldn't get the results I was looking for.

Answer

tobyodavies picture tobyodavies · Nov 9, 2010

if you know the exact keys then it is trivial to produce a perfect hash function -

int hash (int n) {
  switch (n) {
    case 10:   return 0;
    case 100:  return 1;
    case 32:   return 2;
    // ...
    default:   return -1;
  }
}