J Mei J Mei - 1 month ago 4
C Question

Unique hash function without any collisions

So I am given a key that is in the format XYYYYZ, where X is a char from 'A'-'Z', YYYY is and int from 0 to 9999, and Z is a char from 'A'-'C'. I am suppose to make a unique hash function without any collisions.

I was told the smallest someone has made is a table size of 780,000 but I have no idea how.

The one I can think of is X-'A' to get a number from 0 to 26 and multiplying that by 100,000 then multiplying YYYY by 10 and then add (Z - 'A')

So Z1025A would be 2,610,250 and L4444C would be 1,144,443

And the make possible combo is 2699993 and / 2,700,000 would have about a 29% usage rate.

But is there any other way to reduce the the size of the table?

Answer

just do

((Z - 'A') * 26 + (X - 'A')) * 10000 + YYYY
Comments