序、思维导图

        整体思路，首先通过与平衡二叉树的对比引入hash函数的意义，在hash函数的结构上引入一些操作流程以及冲突的解决方法。还将讲述stl散列表、布隆过滤器等内容。

一、hash

背景：在大量网页中过滤提取信息，或在许多文字中提取关键内容。

二分查找

        平衡二叉树能通过比较保证有序，通过每次排除一半的元素达到快速索引的目的。平衡二叉树的增删改查时间复杂度为O(logn)，100万个节点，最多比较20次。其他类似算法如下：

                

散列表

        根据key计算key在表中的位置的数据结构，是key和其所在存储地址的映射关系（节点中的k、v存储在一起）。

        映射函数 Hash(key)=addr可能会把两个或两个以上的不同key映射到同一地址，这种情况称之为hash冲突。

hash函数

        1，选择hash的原因：计算速度快，强随机分布性（等概率、均匀地分布在整个地址空间）

        2，负载因子：数组存储元素的个数/数组长度；用来形容散列表的存储密度（负载因子越小，冲突概率越小）。

        常用方法：murmurhash1\2\3, siphash（redis6.0中用，主要解决字符串问题）

冲突处理

        1，链表法：将冲突元素用链表链接起来，常见的处理方法（极端情况：冲突元素过多，此时可将链表转化为红黑树，提升遍历效率，链表过长的判断值--256）

        2，开放寻址法：将所用的元素都存放在哈希表的数组中，不使用额外的数据结构，一般用线性探查的思路解决（当槽位存在元素时加上一定步长循环判断，但会有哈希聚集的问题），还可使用双重hash解决上面出现的哈希聚集。

        注意：以上方法运用于 负载因子 在合理范围内时（负载因子不在合理范围内：used > size || used < 0.1*size）。

STL unordered 散列表实现

        

        注意每个首节点指向上层的最后一个，方便头插法插入元素。同时设计成一个链表使得迭代器方便迭代。

二，布隆过滤器

        布隆过滤器是一种概率型的数据结构，特点是高效地插入和查询，能确定字符串一定不存在 或 可能存在。不存储具体数据，占用空间小，查询结果存在误差但是误差可控，不支持删除操作。

        原理：

分布式一致性hash

        应用场景：分布式缓存，将数据均衡地分散在不同服务器中，分摊缓存服务器的压力。

        问题：哈希偏移（hash结果随机，不能保证服务器节点均匀分布在哈希环上，导致服务器压力不均匀）

        解决：增加了虚拟节点的概念，理论上哈希环节点数越多，数据分布越均衡。