HashMap-数据结构&哈希算法
前言
本文主要通过以下三部分来阐述HashMap的底层实现原理：
数据结构 & 哈希算法
性能参数 & 扩容机制
快速存取 & 时间复杂度
情景引入
工作的时候遇到了一个问题，同步过去一个商品集合，商品对象A包含了model和quantity，但是返回给我的集合对象B里只有model，没有quantity。我该怎么给返回来的对象B添加上型号对应的数量？
两种思路：
嵌套循环
List<A> aList = new ArrayList<>(); List<B> bList = new ArrayList<>(); for(int i = 0; i < aList.size(); i++){ for (int j= 0; j < bList.size(); j++){ if(aList.get(i).getModel() == bList.get(j).getModel()){ bList.get(j).setQuantity(aList.get(i).getQuantity()); break; } } } 复制代码此方法，假设外层循环执行n次，内层循环执行m次，时间复杂度为O(n*m)。
使用HashMap
// List转Map（键为model，值为quantity） Map<String, Integer> modelAndQuantityMap = aList.stream().collect(Collectors.toMap(Product::getModel, Product::getQuantity)); for(Product product : bList){ product.setQuantity(modelAndQuantityMap.get(product.getModel())); } 复制代码此方法，List转Map时间复杂度为O(n)，HashMap的get()方法时间复杂度？
数据结构&哈希算法
1.数据结构\color{#A0522D}{1.数据结构}1.数据结构
JDK1.7及之前：数组+链表
JDK1.8及之后：数组+链表+红黑树
数组：是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。支持随机访问，计算元素的寻址地址：
a[i]_address = base_address + i * data_type_size 复制代码
链表：和数组一样，也是一种线性表。是不连续的内存空间，将一组零散的内存块串联起来，从而进行数据存储的数据结构。
哈希表：综合了两种特性，是一种寻址比较高效、插入删除也高效的数据结构。哈希表有不同的实现方法，其中最常用的一种方法——拉链法，可以理解为“链表的数组”，如图：
从上图我们可以发现哈希表是由数组+链表组成的，一个长度为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值转化为数组下表)
JDK 1.8中，hash方法如下：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 复制代码获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。举个例子：
String key = "test"; int code = key.hashCode(); // 355648 int code_16 = code >>> 16; // 54 int hash = code ^ code_16; // 3556516 /** * code: 11 0110 0100 0100 1001 0010 * code_16: 00 0000 0000 0000 0011 0110 * hash: 11 0110 0100 0100 1010 0100 */ 复制代码
计算数组下标
通过hash方法计算得到Key的hash值后，怎么才能保证元素均匀分布到每个桶中呢？我们会想到取模，hash%len。但其实HashMap是通过hash&(n-1)计算index的。因为桶数组的长度总是2的n次幂，所以hash&(n-1)就相当于对hash对len取模，而位运算要比取模运算快得多，即两者是等价不等效的，这是HashMap在效率上的一个优化。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ... if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); ... } 复制代码为什么计算出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中的定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... } 复制代码2.重要的类的属性\color{#A0522D}{2.重要的类的属性}2.重要的类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 默认的初始容量是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的填充因子0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 扩容的临界值，当实际大小（容量*填充因子）超过此值时，会进行扩容 // * 总是二次幂数值？ int threshold; // 当桶(bucket)上的结点数超过此值时，链表会转成红黑树 static final int TREEIFY_THRESHOLD = 8; // 存储元素的数组，总是2的幂次倍 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } } 复制代码3.HashMap的构造函数\color{#A0522D}{3.HashMap的构造函数}3.HashMap的构造函数
1. HashMap(int, float)
public HashMap(int initialCapacity, float loadFactor) { // 初始容量不能小于0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 初始容量不能大于最大值，否则为最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 填充因子不能小于或等于0，不能为非数字 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 初始化填充因子 this.loadFactor = loadFactor; // 初始化threshold大小 this.threshold = tableSizeFor(initialCapacity); } 复制代码tableSizeFor(initialCapacity) 方法返回大于initialCapacity的最小的二次幂数值。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } 复制代码2. HashMap(int)
public HashMap(int initialCapacity) { // 调用HashMap(int, float)型构造函数 this(initialCapacity, DEFAULT_LOAD_FACTOR); } 复制代码3. HashMap()
public HashMap() { // 初始化填充因子 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } 复制代码4. HashMap(Map<? extends K>)
public HashMap(Map<? extends K, ? extends V> m) { // 初始化填充因子 this.loadFactor = DEFAULT_LOAD_FACTOR; // 将m中所有元素添加至HashMap中 putMapEntries(m, false); } 复制代码未完待续...
作者：pikachu
链接：https://juejin.cn/post/7026323567339896869