哈希算法&一致性哈希

传统hash算法

一致性哈希算法（分布式系统负载均衡的首选算法）

对key进行hash计算后对2^32取模，并按顺时针方式为数据寻找存储的节点
流程
- 组织hash环：将0~2^32-1数字按顺时针方向组织成一个圆环
- 确定服务器在哈希环上位置：对服务器的key进行hash计算后对2^32取模，得到的数据就是在哈希环上的位置
- 将数据映射到哈希环上：对数据的key进行hash计算后对2^32取模得到映射后的数据，然后按顺时针方向计算，将数据存储到离自己最近的机器中
  - 1和2被存储到A中，3被存储到B中，4被存储到C中
优点
- 节点的增加
  - 比如增加节点D被映射到CB节点中间，这样子就会4就会被迁移到D中，其他对象还是保持原有的存储位置
- 节点的删除
  - 比如B节点被删除了，按照顺时针迁移的方法3会被存储到C节点中，只是3的映射位置发生改变，其他数据没有改动
- 节点的增减只需要重定位环空间中的一小部分数据，只有部分缓存会失效
缺点
- hash环倾斜：在节点太少情况下容易因为节点分布不均匀造成数据倾斜（缓存对象大部分集中在某一台服务器上）
- 虚拟节点机制：对每一个节点计算多个哈希，每个计算结果都放置一个该服务节点，这样子一个实际的节点就会对应多个虚拟节点，虚拟节点越多，hash环上节点越多，缓存被均匀分布的概率就越大，hash环倾斜影响就越小

为什么hashmap是两倍扩容

首先需要直到hashmap中数据是怎么分配的
- 要存入一个数据前会先对key进行哈希计算后得到hash值，再将hash值和（哈希表长度-1）做按位与运算
- 采用按位与是因为计算机中按位运算的效率比较高，不用%
由于哈希表长度是2倍扩容，所以哈希表长度减1后所有的二进制位都是1，在于数据hash值做按位于的时候数据能够充分扩散开减少哈希碰撞（否则如果有1个位置是0就导致这个位置得到的结果是0，也就是说将位置的影响交给数据，不交给哈希表长度）
尽可能减少元素位置的移动
- 以二次幂扩容容器中的元素要么保持原来的位置，要么以二次幂的偏移量出现在新表中