# Hashing using Horner’s Rule

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


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.$$