本文转载自: 掘金
HashMap-数据结构&哈希算法
2021年10月30日\color{#708090}{2021年10月30日}2021年10月30日
前言
--
本文主要通过以下三部分来阐述HashMap的底层实现原理：
> 1. 数据结构 & 哈希算法
> 2. 性能参数 & 扩容机制
> 3. 快速存取 & 时间复杂度
情景引入
----
工作的时候遇到了一个问题，同步过去一个商品集合，商品对象A包含了model和quantity，但是返回给我的集合对象B里只有model，没有quantity。我该怎么给返回来的对象B添加上型号对应的数量？
两种思路：
1. 嵌套循环
undefined
此方法，假设外层循环执行n次，内层循环执行m次，时间复杂度为O(n\*m)。
2. 使用HashMap
undefined
此方法，List转Map时间复杂度为O(n)，HashMap的get()方法时间复杂度是多少呢？
数据结构&哈希算法
---------
1.数据结构\color{#A0522D}{1.数据结构}1.数据结构
> **JDK1.7及之前：数组+链表**
> **JDK1.8及之后：数组+链表+红黑树**
* **数组**：是一种**线性表**数据结构。它用一组**连续的**内存空间，来存储一组具有**相同类型**的数据。支持**随机访问**，计算元素的寻址地址：
undefined
* **链表**：和数组一样，也是一种**线性表**。是**不连续的**内存空间，将一组零散的内存块串联起来，从而进行数据存储的数据结构。
* **哈希表**：综合了两种特性，是一种寻址比较高效、插入删除也高效的数据结构。哈希表有不同的实现方法，其中最常用的一种方法——拉链法，可以理解为“链表的数组”，如图：
从上图我们可以发现哈希表是由**数组+链表**组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢？一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12，28%16=12，108%16=12，140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
* **红黑树**：当链表的长度过长时，其固有弊端就显现出来了，即**查询效率较低**，时间复杂度可能会达到O(n)级别，而数组的查询时间复杂度仅为O(1)。红黑树是一棵接近于**平衡的二叉查找树**，其查询时间复杂度为**O(logn)**，远远比链表的查询效率高。但如果链表长度不到一定的**阈值**，直接使用红黑树代替链表也是不行的，因为红黑树的自身维护的代价也是比较高的，每插入一个元素都可能打破红黑树的平衡性，这就需要每时每刻对红黑树再平衡（左旋、右旋、重新着色）。
**HashMap**是Java中用**哈希表**数据结构实现的**Map**。
2.Hash算法(通俗讲，将key值转化为数组下表)\color{#A0522D}{2.Hash算法(通俗讲，将key值转化为数组下表)}2.Hash算法(通俗讲，将key值转化为数组下表)
1. JDK 1.8中，hash方法如下：
undefined
获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做**异或**运算，返回结果。举个例子：
undefined
2. 计算数组下标
通过hash方法计算得到Key的hash值后，怎么才能保证元素均匀分布到每个桶中呢？我们会想到取模，hash%len。但其实HashMap是通过**hash&(n-1)**计算index的。**因为桶数组的长度总是2的n次幂**，所以**hash&(n-1)**就**相当于**对hash对len取模，而**位运算**要比**取模运算**快得多，即两者是等价不等效的，这是HashMap在效率上的一个优化。
undefined
> **为什么计算出key的hashCode后，还要位移16位再跟自身做异或运算？**
对于初始容量1<<<4来说，如果直接用key的hashcode和数组容量做&运算，会导致只有前四位进行运算，高位没有进行运算。因为容量的高位都是0，而key的hashcode的高位都是有值的。所以为了避免key的高位的**信息丢失**，首先将高十六位右移16位与低十六做异或运算，这样混合得到的新的数值中，高位和低位的信息都保留了。这样做的目的是为了使得高位也能参与哈希，从而进一步降低**hash碰撞**的概率。下面举例说明： > **为什么计算出来hash后，还需要做取模运算？**
> 为了让HashMap存取更加高效，需要尽量减少碰撞，也就是要尽量把数据分配均匀。Hash值的范围前后加起来大概40亿的映射空间，只要哈希算法映射得足够均匀，一般很难出现碰撞，问题是一个40亿长度的数组，内存是放不下的，所以hash值不能直接拿来用，用之前还要对数组长度做取模运算，得到的余数才是对应的数组的下标。这个数组下标的计算方法就是**hash&(n-1)**
> **为什么HashMap的数组长度一定是2的幂次方？**
> 1.使用位运算来实现取模运算\color{#A0522D}{1.使用位运算来实现取模运算}1.使用位运算来实现取模运算
**当 array.ength长度是2的次幂时，** `key.hashcode % array.length`**等于**`key.hashcode & (array.length - 1)`。
X % 2^n = X & (2^n – 1)
假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 - 1 = 7, 表示成2进制是0111。
此时X & (2^3 - 1) 就相当于取X的二进制的最后三位数。为什么，因为&运算规则是：两者相同是1得1；否则得0。因为7的最后三位是1，所以最后三位数的值由X决定，X是1，则为1，X是0，则为0。
从2进制角度来看，X / 8 相当于X >> 3, 即把X右移3位，此时得到的是 X / 8 的商，而被移掉的部分（后3位），则是 X % 8，也就是余数。
所以，只要保证数组的长度是2^n的话，就可以实现用&来代替%。
2.减少哈希碰撞，提高效率\color{#A0522D}{2.减少哈希碰撞，提高效率}2.减少哈希碰撞，提高效率
基于hash & (n - 1)的策略，假设hash从0-15。
先来看length为奇数的情况，假设length = 15的情况：
从上面的图表中我们可以看到，当 length 为15时总共发生了8次碰撞，同时发现空间浪费非常大，因为在 1、3、5、7、9、11、13、15 这八处没有存放数据。
这是因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，那么最后一位为1的位置即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样，空间的减少会导致碰撞几率的进一步增加，从而就会导致查询速度慢。
再来看length为偶数的情况，假设length = 16的情况：
当length为16时，length – 1 = 15， 即 1111，那么，在进行&运算时，值总是与原来hash值相同。所以，当 length=2^n 时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。
多试一些数，就可以发现规律：当length为奇数时，length-1为偶数，而偶数二进制的最后一位永远为0，那么与其进行 & 运算，得到的二进制数最后一位永远为0，那么结果一定是偶数，那么就会导致下标为奇数的桶永远不会放置数据，这就不符合我们均匀放置，减少冲突的要求了。
然而，保证length是偶数还不够，为什么一定是2^n，这就又回到第一点的原因了。
性能参数&扩容机制
---------
1.HashMap在JDK中的定义\color{#A0522D}{1.HashMap在JDK中的定义}1.HashMap在JDK中的定义
undefined
2.重要的类的属性\color{#A0522D}{2.重要的类的属性}2.重要的类的属性
undefined
3.HashMap的构造函数\color{#A0522D}{3.HashMap的构造函数}3.HashMap的构造函数
**1. HashMap(int, float)**
undefined
*tableSizeFor(initialCapacity)* 方法返回大于initialCapacity的最小的二次幂数值。
undefined
**2. HashMap(int)**
undefined
**3. HashMap()**
undefined
**4. HashMap(Map)**
undefined
`未完待续...`