散列：
将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素。
散列函数：
一般直接用STL中的map或unordered_map，除非必须模拟这些方法或者对算法效率要求较高，否则不需要自己实现解决冲突的方法
①直接定址法
- 恒等变换：将 key(输入的数) 作为数组下标 ⭐——最常见最实用
- 线性变换：H(key) = a * key + b
②平方取中法
- 取 key 平方的中间若干位作为 hash 值（很少用）
③除留取余法
- H(key) = key % mod (表长Tsize >= mod，否则会越界)
1、开放定址法
- 线性探查法：H(key), H(key)+1, …
- 平方探查法：H(key), H(key)+1^2, H(key)-1^2, H(key)+2^2, H(key)-2^2, …
if (H(key) + k^2 > Tsize) H(key)+k^2 % Tsize
if (H(key) - k^2 < 0) ((H(key) - k^2) % Tsize + Tsize) % Tsize （可只正向探查避免此种麻烦）
2、链地址法
字符串hash：
将一个字符串S映射为一个整数，使得整数可以尽可能唯一地代表字符串S
(1) 字符串由大写字母 A-Z 组成
- 将大写字母 A-Z 视为 0-25，即对应到了26进制中，再转换为10进制。转换为的整数最大为26^len-1，len为字符串长度
int hashFunc(char S[], int len){
int id = 0;
for (int i = 0; i < len; i++){
id = id * 26 + (S[i] - 'A');
}
return id;
}
(2) 字符串由大写字母 A-Z 和小写字母 a-z 组成
(3) 字符串由大写字母 A-Z，小写字母 a-z 和 数字 1-9 组成
- (1) 62进制转10进制问题
- (2) 若保证字符串末尾是确定个数的数字，可将前面英文字母部分转换为整数后将数字拼接上去
int hashFunc(char S[], int len){
int id = 0;
for (int i = 0; i < len - 1; i++){
id = id * 26 + (S[i] - 'A');
}
id = id * 10 + (S[len-1] - '0');
return id;
}
京公网安备 11010502036488号