"线性哈希"

  "动态扩展数据分布算法"

Posted by Xu on December 10, 2017

线性哈希

线性哈希是一种可动态扩展将数据均匀分布的技术,随着数据量的增加,哈希表的大小也会线性增长,常用于分布式系统和集群来有效的存储数据和负载均衡。

1. 初始化

首先我们需要对hash表各个属性进行初始化,一个哈希表的结构包括分裂点,桶编号,桶内存储key,溢出key如下:

分裂点 桶编号 桶内已存储的key 溢出的key
* 0 4,8,12  
  1 5,9  
  2 6  
  3 7,11,15,19,23  

如上图所示hash表为初始化hash表,key值的分布是根据key mod 散列系数来对应桶编号分散分布的,有几个初始值需要注意:

  • 散列系数:4,(散列系数代表数据分散的程度,因为key值的分布是根据和散列系数求余得到的,所以散列系数越大,数据的分布就越分散)
  • 散列增量:4,(初始桶的个数,且散列系数的增长也是以4为增量线性增长)
  • 桶的容量:5, (一个桶所能容纳最大的key的个数,当达到该桶的最大容量事触发分裂)
  • 分裂点:分裂点最初位于0号桶,小于分裂点所在桶编号的桶都已经发生了分裂

2. 分裂触发

当桶中已存储key的个数已超过桶的容量时发生分裂,如3号桶再添加一个key时,则溢出,触发分裂,如下图所示:

分裂点 桶编号 桶内已存储的key 溢出的key
* 0 4,8,12  
  1 5,9  
  2 6  
  3 7,11,15,19,23 27

当我们插入key 值27,根据key mod 4散列系数,可知27被插入到3号桶,此时桶内的key值已经超过桶的容量:5,溢出,触发分裂。

  1. 寻找分裂点,此时分裂位于0编号桶,故对0编号桶进行分裂。
  2. 添加桶,添加一个桶编号递增,为4号桶
  3. 增加散列系数:0编号桶的散列系数由4+4(散列增量)变成8,所以再次将0编号桶中的key以8为散列系数重新散列,得到下图:
  4. 分裂点下移
分裂点 桶编号 桶内已存储的key 溢出的key
  0 8  
* 1 5,9  
  2 6  
  3 7,11,15,19,23 27
  4 4,12  

如上图所示,虽然是3号桶溢出触发分裂,但是分裂的桶却是分裂点所在的桶,此时我们可设初始化散列函数为h0=keyMOD4,而已经分裂的桶(0号)的新散列函数为h1=keyMOD8,当对已分裂的桶进行插入时则需要使用新的散列函数进行散列分布

3. 散列系数迭代递增

当分裂点下移到最后一个桶:3号桶时,再次触发分裂时就会触发散列系数的迭代递增,增量为散列增量:4,上文提到的初始散列函数为h0=keyMOD4,和新散列函数keyMOD8,当触发散列系数迭代递增时则h0作废,h1作为旧散列函数,散列系数递增8+4:散列增量。新散列函数则变为h2=keyMOD12。且分裂点再次回到0编号桶。

分裂点 桶编号 桶内已存储的key 溢出的key
* 0 8  
  1 9  
  2 10  
  3 11,19,27,35  
  4 4,12  
  5 5  
  6 6  
  7 7,15,23,31  

上图是三号桶分裂之后的hash表

  • 如图分裂点从三号桶回到0号桶,触发散列系数迭代递增,得到新的散列函数h2=keyMOD12,旧的散列函数为h1=keyMOD8,h0作废。
  • 所有大于分裂点编号的桶使用旧hash函数进行散列,小于分裂点编号的桶使用新的hash函数进行散列
  • 直到分裂点位于最后一个7号桶时触发下一轮散列系数的迭代递增。

4.缺点

从上述线性hash的分析来看,当一个桶内存储的key达到桶的容量后触发分裂,并不能及时的对该桶进行分裂从而达到负载均衡,而是在分裂点所在的桶触发分裂,使得有可能本来负载就很少的桶将负载被分裂到两个桶,这样就非常浪费空间和资源,只要当分裂点到达满负载的桶时,才会均衡负载到新的桶。这样会多出许多不必要的分裂浪费系统资源。

其实我们可以为每一个桶添加一个标志位,确定初始化的散列系数,散列增量。初始化的时候所有桶的标志位都被清空,当该桶触发分裂时,直接对该桶进行分裂,并设置标志位。但分裂不仅仅是对该桶进行分裂,而是对该桶的上一级分裂桶一起进行新hash分布。

如下图hash表(桶的容量:4):

桶编号 桶内已存储的key flag
0 8 0
1 9 0
2 10 0
3 11,19,23,31 0

插入15:

桶编号 桶内已存储的key flag
0 8 0
1 9 0
2 10 0
3 11,19 1
7 23,31,15 0

插入7:

  1. 7mod4 = 3,发现三号桶标志位被设置,则寻找新的散列系数4+4 =8
  2. 7mod8 = 7,发现七号桶标志位没有被设置,则添加到七号桶,如下图所示
桶编号 桶内已存储的key flag
0 8 0
1 9 0
2 10 0
3 11,19 1
7 23,31,15,7 0

插入39:

  1. 39mod4 = 3,发现三号桶标志位被设置,则寻找新的散列系数4+4 =8
  2. 39mod8 = 7,发现七号桶标志位没有被设置,则添加到七号桶
  3. 此时7号桶触发分裂,分裂系数递增:8+4=12
  4. 对7号桶,及父分裂桶3号桶均以12散列系数进行新hash散列分布,如下图:
桶编号 桶内已存储的key flag
0 8 0
1 9 0
2 10 0
3 15, 1
7 31,7,19 1
11 23 11 0

插入35:

  1. 35mod4 = 3,发现三号桶标志位被设置,则寻找新的散列系数4+4 =8(此时的标志位应该以分裂的子桶为准)
  2. 35mod8 = 3,发现三号桶被分裂的子桶7号桶标志位被设置,则寻找新的散列系数8+4 =12(此时的标志位应该以分裂的子桶为准)
  3. 35mod12 = 11, 发现7号桶被分裂的子桶11号桶标志位没有被设置,插入到11号桶
桶编号 桶内已存储的key flag
0 8 0
1 9 0
2 10 0
3 15, 1
7 31,7,19 1
11 23 11,35 0