一个“好”的散列函数一般应考虑下列两个因素：
- 计算简单，以便提高转换速度；
- 关键词对应的地址空间分布均匀，以尽量减少冲突。
数字关键词的散列函数构造
-
直接定址法
取关键词的某个线性函数值为散列地址，即 \(h(key) = a * key + b (a、b为常数)\)
-
除留余数法
散列函数为：\(h(key) = key \mod p\)
-
数字分析法
分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址
-
折叠法
把关键词分割成位数相同的几个部分，然后叠加
-
平方取中法
字符关键词的散列函数构造
-
一个简单的散列函数——ASCII码加和法
对字符型关键词key定义散列函数如下：$ h(key) = (Σkey[i]) \mod TableSize$
-
简单的改进——前3个字符移位法
\(h(key)=(key[0]*27^2 + key[1]*27 + key[2])\mod TableSize\)
-
好的散列函数——移位法
涉及关键词所有n个字符，并且分布得很好：
\(h(key)=(\sum_{i=0}^{n-1}key[n-i-1]*32^i) \mod TableSize\)
Java 关联
- Object#hashCode
- Integer#hashCode
- String#hashCode