哈希函数设计
- “键”通过哈希函数得到的“索引”分布越均匀越好；
- 对于一些特殊领域，有特殊领域的哈希函数设计方式，甚至有专门的论文；
一般的哈希函数设计原则
- 整型
- 小范围正整数直接使用；
- 小范围负整数进行偏移，比如 -100 ~ 0 -> 0 ~ 100；
- 大整数
- 通常做法：取模，比如取后4位，等同于mod 10000，但取模不能利用大整数中所有有用的信息，一个简单的解决办法是：模一个素数，具体素数怎么选择有人研究的，比如从这里可以参考；
- 浮点型
- 将浮点型占用的二进制空间看成整型，用整型的办法处理；
- 字符串
- 转成整型处理，用26进制表示字符串，比如：code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0；
- hash("code") = ( c * B^3 + o * B^2 + d * B^1 + e * B^0 ) % M
hash("code") = ( ( ( ( c * B ) + o ) * B + d ) * B + e ) % M
hash("code") = ( ( ( ( c % M ) * B + o ) % M * B + d ) % M * B + e) % M
int hash = 0
for(int i = 0; i < s.length(); i++)
hash = (hash * B + s.charAt(i)) % M
- 复合类型
- 可以转换成字符串来处理，而字符串又可以转成整数来处理；
总而言之，就是转成整型处理，但这并不是唯一的方法！
哈希函数设计原则
- 一致性：如果 a == b，则hash(a) == hash(b)
- 高效性：计算高效简便；
- 均匀性：哈希值分布均匀；
