JDK1.8 HashMap数据结构介绍
默认JDK8，如果有错误，麻烦在评论区告诉我一下😁
哈希表
哈希表（Hash table，也叫散列表），能够根据键(key)直接访问相应的值(value)。查找算法分为两步:
- 用哈希函数将被查找的key转化为数组的一个索引。理想情况下，不同的key都会转化为不同的索引值，但现实情况也会存在不同的key有相同的索引值。这就叫碰撞冲突，可以通过拉链法或线性探测法解决冲突(后面会讲)。
- 通过生成的索引值直接访问数据。
哈希表是算法在时间和空间上做出权衡的经典案例。如果没有内存限制，那么我们可以直接将key作为数组的索引，那么所有的查找操作只需要访问内存一次；如果没有时间限制，我们可以用无序数组并进行顺序查找，这样只需要很少的内存，但花费的时间太长了。而哈希表则使用了适度的空间和时间并在这两种极端中找到一个平衡。
哈希函数
假设有一个能够保存M个键值对的数组，那么我们就需要一个能够将任意key转化为该数组范围内的索引([0,M-1]范围内的整数)的哈希函数。这个哈希函数最好还要满足下面的要求:
- 容易计算并且速度快。
- 计算出来的索引值最好能够均匀分布所有的键，避免产生太多的冲突。
由于key的类型可能是数字，字符串，所以我们需要设计不同的哈希函数来对应不同的键。Java中为许多常用的数据类型重写了hashCode()方法，在文章Object中的hashCode()终于搞懂了！！！有详细的介绍。
冲突解决
当出现两个或多个key的哈希值相同的情况，可以通过拉链法或线性探测法来解决，这篇文章着重讲解一下拉链法，因为HashMap的底层实现就是基于拉链法。
大致思路如下:将大小为M的数组中的每个元素指向一个链表，链表中的每个结点都存储了哈希值为该元素的索引的键值对。当要查找某个元素时，首先根据哈希值找到对应的链表，然后沿着链表顺序查找相应的key，并返回value。
位运算符
在介绍HashMap之前补充一些位运算符的知识
<<：左移，空位补0，被移除的高位丢弃，空缺位补0。>>: 右移，被移位的二进制最高位是0，右移后，空缺位补0；最高位是1，空缺位补1。>>>: 无符号右移，被移位二进制最高位无论是0或者是1，空缺位都用0补。&: 与运算，二进制位进行&运算，只有1&1时结果是1，否则是0;|：或运算，二进制位进行 | 运算，只有0 | 0时结果是0，否则是1;^:异或运算，相同二进制位进行 ^ 运算，结果是0；1^1=0,0^0=0；不相同二进制位 ^ 运算结果是1。1^0=1,0^1=1~:取反运算，正数取反，各二进制码按补码各位取反负数取反，各二进制码按补码各位取反
HashMap简介
HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突 (两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同) 而存在的（“拉链法”解决冲突）。
JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。
补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。
这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡 。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。具体可以参考 treeifyBin方法。
虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变的更高效。
继承关系
HashMap类实现了一个Map接口，该接口定义了一组键值对映射通用的操作,同时还继承了AbstractMap抽象类，该抽象类继承Map接口。但是HashMap类通过继承AbstractMap抽象类也实现了Map接口，是不是多此一举呀?
据 Java集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。 StackOverFlow问题链接
HashMap还实现了Cloneable接口和Serializable接口，分别用来进行对象克隆和对象序列化。
成员变量
下面介绍几个重要的变量
DEFAULT_INITIAL_CAPACITY(默认集合初始容量)
//默认初始容量是16(必须是2的n次幂)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16可以发现初始容量必须是2的n次幂，具体原因下面分析一下:根据哈希表的原理，我们可以知道当向HashMap中添加一个元素时，需要根据key的哈希值去确定其在数组中的具体位置。HashMap为了存取高效，要尽量减少冲突碰撞，也就是要尽量把数据分配均匀，每个链表长度大致相同。
key的哈希值可能是一个很大的整数，超过散列表的范围，因此需要把它缩小到适合索引的范围。假设假设哈希表的索引处于0到n-1之间，将一个整数缩小到0和n-1之间的最常用的做法是使用hash%n,其中n为大于2的素数。比如Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。理想情况下应该为n选择一个素数，但是选择一个大的素数将很耗时。而在HashMap中使用的方法很巧妙，它通过hash&(length-1)来计算，当length长度为2的n次幂时，hash&(length-1)的运算结果总是等价于hash%length，&的运算效率也比%更高。
在创建HashMap对象的时候，可以传入initialCapacity，如果输入的大小不是2的n次幂，那么底层会通过位移运算和或运算得到一个离你传入的数字最近的一个2的幂次数。
源码如下:
//创建HashMap集合的对象，指定数组长度是10，不是2的幂
HashMap hashMap = new HashMap(10);
-----------------------------------------------
/* 指定“容量大小”和“加载因子”的构造函数 initialCapacity: 指定的容量 loadFactor:指定的加载因子 */
public HashMap(int initialCapacity, float loadFactor) {
//判断初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判断负载因子loadFactor是否小于等于0或者是否是一个非数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
/** * tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会 * 变为比指定初始化容量大的最小的2的n次幂。但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了， * 并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写： * this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; * 这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。 * 但是，请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化， * table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算，put方法的具体实现我们下面会进行讲解 */
this.threshold = tableSizeFor(initialCapacity);
}
最后调用了tableSizeFor，来看一下方法实现：
/** * Returns a power of two size for the given target capacity. 返回比指定初始化容量大的最小的2的n次幂 */
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;
}tableSizeFor(int cap) 是解决initialCapacity不是2的n次幂的核心方法。过程如下图：
这里说两个问题：
- 首先，为什么要对cap做减1操作，
int n = cap - 1？这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。比如传入16，如果不减1，最后结果会是32，读者可以进行测试。 - 容量最大也就是32bit的正数，因此最后
n |= n >>> 16，最多也就32个1，但是这已经是负数了。在执行tableSizeFor之前，其实会对initialCapacity做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY(2 ^ 30)，会执行移位操作。所以这里面的移位操作之后，最大30个1，不会大于等于MAXIMUM_CAPACITY。30个1，加1之后得2 ^ 30 。
DEFAULT_LOAD_FACTOR
static final float DEFAULT_LOAD_FACTOR = 0.75f;默认的装载因子，用于衡量HashMap满的程度，计算HashMap的实时装载因子loadFactor的方法是size/capacity。size是当前HashMap中存放键值对的数量，capacity是桶的数量。默认值为0.75，loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散 。这是对空间和时间效率的一个平衡选择，建议不要修改。
当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。，所以开发中尽量减少扩容的次数，可以通过创建HashMap集合对象时指定初始容量来尽量避免。
TREEIFY_THRESHOLD
//当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，数组长度大于64且链表长度达到8就转成红黑树，当长度降到6就转成普通bin。
//当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
//当集合中的容量大于这个值时，表中的桶才会进行树形化，否则桶内元素太多时会扩容。
static final int MIN_TREEIFY_CAPACITY = 64;这样就解释了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，其实就是空间和时间的权衡。
这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。 不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，不是随便决定的，而是根据 概率统计决定的。由此可见，发展将近30年的Java每一项改动和优化都是非常严谨和科学的。
也就是说：选择8因为符合泊松分布，超过8的时候，概率已经非常小了，所以我们选择8这个数字。
table
//存储元素的数组
transient Node<K,V>[] table;在JDK8中我们了解到HashMap是由数组加链表加红黑树来组成的结构，其中table就是HashMap中的数组，JDK8之前数组类型是Entry<K,V>类型。从JDK8之后是Node<K,V>类型。只是换了个名字，都实现了一样的接口：Map.Entry<K,V>。负责存储键值对数据的。
threshold
// 临界值 当实际大小(容量*负载因子)超过临界值时，会进行扩容
int threshold;计算公式：capacity(数组长度默认16) /* loadFactor(负载因子默认0.75)。这个值是当前已占用数组长度的最大值。当size>=threshold的时候，那么就要考虑对数组的resize(扩容)，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍。
添加元素
流程
put方法还是比较复杂的，步骤大致如下:
先通过hash值计算出key映射到哪个桶；
1.
如果桶上没有碰撞冲突，则直接插入；
1.
如果出现碰撞冲突了，则需要处理冲突：
- 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；
- 否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；
如果桶中存在重复的键，则为该键替换新值value；
*
如果size大于阈值threshold，则进行扩容；
源码
具体的方法如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}我们可以看到在putVal()方法中key在这里执行了一下hash()方法。确定哈希桶数组索引位置需要下面三步:
- 取hashCode值，
key.hashCode()。 - 高位参与运算，h>>>16。
- 取模运算，(n-1)&hash。
来看一下Hash方法是如何实现的。
static final int hash(Object key)
{
int h;
/* 1）如果key等于null： 可以看到当key等于null的时候也是有哈希值的，返回的是0. 2）如果key不等于null： 首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值 */
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}hashCode()得到的是一个32位int类型的值，通过hashCode()的高16位异或低16位实现，如果当n即数组长度很小，假设是16的话，那么n-1即为 00000000 00000000 00000000 00001111 ，这样的值和hashCode()直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。例如下面这个例子，hashCode值的红色部分再怎么变化也没用，如果hashCode值的红色部分变了，黑色部分没变，就会造成索引结果仍然是10，从而造成了哈希冲突。
获取桶数组索引的步骤如下:
现在看putVal()方法，看看它到底做了什么。
主要参数：
- hash： key的hash值
- key： 原始Key
- value： 要存放的值
- onlyIfAbsent： 如果true代表不更改现有的值
- evict ：如果为false表示table为创建状态
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/* 1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。 2）(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null，第一次肯定是null 3）(n = tab.length) == 0 表示将数组的长度0赋值给n,然后判断n是否等于0，n等于0 由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化。并将初始化好的数组长度赋值给n. 4）执行完n = (tab = resize()).length，数组tab每个空间都是null */
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/* 1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中 2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p 3) (p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null， 如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的桶中 小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置 */
if ((p = tab[i = (n - 1) & hash]) == null)
//创建一个新的节点存入到桶中
tab[i] = newNode(hash, key, value, null);
else {
// 执行else说明tab[i]不等于null，表示这个位置已经有值了。
Node<K,V> e; K k;
/* 比较桶中第一个元素(数组中的结点)的hash值和key是否相等 1）p.hash == hash ：p.hash表示原来存在数据的hash值 hash表示后添加数据的hash值 比较两个hash值是否相等 说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } 而在Node类中具有成员变量hash用来记录着之前数据的hash值的 2）(k = p.key) == key ：p.key获取原来数据的key赋值给k key 表示后添加数据的key 比较 两个key的地址值是否相等 3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等， 那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等 */
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/* 说明：两个元素哈希值相等，并且key的值也相等 将旧的元素整体对象赋值给e，用e来记录 */
e = p;
// hash值不相等或者key不相等；判断p是否为红黑树结点
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 说明是链表节点
else {
/* 1)如果是链表的话需要遍历到最后节点然后插入 2)采用循环遍历的方式，判断链表中是否有重复的key */
for (int binCount = 0; ; ++binCount) {
/* 1)e = p.next 获取p的下一个元素赋值给e 2)(e = p.next) == null 判断p.next是否等于null，等于null， 说明p没有下一个元素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键 将该键值对插入链表中 */
if ((e = p.next) == null) {
/* 1）创建一个新的节点插入到尾部 p.next = newNode(hash, key, value, null); Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } 注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个节点肯定是null 2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素 */
p.next = newNode(hash, key, value, null);
/* 1)节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树 2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历节点的个数。 值是0表示第一个节点，1表示第二个节点。。。。7表示第八个节点，加上数组中的的一个元素，元素个数是9 TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7 如果binCount的值是7(加上数组中的的一个元素，元素个数是9) TREEIFY_THRESHOLD - 1也是7，此时转换红黑树 */
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树
treeifyBin(tab, hash);
// 跳出循环
break;
}
/* 执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等 */
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
/* 要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了 直接执行下面的if语句去替换去 if (e != null) */
break;
/* 说明新添加的元素和当前节点不相等，继续查找下一个节点。 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 */
p = e;
}
}
/* 表示在桶中找到key值、hash值与插入元素相等的结点 也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值 这里完成了put方法的修改功能 */
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
//e.value 表示旧值 value表示新值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
//修改记录次数
++modCount;
// 判断实际大小是否大于threshold阈值，如果超过则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}treeifyBin方法
节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树(treeifyBin方法里面还会判断数组长度是否大于64)，转换红黑树的方法 treeifyBin，整体代码如下：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树 tab表示数组名 hash表示哈希值
treeifyBin(tab, hash);treeifyBin方法如下所示：
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. 替换指定哈希表的索引处桶中的所有链接节点，除非表太小，否则将修改大小。 Node<K,V>[] tab = tab 数组名 int hash = hash表示哈希值 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/* 如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64), 就去扩容。而不是将节点变为红黑树。 目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值 ，链表长度有可能就变短了，数据会放到数组中，这样相对来说效率高一些。 */
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//扩容方法
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
/* 1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化 2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e,e是哈希表中指定位置桶里的链表节点，从第一个开始 */
//hd：红黑树的头结点 tl :红黑树的尾结点
TreeNode<K,V> hd = null, tl = null;
do {
//新创建一个树的节点，内容和当前链表节点e一致
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
//将新创键的p节点赋值给红黑树的头结点
hd = p;
else {
/* p.prev = tl：将上一个节点p赋值给现在的p的前一个节点 tl.next = p;将现在节点p作为树的尾结点的下一个节点 */
p.prev = tl;
tl.next = p;
}
tl = p;
/* e = e.next 将当前节点的下一个节点赋值给e,如果下一个节点不等于null 则回到上面继续取出链表中节点转换为红黑树 */
} while ((e = e.next) != null);
/* 让桶中的第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树 而不是链表数据结构了 */
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}扩容机制
流程
当HashMap中的元素个数超过capacity(数组长度默认16) /* loadFactor(负载因子默认0.75时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16×0.75=12(这个值就是阈值或者边界值threshold值)的时候，就把数组的大小扩展为2×16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。
HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。例如我们从16扩展为32时，具体的变化如下所示：
容量变为原来的二倍后，n-1的二进制数也由1111变为11111。当容量为16时，(n-1)&hash的结果都是0101，即十进制的5；当容量变为32时，hash1的结果是0101，十进制的5，hash2的结果是10101，十进制的21(5+16)。扩容之后所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。
因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。在源码中通过e.hash & oldCap进行判断。oldCap就是扩容之前的容量，在上面的例子中就是16，hash1结果为0，表示还在原位置，hash2结果不为1，表示结果为原位置+旧容量，即5+16=21。
可以看看下图为16扩充为32的resize示意图：
正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。
源码
final Node<K,V>[] resize() {
//得到当前数组
Node<K,V>[] oldTab = table;
//如果当前数组等于null长度返回0，否则返回当前数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//当前阈值点 默认是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
//如果老的数组长度大于0
//开始计算扩容后的大小
if (oldCap > 0) {
// 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
//修改阈值为int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
/* 没超过最大值，就扩充为原来的2倍 1)(newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量 2）oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16 */
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
//老阈值点大于0 直接赋值
else if (oldThr > 0) // 老阈值赋值给新的数组长度
newCap = oldThr;
else { // 直接使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize最大上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//新的阈值 默认原来是12 乘以2之后变为24
threshold = newThr;
//创建新的哈希表
@SuppressWarnings({ "rawtypes","unchecked"})
//newCap是新的数组长度--》32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//判断旧数组是否等于空
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
//遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//原来的数据赋值为null 便于GC回收
oldTab[j] = null;
//判断数组是否有下一个引用
if (e.next == null)
//没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入
newTab[e.hash & (newCap - 1)] = e;
//判断是否是红黑树
else if (e instanceof TreeNode)
//说明是红黑树来处理冲突的，则调用相关方法把树分开
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 采用链表处理冲突
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//通过上述讲解的原理来计算节点的新位置
do {
// 原索引
next = e.next;
//这里来判断如果等于true e这个节点在resize之后不需要移动位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}好，源码就先分析到这里，如果前面看懂了，后面的删除查找对你来说相信也不是问题。
并发问题
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。在多线程环境下，JDK1.7 会产生死循环、数据丢失、数据覆盖的问题，JDK1.8 中会有数据覆盖和多线程同时扩容等问题。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_46215617/article/details/119576554
内容来源于网络，如有侵权，请联系作者删除！
