哈希表中执行插入和搜索操作效率是非常高的
(1)如果没有产生冲突,那么效率就会更高
(2)如果发生冲突,存取时间就依赖后来的探测长度
(3)平均探测长度以及平均存取时间,取决于填装因子,随着填装因子变大,探测长度也越来越长
(4)随着填装因子变大,效率下降的情况,在不同开放地址法方案中比链地址法更严重,所以我们来对比一下它们的效率,再决定我们选取的方案
在分析效率之前,我们先了解一个概念:装填因子
(1)装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值
(2)装填因子 = 总数据项 / 哈希表长度
(3)开放地址法的装填因子最大是多少呢?1,因为它必须寻找到空白的单元才能将元素放入
(4)链地址法的装填因子呢?可以大于1,因为拉链法可以无限的延申下去,只要你愿意.(当然后面效率就变低了)
链地址法相对来说效率是好于开放地址法的
所以在真实开发中,使用链地址法的情况较多
- 因为它不会因为添加了某元素后性能急剧下降
- 比如在java的HashMap中使用的就是链地址法