散列表性能分析
散列表性能分析
0x00 如何分析
成功查找次数，即在散列表里的元素的平均查找次数
不成功查找次数，是不在表里的每一类（同一类的hash函数值相同）的平均查找次数
0x01 线性探测的查找性能
这只是该装填因子下，线性探测法的期望查找次数，对于每个具体的散列表，平均查找次数不一定与期望值相等。
0x02 平方探测法和双散列探测法
0x03 分离链接法
0x04 散列表的优缺点分析
选择合适的hash函数和冲突解决方法，其查找效率期望通常是常数O(1)，几乎与关键字的空间大小n无关，适合关键字直接比较计算量大的问题。
这中高效率是以较小的装填因子alpha为前提，因此散列表是一个以空间换时间
散列表储存元素的位置是随机的，不便于顺序查找关键字，也不适合与范围查找，或最大最小值查找
0x05 开放地址法与分离链表法的比较
开放地址法 优点 ：本质是一个数组，储存效率高，随机查找，实现简单，缺点 ：但是容易发生聚集现象
分离链接法 优点： 顺序存储方法和链式储存方法的结合，链表部分的储存效率和查找效率比较低，删除元素不用懒惰删除，从而没有储存垃圾 缺点 装填因子太小会造成浪费，但是如果列表太长效率又会降低。
