perfect hash function

Question

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 1

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

Answer 2

Found One

I tried a few things and found one semi-manually:

(n ^ 28) % 13 

The semi-manual part was the following ruby script that I used to test candidate functions with a range of parameters:

t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0] (1..200).each do |i|   t2 = t.map { |e| (e ^ i) % 13 }   puts i if t2.uniq.length == t.length end