处理冲突的方法
- 开放地址法：换个位置
- 链地址法：同一位置的冲突对象组织在一起
散列表查找性能分析
- 成功平均查找长度(ASLs)
- 不成功平均查找长度 (ASLu)
开放定址法（Open Addressing）
一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址
若发生了第 i 次冲突，试探的下一个地址将增加di，基本公式是：
\(h_i(key) = (h(key)+d_i) \mod TableSize ( 1 ≤ i < TableSize )\)
\(d_i\) 决定了不同的解决冲突方案：
- 线性探测法（Linear Probing）：\(d_i=i\)
- 平方探测法（Quadratic Probing）：\(d_i=\overset{+}{-}i^2\)
- 双散列探测法（Double Hashing）：\(d_i=i*h_2(key)\)
- 再散列（Rehashing）
- 当散列表元素太多（即装填因子 α太大）时，查找效率会下降；
- 实用最大装填因子一般取 0.5 <= α<= 0.85
- 当装填因子过大时，解决的方法
分离链接法（Separate Chaining）
将相应位置上冲突的所有关键词存储在同一个单链表中
标签：装填,20230410,因子,11.3,地址,查找,冲突,key From： https://www.cnblogs.com/huangwenjie/p/17490522.html