哈希相关总结

• 根据key计算key在表中的位置的数据结构，是key和所在存储地址的映射关系

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

• 计算速度快
• 强随机分布

• 链表法，引用链表来处理哈希冲突，也就是将冲突元素用链表链接起来，这也是常用的处理冲突的⽅式，但是可能出现一种极端情况，冲突元素比较多，该冲突链表过长，这个时候可以将这个链表转换为红黑树，由原来链表时间复度转换为红黑树时间复杂度，那么判断该链表过长的依据是多少？可以采⽤超过 256（经验值）个节点的时候将链表结构转换为红黑树结构

• 开放寻址法

  将所有的元素都存放在哈希表的数组中，不使用额外的数据结构；一般使用线性探查的思路解决；

  1. 当插入新元素的时，使用哈希函数在哈希表中定位元素位置；

  2. 检查数组中该槽位索引是否存在元素。如果该槽位为空，则插⼊，否则3；

  3. 在 2 检测的槽位索引上加一定步长接着检查2； 加⼀定步长分为以下几种：

  • i+1,i+2,i+3,i+4, … ,i+n
  • i- ,i+ ,i- ,1+ , … 这两种都会导致同类 hash 聚集；也就是近似值它的hash值也近似，那么它的数组槽位也靠近，成 hash 聚集；第一种同类聚集冲突在前，第二种只是将聚集冲突延后； 另外还可以使用双重哈希来解决上面出现hash

  聚集现象：

  在.net HashTable类的hash函数Hk定义如下：

  Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) +1) % (hashsize – 1)))] % hashsize

  在此 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))) 与 hashsize 互为素数（两数互为素数表示两者没有共同的质因⼦）；执⾏了 hashsize 次探查后，哈希表中的每⼀个位置都有且只有⼀次被访问到，也就是说，对于给定的 key，对哈希表中的同⼀位置不会同时使⽤ Hi 和 Hj；

• 布隆过滤器是一种概率型数据结构，特点是高效插入跟查询，能确定某个字符串一定不存在或者可能存在
• 布隆过滤器不存在具体的数据，占用空间很小，查询存在误差，但误差可控，不支持删除操作
• 由一个数组跟n个hash函数构成
  

​ 当一个元素加入位图时，通过 k 个 hash 函数将这个元素映射到位图的k个点，并把它们置为1，当检索时，再通过 k 个 hash 函数运算检测位图的k个点是否都为1；如果有不为1的点，那么认为该key不存在；如果全部为1，则可能存在；

位图每个位只有两种状态(0和1)，一个位被设置为1，但不确定是被那个hash函数设置的也不确定设置了多少次

• 解决缓存穿透
• 描述缓存场景
• 热key限流

在实际应用中，该选择多少个 hash 函数？要分配多少空间的位图？预期存储多少元素？如何控制误差？

n -- 布隆过滤器中元素的个数，如上图 只有str1和str2 两个元素 那么 n=2 
p -- 假阳率，在0-1之间 0.000000 
m -- 位图所占空间 
k -- hash函数的个数 
公式如下： 
n = ceil(m / (-k / log(1 - exp(log(p) / k)))) 
p = pow(1 - exp(-k / (m / n)), k) 
m = ceil((n * log(p)) / log(1 / pow(2, log(2)))); 
k = round((m / n) * log(2));

在实际使用布隆过滤器时，首先需要确定 n 和 p，通过上面的运算得出 m 和 k；通常可以在下面，这个网站上选出合适的值；

布隆过滤器参数计算

• 分布式一致性哈希算法将空间组成一个虚拟的圆环，圆环大小是2³²
• 多个服务器都通过这种方式在hash环上映射一个点来标识该服务器的位置
• 当用户操作某个key，用同样的算法生成一个值，沿着环的顺时针定位某个服务器，该key就在该服务器当中

• hash算法得到的结果是随机的，不能保证服务器上的结点是均匀分布在哈希环上，分布不均会引起请求访问不均匀，服务器承压不均匀

• 为了解决哈西偏移问题，增加了虚拟节点的概念，理论上哈希环上结点数量越多，数据分布越均匀
  是均匀分布在哈希环上，分布不均会引起请求访问不均匀，服务器承压不均匀

• 为了解决哈西偏移问题，增加了虚拟节点的概念，理论上哈希环上结点数量越多，数据分布越均匀
• 为每个服务器计算多个hash结点