一致Hash（一）

图片来自于百度图片

内容提前知

1、Hash表

2、Hash函数

3、hashMap中的默认容量和加载因子

4、java中的hashCode方法

5、分布式中hash

Hash表

将key进行hash运算，得到一个int值，此值就是我们初始化时候新建的一个数组的下标，将value放进这个下标表示的内存中。因此我们可以看出hash查找数据很快，但是插入很慢。那么当出现两个数据的hash值一致，我们应该怎么办呢?在Java中使用单链表来解决。

如 ：key（A）的hash为1，key（b）的hash也为1，则按照下面的方式进行存储

Hash函数

有很多获取一个key的hash算法，如下面的三种：

直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。

数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

hash函数的选择，通常考虑以下因素：

· 计算哈希函数所需时间

· 关键字的长度

· 哈希表的大小

· 关键字的分布情况

· 记录的查找频率

hashMap中的默认容量和加载因子

默认容量决定了初始创建的数组大小，而默认容量*加载因子决定了当数组个数达到多少的时候对数组进行扩容（新创建更大空间，将原数组进行复制）。因此这两个数极大的决定了hash的性能。

java中的hashCode方法

我们先来看看String类中的hash算法，其实就是采用了上面所讲到的直接寻址法。

分布式中hash

一致性哈希算法被广泛的应用在分布式系统中，那么为什么叫一致性hash算法的呢？先看下面的情景：

假设我们现在有10台服务器，采用Hash方式对数据分片存储，将使用hash(file) % 10来定位数据存储的服务器。某一天发现10台服务器缓存太小，我们需要加服务器，这个时候的服务器变为了11台，取数据的服务器定位方式就变为hash(file) % 11，导致不能定位到之前存储数据的服务器。为了规避这种情况，就需要保证不管我的服务器怎么变化，都可以把数据得到，因此就需要保证hash的一致性，这就是一致性hash算法。

下期预告

下期将主要分享分布式一致Hash的算法和原理！

如果你对Linux、Java后端、分布式系统感兴趣，扫描上方二维码，欢迎加入我们的知识星球