哈希表
使用哈希函数插入数据的数组叫哈希表
哈希化
把一个大范围的数字转化成一个小范围的数字叫哈希化
哈希函数
把一个大范围的数字转化成一个小范围的数字的函数叫哈希函数
把关键字转化为数组下标
1, 关键字不需要转换, 比如员工编号从 0 到 1000, 关键字员工编号可以直接做为数组下标
2, 把一部英文字典装入哈希表, a 是 1,b 是 2,c 是 3, 依此类推, z 是 26, 还有空格是 0
1) 数字相加 cats=3+1+20+19=43
假设单词最长有 10 个字母组成 a 的编码是 1,zzzzzzzzzz 是 26*10=260, 这样单词编码的范围是从 1 到 260. 不幸的是, 字典中一共有 50000 个单词. 数组下标太少, 每个数组元素大概要存储 50000/260=192 个单词.
2) 幂的连乘
- 7564= 7*103+ 5*102+ 6*101+ 4*100
- cats= 3*273+ 1*102+ 20*101+ 19*100
这样每个单词对应独一无二的一个数字
最长的 10 个字母的单词 zzzzzzzzzz, 将转化成 26*279+26*278+26*277+26*276+26*275+26*274+26*273+26*272+26*271+26*270
仅 279 就超过 7000000000000, 结果非常巨大, 内存中的数组根本不可能有这么多的单元, 产生的数组下标太多
3) 哈希函数
取余法
index = x / arrayLength
哈希化后的冲突
开放地址法
线性探测, 二次探测, 再哈希法
链地址法
哈希表
来源: http://www.bubuko.com/infodetail-2965698.html