Hash Function

LeetCode LintCode DataStructure

Submit 1 : 没有取模, 求和算法也有误

submit 2:

submit3: 这样写是会溢出的，long的最大范围是2^64,超过的话就会溢出，溢出机会变负的，所以要边加sum边取模； 因为内存里数值存的是补码，最高位0代表正1代表负，加的太多把符号位占了就变负了。比如0111(7)+0111(7)=1110(-2) （那1110 = -2是这么看的，首先判断是负数，然后全部取反得到0001， 加1得到0010， 就是2，加上负号就是-2）

AC:

取模运算分配律：
(a+b) % c = (a%c + b%c) % c
(a-b) % c = (a%c - b%c) % c
a * b % c = (a%c * b%c) % c