I have a question that seems really intuitive to me but I can't think of a way to prove it.

Assume we a have a file with words that are different from each other and contain digits only for example "1234", "456" etc.

So a simple perfect hash function is to calculate for "1234" :$ 4*10^0 + 3*10^1 + 2*10^2 + 1*10^3 = 1234 $ and put in the hash table in this index,

and this promise us that every 2 words will be mapped to different cells.

Similarly, For words that contain only enligh letter "aba", "abc" someone told me that a perfect hash would be:$ 'a'*26^0 + 'b'*26^1 + 'a'*26^2 $ (26 becuase this is the number of english letters) but I can't prove why this is true, so my question is: why is this mapping promise us that every 2 different words will be mapped to different cells? how can I prove it?

  • $\begingroup$ It is like treating English strings as base $26$ numbers with $'a'$ being $0$, $'b'$ being $1, \dots 'z'$ being $25$. After all, $'0', '1', \dots '9'$ are just nine symbols. We can take any finite set of symbols of size $d \ge 2$ to represent numbers in base $d$. $\endgroup$ – Alex Vong May 26 '17 at 9:49
  • $\begingroup$ So in general, if we let $\Sigma = \{a_0, a_1, \dots, a_{d - 1}\}$ to be a set of symbols. Then we can write any nonnegative integer as $a_{k_1} a_{k_2} \dots a_{k_n}$ to mean $k_1 \cdot d^{n - 1} + k_2 \cdot d^{n - 2} + \dots + k_{n - 1} \cdot d + k_n$ where $k_j = 0, 1, \dots d - 1$. $\endgroup$ – Alex Vong May 26 '17 at 10:02
  • 1
    $\begingroup$ Your "perfect hash function" is not perfect. Note that "0010" and "0002" are mapped to the same hash value. There are many such collisions. To be perfect, you would need to use a value of $d =10$ or higher instead of $d = 2$. $\endgroup$ – Paul Sinclair May 26 '17 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.