61散列表的性能分析

'''
散列表的性能分析
    平均查找长度ALS 用来度量散列表查找效率：成功、不成功。
    关键词的比较次数，取决于产生冲突的多少，
    影响产生冲突多少的因素有：
        1、散列函数是否均匀
        2、处理冲突的方式
        3、散列表的装填因子a

一、线性探测法查找性能分析
    线性探测法期望探测次数满足以下公式：
    p = 0.5 * [1+1/(1-a)^2]    # 插入和不成功查找
    p = 0.5 * [1+1/(1-a)]      # 成功查找
    查找次数的期望仅仅和 a装填因子 有关。

二、平方探测法和双散列探测法查找性能
    探测次数满足以下公式：
    p = 1/(1-a)                # 插入和不成功查找
    p = -(1/a) * In(1-a)       # 成功查找哦
    查找次数的期望仅仅和 a装填因子 有关。

三、分离链接法的查找性能
    所有地址链表 的平均长度定义成 装填因子a，a有可能超过1，
    期望探测次数有如下公式：
    p = a + e^(-a)             # 插入和不成功查找
    p = 1 + a/2                # 成功查找
    注意：装填因子的定义和 开放地址法的 是不一样的。

回顾散列查找的特点：
    一、优点：
        复杂度和问题的规模没有关系，不像搜索树logN 这样和规模N有关。
        只要不冲突就是一次算出位置，不用一个一个比较找位置。
    二、优点：
        适用于str字符串管理，因为关键词key经常是字符串，一个一个比较不方便。
        散列表直接把str转为了数字。
    三、a小冲突就少，散列表是以空间换时间的做法。
    四、缺点：
        散列表存储关键字是随机的，不便于顺序查找关键字，
        比如 不适合查询   范围、最大值、最小值。

开放地址法 与 分离链接法的比较：
    开放地址法
        优点：散列是一个数组，存储效率高，随机查找。
        缺点：有"聚集"现象。
    分离链接法
        优点：关键词删除不需要"懒惰删除"，没有存储垃圾。
        缺点：a小，链表短了，可能需要更多的数组空间来细分位置，
             从而浪费空间。
             a大，链表长了，一旦进入了链表内的查找，效率低。
'''