JiangLiruii#algorithm#第18讲-散列表(中)1

# 散列表中: 如何打造一个工业级水平的散列表 ## 通过散列表上已知散列表的查询效率不能笼统的说成是 O(1), 跟散列函数, 装载因子, 散列冲突等都有关系. ### 在极端情况下, 有恶意的攻击者通过设计的构造数据, 使所有的数据都到一个槽里, 如果我们使用的是基于链表的冲突解决办法, 那么散列表就会退化为链表, 查询的时间复杂度也从 O(1)急剧退化到O(n).如果有10w 个数据, 退化后的查询效率就下降了10w 倍, 从时间上来说, 如果之前查询只需要0.1s, 现在就需要1w 秒 ,这回极大的消耗 CPU 或线程资源, 导致无法响应请求, 达到拒绝服务(DoS)的攻击目的.这也是**散列表冲撞的基本原理** ## 如何设计一个可以应对各种异常的工业级散列表, 避免在散列冲突的情况下, 散列表的性能急剧下降并且能抵抗散列碰撞攻击? ### 如何设计散列函数 #### 散列函数的好坏直接决定了散列表冲突的概率大小, 也直接决定了散列表的性能, 好的散列表需要满足以下几点: - 设计不能太复杂, 否则会消耗很多的计算时间. - 生成的值尽可能随机并且均匀分布, 1是最小化散列冲突2是即使冲突, 散列到每个槽里的数据也会比较平均 #### 几个常用的散列函数设计方法 - 数据分析法: 通过分析数据得出散列值,手机尾号后四位是比较不容易冲突的, 反之, 手机号的前三位的冲突概率大很多, 所以选择后四位作为散列值. - 公式法: 上次说到的 word 拼写检查, 我们可以将单词中每个字母的 ASCII 码值进行相加, 然后再跟散列表的大小求余, 取模, 作为散列值. 比如英文单词 nice