哈希表基本原理你都不懂，还敢说你能看懂HashMap？
HashMap是Java面试中的一个基础面试题，基本上是必问的，但是好多小伙伴多多少少都看过HashMap的源码流程分析，但是却不知道HashMap是基于怎样的一个数据结构来实现的，也就是对哈希表的了解很少，这样肯定就会导致好多小伙伴在看HashMap源码的时候对于一些提到的处理流程，会感觉懵懵懂懂，似懂非懂的。要想真正搞懂HashMap的底层原理，必须要先搞懂哈希表是什么。今天，咱们就一起讨论一下哈希表这种数据结构到底是什么样的。
1、什么是哈希表？
我们先来想一下，如何在一组没有顺序的数据中找到指定的数据？既然是无序的，那我们肯定要遍历这一组数据，然后逐个与要查找的元素进行比较，这就意味着查找这个元素的时间复杂度为O(n)。在数据量很庞大的时候，即便是时间复杂度为O(n)的操作也是非常耗性能的。那么有没有一种数据结构，这个数据结构中的每一个元素都与这个元素所在的位置之间存在一个对应关系，这样的话，我们每次查找时，知道了这个对应关系，通过对应关系，可以直接计算出元素所在的位置，时间复杂度为O(1)，可以大大节省程序查找的效率，这种数据结构就是我们要说的哈希表。
先来看一下哈希表的官方定义：
定义看起来就是很别扭，我们通俗点来讲，哈希表就是通过一个映射函数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应该放在哪里呢？
对于这种情况，我们就叫做哈希冲突，哈希冲突的官方定义为：
2.1 如何减少哈希冲突？
虽然哈希冲突无法完全避免，但是我们还是可以通过选择合适的哈希函数，来降低哈希冲突发生的概率。常用的哈希函数有以下几种：
除留取余法
直接定址法
数字分析法
假设关键字是以数值为基的数（如以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可以选取关键字的若干位数组成哈希表。
除了上面这几种哈希函数，还有很多种。总之，选取合适的哈希函数是可以有效减少哈希冲突的。
2.2 如何处理哈希冲突？
虽然可以选择合适的哈希函数来减少哈希冲突，但是哈希冲突还是会发生的，如果碰到了哈希冲突，我们应该如何解决呢？
（1）开放定址法(线性探测再散列)
开放定址法是指当发生哈希冲突的时候，按照某种方法继续探测哈希表中的其他存储位置，一直找到空位置为止。
刚刚我们在开头演示插入元素时，在插入34这个元素时，发现要插入的位置已经存在元素了，我们用开放定址法来解决这个哈希冲突。
过程分析：
第一次计算34要插入的位置是1号位置，而1号位置已经存在元素23了，那么就将1加1得到2，然后再查看2号位置是否有元素，发现2号位置是空的，那么就可以把34这个元素放在2号位置了。得到以下的哈希表：
（2）再哈希法
再哈希法就是选取几个不同的哈希函数，当发生哈希冲突的时候，就换一个哈希函数计算结果，直到不再发生冲突为止。
这个时候哈希表已经退化成了一个普通的链表，在这种结构下去查找一个元素，时间复杂度是O(n)，所以当哈希表中的链表过长的时候，我们就要对其进行优化处理。二叉树的查找效率是要高于链表的。因此，我们可以在链表达到一定长度的时候，把链表转化成一棵树，HashMap的源码中也是这么做的，当数组的长度大于64，且arr[i]位置上的链表的长度大于8时，就会把arr[i]上的链表转换成一棵红黑树。上面的数据经过树化之后得到的结果如下：
红黑树是一个可以自平衡的二叉查找树。它的查询的时间复杂度为o(lgn)。通过这样的优化可以提高哈希表的查询效率。
4、哈希表的扩容与Rehash
在哈希表长度不变的情况下，随着哈希表中插入的元素越来越多，那么发生冲突的概率必然会越来越大，相应的查找效率也会越来越低。这就说明影响哈希表性能的因素除了哈希函数和处理冲突的方法之外，还与哈希表的装填因子有关。
哈希表中元素的个数与哈希表的长度之间的比值称为装填因子。
装填因子 α = 哈希表中元素个数/哈希表长度
从上面的公式可以看出，装填因子α的值越小，产生哈希冲突的概率也就越小，查找的效率也就越高。而减小α装填因子的方式就是扩大哈希表的容量，但是这样会降低哈希表的使用率，这是一个矛盾关系，没有完美的解决方案，只能根据实际场景设置最佳的装填因子，一般装填因子设置的范围是在0.65 ~ 0.9 之间。而HashMap的装填因子设置的是 0.75。一旦HashMap的装填因子大于0.75的时候，为了减少哈希冲突，就需要对哈希表进行扩容的操作了。比如我们把原来的哈希表长度扩大2倍。
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，扩容前的数据插入如下图所示：
我们可以明显看到，扩容之后的元素存放位置与扩容之前可以说是完全不同。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
5、总结
哈希表是数据结构中一个非常重要的知识点。哈希表弥补了线性表或者树的查找效率低的问题，通过哈希表我们可以把查找某个元素的时间复杂度降低到O(1)，但是哈希表本身也存在哈希冲突和Rehash等问题，没有完美的解决方案，为了尽量减少这些问题的出现，我们只能根据实际情况选择最佳的设定方案来降低问题出现的概率。
理解了哈希表之后，对于我们理解HashMap的底层原理有很大帮助，因为HashMap本身就是基于哈希表实现的。
如果本篇文章对你有帮助，可以点点关注，后续会继续更新与HashMap相关的技术点。