哈希表的原理（哈希表基本原理）

HashMap是Java面试中的一个基础面试题，基本上是必问的，但是好多小伙伴多多少少都看过HashMap的源码流程分析，但是却不知道HashMap是基于怎样的一个数据结构来实现的，也就是对哈希表的了解很少，这样肯定就会导致好多小伙伴在看HashMap源码的时候对于一些提到的处理流程，会感觉懵懵懂懂，似懂非懂的。要想真正搞懂HashMap的底层原理，必须要先搞懂哈希表是什么。今天，咱们就一起讨论一下哈希表这种数据结构到底是什么样的。

1、什么是哈希表？

我们先来想一下，如何在一组没有顺序的数据中找到指定的数据？既然是无序的，那我们肯定要遍历这一组数据，然后逐个与要查找的元素进行比较，这就意味着查找这个元素的时间复杂度为O(n)。在数据量很庞大的时候，即便是时间复杂度为O(n)的操作也是非常耗性能的。那么有没有一种数据结构，这个数据结构中的每一个元素都与这个元素所在的位置之间存在一个对应关系，这样的话，我们每次查找时，知道了这个对应关系，通过对应关系，可以直接计算出元素所在的位置，时间复杂度为O(1)，可以大大节省程序查找的效率，这种数据结构就是我们要说的哈希表。

先来看一下哈希表的官方定义：

哈希表又叫散列表，是一种根据设定的映射函数f(key)将一组关键字映射到一个有限且连续的地址区间上，并以关键字在地址区间中的“像”作为元素在表中的存储位置的一种数据结构。这个映射过程称为哈希造表或者散列，这个映射函数f(key)即为哈希函数也叫散列函数，通过哈希函数得到的存储位置称为哈希地址或散列地址

定义看起来就是很别扭，我们通俗点来讲，哈希表就是通过一个映射函数f(key)来表示数组中每个元素和这个元素所在位置的关系。

举个例子，有一组数据：[18,23,5,32,50,14]，我们用散列存储的方式将其存储在一个长度为11的数组中。采用除留取余法，将这组数据分别模上数组的长度（即f(key)=key % 11），以余数作为该元素在数组中的存储的位置。则会得到一个如下图所示的哈希表：

此时，如果我们想从这个表中找到值为14的元素，只需要将14模上11即可得到14在数组中的存储位置。可见哈希表对于查找元素的效率是非常高的。

2、什么是哈希冲突

我们在上面举了例子来说明什么是哈希表，并且看到了在哈希表中查找元素是多么快，那么现在我们要往这一组数据中再插入几个元素，比如插入 33 、34 ，插入33时，先计算33要插入的位置，33 % 11 = 0，所以33这个元素插入数组中0号位置。

然后再插入34，使用34%11 = 1，确定了34这个元素要插入数组中的1号位置，但是1号位置已经存在了元素23了，这个时候34应该放在哪里呢？

对于这种情况，我们就叫做哈希冲突，哈希冲突的官方定义为：

对于不同的关键字，可能得到同一个哈希地址，即key1≠key2,而 f(key1)=f(key2)，对于这种现象我们称之为哈希冲突，也叫哈希碰撞

这个官方定义看起来比较简单一些，容易理解，就是不同的关键字，也就是要插入的数组元素，经过哈希函数计算可能得到相同的哈希地址。

一般哈希冲突只能尽量地减少，无法完全避免。因为哈希函数是从关键字集合到地址集合的映射，通常来说关键字集合是比较大的，因关键字在理论上可以是有无限多个的，而用来存储这些关键字的数组容量是有限的，这就导致了哈希冲突的必然性。

2.1 如何减少哈希冲突？

虽然哈希冲突无法完全避免，但是我们还是可以通过选择合适的哈希函数，来降低哈希冲突发生的概率。常用的哈希函数有以下几种：

• 除留取余法
• 取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址。即：f(key)=key % p, p≤m;
• 直接定址法
• 直接定址法是指取关键字或关键字的某个线性函数值为哈希地址。即：f(key)=key 或者 f(key)=a*key+b、
• 数字分析法
• 假设关键字是以数值为基的数（如以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可以选取关键字的若干位数组成哈希表。

除了上面这几种哈希函数，还有很多种。总之，选取合适的哈希函数是可以有效减少哈希冲突的。

2.2 如何处理哈希冲突？

虽然可以选择合适的哈希函数来减少哈希冲突，但是哈希冲突还是会发生的，如果碰到了哈希冲突，我们应该如何解决呢？

（1）开放定址法(线性探测再散列)

开放定址法是指当发生哈希冲突的时候，按照某种方法继续探测哈希表中的其他存储位置，一直找到空位置为止。

刚刚我们在开头演示插入元素时，在插入34这个元素时，发现要插入的位置已经存在元素了，我们用开放定址法来解决这个哈希冲突。

过程分析：

