新手小白浅析哈希表

猫猫的窝 11-26 1523

前言：

当前小伙伴们对“一致性哈希算法优缺点”大约比较着重，看官们都需要知道一些“一致性哈希算法优缺点”的相关资讯。那么小编同时在网摘上收集了一些对于“一致性哈希算法优缺点””的相关资讯，希望同学们能喜欢，看官们一起来了解一下吧！

一.概念

一种数据结构，用于存放数据，HashTable（哈希表）=散列表

hash算法基本原理：是把任意长度的输入变成固定长度的输出

哈希函数：根据关键字设计的，有很多种函数，主要原理是根据数组的大小进行求模运算，其数组的大小一般设计为质数，因为需要均匀的散布

二.构建方法

举例：上学每个人都有学号，学号对应名字

key value

学号姓名

1 ：张三

2 : 李四

3 : 王五

需求：根据学号3迅速得到对应姓名

一般我们从头遍历到尾，先去查1然后2，最后3，如果有一万个、那岂不是需要遍历一万次呢，此种做法非常慢，不可以取

数组的结构可以使我们快速定位到3，数组有下标、索引的概念，把学号当做索引，根据索引计算对应的元素内存在哪里，

比如a数组存以下数据

我们只需要看a[3]所对应的值是什么，不需要看a[1],a[2],，这样查询非常块，就算有一万个元素，也可以一步到位，不需要从头遍历到尾

以上也为一种意义上的哈希表，把key转换为索引，数组的元素存的是key对应的value的值

三.结构理解

像HashMap里面有写好哈希表，当存储一对key-value键值对元素的时候,把key拿出来，通过一个hash函数，找到一个内存地址，然后key和value键值对Entry放在对应的内存地址上

举例：存学号1:张三

把1 拿出来通过hash函数，找到内存地址a ，内存地址a上对应着键值对 1：张三

1 a:1 张三

2 b:2 李四

3 c:3 王五

四.哈希碰撞

1 现象

定义：两个不同的key，通过同一个hash函数，得到的相同的内存地址，此种情况为哈希碰撞

举例：

key 1通过hash函数找到内存地址a,

key 2通过hash函数找到内存地址b

key 3通过hash函数找到内存地址c

此时有数据 4：赵六，拿key 4 通过hash函数算的内存地址也是c,但此时内存地址c已经存储了元素，此种现象为哈希碰撞O(K),k为碰撞的元素个数

2 链表式解决方案

链表，每一块内存有一个空间引用保存这下一块内存的地址

每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题，此种方案叫链表式解决方案。

3 开放地址解决方案

思想：与链表式解决方案相比，此种方案主要区别是不用next指针，把其它下标的位置都对外开放

3.1 线性探测法

tips:该方法不是很好，很容易把数字聚集到一个地方，查找容易浪费性能，执行很多次

如果遇到冲突，就往下一个地址寻找空位，新位置=原下标位置+i (i是查找的次数)

如图：以下关键字2，38，28，4，12存入理解

当存入关键字2时

hash(2)=2,此时数组下标的位置有元素，已被占用，就往下找，数组下标3的位置为空，因此关键字2存在数组下标为3的位置

当存入关键字38时

hash(38)=12,数组下标12的位置没有元素，可直接将38存入

当存入关键字28时

hash(28)=2,下标2位置已被占用，由于是线性探测法，可一直往下找到空的位置，所以关键字28放入下标为4的位置，同理，关键字4存入下标为5的位置

当存入关键字12时

hash(12)=12，位置已被占用，就会转回来从头开始寻找，存入下标为0的位置

3.2 平方探测法

如果遇到冲突，就往（原始位置+i²）的位置寻找空位，i是查找的次数

即新位置=原始位置+i²

1²，2²，3²，4²，5²，6² 距离越来越大比较分散，不扎堆，解决了线性探测法扎堆的问题

也由关键字2，28，19，10 存入举例说明

当存入关键字2时

hash(2)=2，下标为2的位置已被占用，用平方探测法探测下一个位置是否为空，

第一次探测1²=1，是空的，可以直接放入

当存入关键字28时

hash(28)=2,下标为2位置已被占用，平方探测法探测

第一次探测1²，下标2+1²=3的位置被关键字2占用，

第二次探测2²，下标2+4=6的位置未被占用，可直接放入

当存入关键字19时

hash(19)=6,下标为6的位置被占用，平方探测法探测

第一次探测1²，下标6+1²=7的位置未被占用，可直接存入

当存入关键字10时

hash(10)=10,下标为10的位置未本占用，可直接存入

3.3 双哈希

要设置第二个hash函数，hash2(key)=R-(key mod R) 其中R 要取比数组尺寸下的质数

如R=7: hash2(关键字)=7-（关键字 % 7）也就是说二次hash的结果在1-7之间，不会等于0，（如果为0，则新位置=原位置，不合理）

如遇到冲突，新位置=原位置+i*hash2(key) 可以让数字没有太多规律的分配

由以下关键字举例说明

当存入关键字15时

hash(15)=2,数组下标为2的位置未被占用，可直接存入

当存入关键字2时

hash(2)=2,数组下标为2的位置被占用，出现冲突，

需要计算hash2(2)=5,新位置下标=2+5=7，位置为空，可以直接放入

当存入关键字18时

hash(18)=5,数组下标为5的位置为空，可直接放入

当存入关键字28时

hash(28)=2,产生冲突

需计算hash2（28）=7，存储位置为7+2=9

4 一致性hash算法

4.1 衍生场景

场景：分布式缓存中，有三条服务器S0,S1,S2 同时有3万张图片想均匀的缓存到3台服务器

hash算法：hash(图片名称)=图片名称 mod 机器数3 结果为0，1，2三种情况，正好与服务器编号对应，缓存对应的服务器上

假如：图片名称为6,hash(6)=6%3=0,缓存到服务器S0上

缺陷：服务器增加一台，由3台变成4台，同一图片名称hash函数计算，除数由3变成4，余数变化，即该缓存的服务器编号变化了

比如原先的图片名称6 ，hash（6）=6%4=2，程序会到服务器S2上去寻找图片，但实际上是存储在服务器S0上，读取不到数据。由于服务器数量发生变化，大量缓存在同一时间失效，称为缓存雪崩此时，只有去后端服务器上获取数据，压力都在后端服务器，整个系统可能被压垮，为避免此问题，需使用一致性hash算法。

4.2 原理

有一个圆环（hash环），有2的32次方个点组成，还是有A,B,C三条服务器

hash(A)=A%(2的32次方) 得出的整数代表服务器A,hash环上必定有一点对应，服务器A映射到hash环上，服务器B、C一样的方法。

同理，hash(a.jpg)%(2的32次方)也映射到hash环上

此时图片和服务器都被映射到hash环上

接下来怎么确定图片被缓存到哪台服务器上呢？

从图片的位置开始，顺时针查找，遇到的第一台服务，为该图片应该缓存的服务器

假设有a.jpg,b.jpg,c.jpg,由以下图片和服务在hash环上的位置，由此可确定

a.jpg被缓存到服务器B上,

b.jpg被缓存到服务器C上

c.jpg被缓存到服务器A上

此时，加入增加一台服务器D,按一致性hash算法规则，现将服务器D映射到hash环上，此时一部分图片延顺时针方向遇到的服务器由A变成服务器D，增加一台服务会导致一小部分图片无法访问，但大部分图片顺时针方向遇到的服务器不变，可以正常访问。