6
$\begingroup$

When hashing a (key, value) pair where the key is a string, I have seen the following hash function in use:

E.g. $c_n + 256c_{n-1}+ 256^2c_{n-2}+...256^{n-1}c_1$, where this represents the string $c_1c_2..c_n$. I understand the equation above can be written as: $c_n + 256(c_{n-1} + 256(c_{n-2}+...256c_1))$, could someone explain how the following is valid, when I have to compute mod over the entire sum, how can we take it term by term?

r= 0;
for i = 1 to n do
r := (c[i] + 256*r) mod TableSize
$\endgroup$
9
$\begingroup$

Let's prove by induction that after $i$ iterations, $$ r = \sum_{j=1}^i 256^{i-j} c[j] \bmod m, $$ where $m$ is the size of the table.

The base case is $i = 0$, where $r = 0 = 0 \bmod m$. Now suppose that the formula holds after $i-1$ iterations. After $i$ iterations, we have \begin{align*} r &= \left[ c[i] + 256 \left(\sum_{j=1}^{i-1} 256^{i-1-j} c[j] \bmod m\right) \right] \bmod m \\ \\ &= \left[ c[i] + \sum_{j=1}^{i-1} 256^{i-j} c[j] \right] \bmod m \\ &= \sum_{j=1}^i 256^{i-j} c[j] \bmod m, \end{align*} using several times the formulas $$ (a + b) \bmod m = \left[(a \bmod m) + (b \bmod m)\right] \bmod m, \\ (ab) \bmod m = \left[(a \bmod m)(b \bmod m)\right] \bmod m. $$

For the proofs of these two formulas check: this and this.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.