对于频繁使用的查找表,希望 ASL = 0
记录在表中位置和其关键字之间存在一种确定的关系
3, 3, 0, 6, 6, 3
可见,若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上,从而增加了“冲突”的可能
考虑因素
采用何种构造哈希函数的方法取决于建表的关键字集合的情况
原则是使产生冲突的可能性降到尽可能地小
一旦冲突,就找下一个空地址存入
di = 12, -12, 22, -22, …±k2
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中:m为哈希表长度
di 为随机数
优点:
对于给定值 K,计算哈希地址 i = H(K)
案例v01
案例v02
从查找过程得知,哈希表查找的平均查找长度实际上并不等于零
决定哈希表查找的ASL的因素
编译器对标识符的管理多是采用哈希表
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。