Polynomial for producing hash values:

$p(z)=a_0+a_1z+\cdots, a_{n-1}z^{n-1}$

Honor's method for that polynomial:

$$ p_0(z)=a_{n-1} \\ p_i(z)=a_{n-i-1}+zp_{i-1}(z), (i=1, \cdots, n-1)\\ $$

Problem: For 50,000 English words and for $z=33$, we would get at most 6 collisions. So, how we can prove that please? Also, to calculate the hash using Honor's method, we split the key into a fixed length of size 8 bits, 16 bits or 32 bits, etc. Why we do this split for the key please?

  • 2
    $\begingroup$ You probably mean “Horner”. $\endgroup$ Aug 26, 2021 at 15:59
  • 2
    $\begingroup$ The number of collisions depends on the words. Perhaps it’s 6 collisions in expectation. The expected number of collisions depends on the length of the hash. Under the simplifying assumption that hashes are random, the expected number of collisions for $n$ words and $b$ bits is roughly $n^2/2^{b+1}$. $\endgroup$ Aug 26, 2021 at 16:02
  • 1
    $\begingroup$ Also, I personally don’t split keys. If someone else is, you should ask them why they do it. $\endgroup$ Aug 26, 2021 at 16:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.