第一次计算34要插入的位置是1号位置，而1号位置已经存在元素23了，那么就将1加1得到2，然后再查看2号位置是否有元素，发现2号位置是空的，那么就可以把34这个元素放在2号位置了。得到以下的哈希表：

（2）再哈希法

再哈希法就是选取几个不同的哈希函数，当发生哈希冲突的时候，就换一个哈希函数计算结果，直到不再发生冲突为止。

（3）链地址法

链地址法是指碰到哈希冲突的时候，将冲突的元素以链表的形式进行存储。也就是只要哈希地址相同的元素，都插入到同一个链表中，元素的插入方式可以是头插法，也可以是尾插法。

我们以[33,23,34,14,5,50,18,32] 这一组数据为例，使用链地址法解决哈希冲突。得到如下图所示的哈希表：

再插入一些数据[22,44,25,55,36,47]，使用链地址法得到如下的哈希表:

3、链地址法的弊端与优化

链地址法是比较常用的一种解决哈希冲突的方式，HashMap就是基于链地址法的哈希表结构。虽然这是一种不错的处理方式，但是也存在一些明显的弊端。在极端情况下，他的查询时间复杂度还是会达到O(n)级别。比如我们继续为上面的例子中插入数据[48,15,26,4,70,82,59]，此时的哈希结构会变成如下：

这个时候哈希表已经退化成了一个普通的链表，在这种结构下去查找一个元素，时间复杂度是O(n)，所以当哈希表中的链表过长的时候，我们就要对其进行优化处理。二叉树的查找效率是要高于链表的。因此，我们可以在链表达到一定长度的时候，把链表转化成一棵树，HashMap的源码中也是这么做的，当数组的长度大于64，且arr[i]位置上的链表的长度大于8时，就会把arr[i]上的链表转换成一棵红黑树。上面的数据经过树化之后得到的结果如下：

红黑树是一个可以自平衡的二叉查找树。它的查询的时间复杂度为o(lgn)。通过这样的优化可以提高哈希表的查询效率。

4、哈希表的扩容与Rehash

在哈希表长度不变的情况下，随着哈希表中插入的元素越来越多，那么发生冲突的概率必然会越来越大，相应的查找效率也会越来越低。这就说明影响哈希表性能的因素除了哈希函数和处理冲突的方法之外，还与哈希表的装填因子有关。

哈希表中元素的个数与哈希表的长度之间的比值称为装填因子。

装填因子 α = 哈希表中元素个数/哈希表长度

从上面的公式可以看出，装填因子α的值越小，产生哈希冲突的概率也就越小，查找的效率也就越高。而减小α装填因子的方式就是扩大哈希表的容量，但是这样会降低哈希表的使用率，这是一个矛盾关系，没有完美的解决方案，只能根据实际场景设置最佳的装填因子，一般装填因子设置的范围是在0.65 ~ 0.9 之间。而HashMap的装填因子设置的是 0.75。一旦HashMap的装填因子大于0.75的时候，为了减少哈希冲突，就需要对哈希表进行扩容的操作了。比如我们把原来的哈希表长度扩大2倍。

扩容并不是在原有的基础上进行扩容，而是重新生成一个长度为2倍的哈希表。因此扩容之后就需要把原来哈希表中的数据从新进行哈希地址的计算，然后存放到新的哈希表中，这个过程我们称之为 Rehash。

HashMap源码中定义的默认装填因子为0.75：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

我们以[19,24,6,33,51,15,25,72,37,17,4,55,83]这组数据为例来演示哈希表扩容与Rehash的过程。假设哈希表的初始长度为11，装载因子的最大值定为0.75，扩容前的数据插入如下图所示：

当我们插入第9个元素的时候发现此时的装填因子已经大于0.75了，因此要触发一次扩容操作。我们将数组大小扩容2倍，扩容后将已经存在于哈希表中的数据重新计算哈希地址，然后再放入对应位置，会得到如下结果：

我们可以明显看到，扩容之后的元素存放位置与扩容之前可以说是完全不同。

Rehash的操作将会把已经存储的数据全部重新计算哈希地址，这样的操作会涉及大量元素的移动，也是一个非常耗性能的操作，因此我们在开发中尽量避免Rehash的出现，提前预估好元素的个数，指定哈希表的长度，这样就可以有效的减少Rehash了，比如HashMap的默认初始容量为16。源码中的定义如下：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

5、总结
哈希表是数据结构中一个非常重要的知识点。哈希表弥补了线性表或者树的查找效率低的问题，通过哈希表我们可以把查找某个元素的时间复杂度降低到O(1)，但是哈希表本身也存在哈希冲突和Rehash等问题，没有完美的解决方案，为了尽量减少这些问题的出现，我们只能根据实际情况选择最佳的设定方案来降低问题出现的概率。

理解了哈希表之后，对于我们理解HashMap的底层原理有很大帮助，因为HashMap本身就是基于哈希表实现的。