【Java集合】HashMap系列（二）——底层源码分析

阅读：评论：0

目录

一、HashMap的简介

1.1 HashMap简介和继承结构关系

1.2 HashMap主要的API

二、构造方法

2.1 四个构造方法

2.2 tableSizeFor方法

2.2.1 算法原理

2.2.2 算法演示

2.2.3 总结

2.3 putMapEntries方法

三、put()方法

3.1 put()方法的作用和执行流程

3.2 put()和putVal()源码

3.2.1 实现为空的方法

3.2.2 treeifyBin()方法

3.3 对比JDK1.7的put()方法源码

3.3.1 JDK1.7的put()方法执行流程

3.3.2 JDK1.7的put()方法源码

3.3.3 jdk1.7和jdk1.8的区别

四、resize()方法

4.1 resize()方法执行流程

4.2 resize()方法源码

4.2.1 计算新索引的位置（e.hash & oldCap）

4.3 对比JDK1.7的resize()扩容方法源码

4.3.1 JDK1.7的resize()方法执行流程

4.3.2 JDK1.7的resize()方法源码

4.3.3 initHashSeedAsNeeded()方法源码

4.3.4 jdk1.7和jdk1.8的区别

五、get()方法

5.1 get()方法的执行流程

5.2 get()方法的源码

5.3 对比JDK1.7的get()方法源码

5.3.1 JDK1.7的get()方法执行流程

5.3.2 JDK1.7的get()方法源码

六、remove()方法

6.1 remove()方法的执行流程

6.2 remove()方法源码

6.3 JDK1.7的remove()方法源码

七、HashMap其他操作方法

7.1 containsKey()方法

7.1.1 JDK1.8

7.1.2 JDK1.7

7.2 containsValue()方法

7.2.1 JDK1.8

7.2.2 JDK1.7

一、HashMap的简介

1.1 HashMap简介和继承结构关系

HashMap采用键值对形式的存储结构，每个key对应唯一的value，查询和修改的速度很快，能到到O(1)的平均复杂度。他是非线程安全的，且不能保证元素的存储顺序。以下为HashMap的继承结构关系。

HashMap继承了AbstractMap，而AbstractMap的父类又是Map接口，所以HashMap也间接实现了Map接口，并且实现了Serializable接口，能被序列化，还实现了Cloneable接口可被克隆（浅拷贝）。

在Java8中HashMap采用了数组+链表+红黑树的数据结构。数组的每个元素又被称作桶，Node<key,value>。在添加元素的时候，会根据hash算法计算出不同的key对应的数组下标，但是并不能保证不同的key一定能计算出不同的数组下标进而分配到不同的桶中，不同的key也有可能对应同一个数组下标，这种现象被称为哈希冲突。为了解决哈希冲突带来带来的问题，所以在jdk1.8之前，当根据key计算出的数组下标上，已经有了元素，这个位置已经被占用了，这时候就把该元素放在此数组下标的链表的尾部。

但是一个链表的长度达到一定级别时，查询有时需要遍历整个链表，时间复杂度是O(n)。所以在jdk1.8后，当链表的长度大于等于8并且整个数组的大小大于等于64时，将这个链表转化成红黑树，红黑树的查询效率是O(logn)相比链表有提高了查询速率。

1.2 HashMap主要的API

// 获得指定键的值
V get(Object key); // 添加键值对
V put(K key, V value);  // 将指定Map中的键值对 复制到此Map中
void putAll(Map<? extends K, ? extends V> m);  // 删除该键值对
V remove(Object key);  // 判断是否存在该键的键值对；是 则返回true
boolean containsKey(Object key); // 判断是否存在该值的键值对；是 则返回true
boolean containsValue(Object value);  // 单独抽取key序列，将所有key生成一个Set
Set<K> keySet();// 单独value序列，将所有value生成一个Collection
Collection<V> values(); // 清除哈希表中的所有键值对
void clear();// 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
int size(); // 判断HashMap是否为空；size == 0时 表示为 空
boolean isEmpty();

二、构造方法

2.1 四个构造方法

HashMap 中有四个构造方法，它们分别如下：

/*** 默认构造函数。 默认初始容量是16和负载因子是0.75*/
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
}/*** 包含另一个“Map”的构造函数，包含另一个Map的映射，如果被映射的Map是一个null会抛出空指针异常。负载因子是默认的* 直接传入存储了要添加进HashMap的key-value对的map，来构造HashMap*/
public HashMap(Map<? extends K, ? extends V> m) {//将默认的负载因子赋值给成员变量loadFactorthis.loadFactor = DEFAULT_LOAD_FACTOR;//调用PutMapEntries()来完成HashMap的初始化赋值过程putMapEntries(m, false);//下面会分析到这个方法
}/*** 指定“容量大小”的构造函数，直接使用默认负载因子0.75*/
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/**
* 构造一个空的HashMap并指定初始容量和负载因子。
* 要注意HashMap源码里面并没有专门的一个属性来存储数组的容量，而是通过threshold来简介限制数组容量的
* 通过将自定义初始化数组容量传入tableSizeFor()方法，计算得出initialCapacity容量大小应该对应的阈值threshold大小
* 这样当数组内元素数大于threshold，就会触发扩容操作，间接限定了数组容量大小
**/
public HashMap(int initialCapacity, float loadFactor) {//如果初始容量小于0，抛出非法参数异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);//如果初始容量大于最大的容量也就是2^30,那么就按照最大的初始容量赋值。if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//如果负载因子小于0或者是NaN（float NaN = 0.0f / 0.0f;）也会抛出非法参数异常if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " + loadFactor);// 设置重载因子this.loadFactor = loadFactor;// 调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold// 注意，这里赋给threshold并不是扩容阈值，只是临时赋值。//此时HashMap还没有创建数组，当插入数据的时候会判断该HashMap是否已经初始化，那个时候就会执行resize()方法进行一次扩容,就会重新计算一正确的扩容阈值赋值给thresholdthis.threshold = tableSizeFor(initialCapacity);
}

此处仅用于接收初始容量大小（capacity）、加载因子(Load factor)，但仍无真正初始化哈希表（即初始化存储数组table），仅仅是声明了HashMap对象。
此处先给出结论：真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put（）时。下面会详细说明

2.2 tableSizeFor方法

/*** 计算出大于等于参数的第一个2的幂次方* 例如：1返回1，3返回4，8返回8，9返回16，125返回128，* 如果参数大于默认最大值，则容量取默认最大值。*/
static final int tableSizeFor(int cap) {int n = cap - 1;      //容量减1，为了防止初始化容量已经是2的幂的情况，最后有+1运算。如果cap已经是2的幂， 又没有执行这个减1操作，则执// 行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。n |= n >>> 1;         //将n无符号右移一位再与n做或操作n |= n >>> 2;         //将n无符号右移两位再与n做或操作n |= n >>> 4;         //将n无符号右移四位再与n做或操作n |= n >>> 8;         //将n无符号右移八位再与n做或操作n |= n >>> 16;        //将n无符号右移十六位再与n做或操作//如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负 //数,所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

其中：

a |= b 即为 a = a|b

>>> 是无符号右移运算符无论正负，右移后，高位填充0

2.2.1 算法原理

要理解这个方法的核心，关键在于中间五步移位加上或运算。

这个算法的原理：2的整数幂用二进制表示都是最高有效位为1，其余全是0，比如十进制8和32，下图只用了一个字节示意。

对任意十进制数转换为2的整数幂，结果是这个数本身的最高有效位的前一位变成1，最高有效位以及其后的位都变为0。

通过上面理论基础，我们可以得出该算法的核心思想是，先将最高有效位以及其后的位都变为1，最后再+1，就进位到前一位变成1，其后所有的满2变0。所以关键是如何将最高有效位后面都变为1。

2.2.2 算法演示

下面用图来进行演示。这里将十进制的25转换为32。

作者的做法是先移位，再或运算。

右移一位，再或运算，就有两位变为1；

右移两位，再或运算，就有四位变为1…

最后右移16位再或运算，保证32位的int类型整数最高有效位之后的位都能变为1.

全过程示意图

初始容量-1

之所以在开始移位前先将容量-1，是为了避免给定容量已经是8,16这样2的幂时，不减一直接移位会导致得到的结果比预期大。比如预期16得到应该是16，直接移位的话会得到32。在上图中就是所有x本身已经是0的情况下，不减1得到的结果变大了。

初始值

选取任意int类型数字，下图x表示不确定0或者1.

我们目的是将所有的x变为1，如下图

最后+1，就能进位得到2的整数幂。

我们要做的就是不断通过右移+或运算来达到目的。

右移一位+或运算

可以看出，右移一位再或运算，有两位变成了1。

右移二位+或运算

右移两位再或运算，有四位变成了1。

右移四位+或运算

右移四位再或运算，有八位变成了1。

右移八位+或运算

右移八位再或运算，有十六位变成了1。

右移十六位+或运算

右移十六位再或运算，注意这里不是三十二位全变，而是最高位后面的全变1。

结果+1

可以看出，不管x是多少，我们都能将其转换为1。而且分别经过1,2,4,8,16次转换，不管这个int类型值多大，我们都会将其转换，只是值较小时，可能多做几次无意义操作。

2.2.3 总结

这个方法之所以高效，是因为移位运算和或运算都属于比较底层的操作，代码的数量不会比最终的指令数多，也就是通过几个简单操作实现了我们的目的。但其实第一次看HashMap这个构造方法的时候，有一些不理解，就是为什么传入的指定初始容量initialCapacity，通过计算得到了大于等于initialCapacity的第一个2的幂次方，这个值就应该是HashMap容量capacity。然而却把这个capacity赋值给了threshold。

this.threshold = tableSizeFor(initialCapacity);

开始就觉得这里写很奇怪，觉得应该是这样写：

this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

觉得这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。

但是后来才意识到在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。这个源码在后面会详细讲解。

2.3 putMapEntries方法

下面我们再来看看在传入Map参数的构造方法中调用的putMapEntries()方法。这个方法调用了HashMap的resize()扩容方法和putVal()存入数据方法。

putMapEntries函数会被HashMap的拷贝构造函数public HashMap(Map<? extends K, ? extends V> m)或者Map接口的putAll函数（被HashMap给实现了）调用到。该函数使用的是默认修饰符（default），也就是只有包访问权限，只能被本类或者该包下的类访问到，所以一般情况下用户无法调用。

/*** 该方法的作用：将传入的子Map中的全部元素逐个添加到HashMap中* @param evict 最初构造此Map时为false，否则为true（中继到afterNodeInsertion方法）。*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//获得参数Map的大小，并赋值给sint s = m.size();// 判断大小是否大于0  只有大于零Map中才有元素来插入HashMapif (s > 0) {// 判断table是否已经初始化  如果table=null一般就是构造函数来调用的putMapEntries，或者构造后还没放过任何元素if (table == null) { // pre-size// 如果未初始化，则计算HashMap的最小需要的容量（即容量刚好不大于扩容阈值）。这里Map的大小s就被当作HashMap的扩容阈值，然后用传入Map的大小除以负载因子就能得到对应的HashMap的容量大小（当前m的大小 / 负载因子 = HashMap容量）// 先不考虑容量必须为2的幂，那么下面括号里会算出来一个容量，使得size刚好不大于阈值。但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1。此时ft可以临时看作HashMap容量大小float ft = ((float)s / loadFactor) + 1.0F;//比较最大容量与ft，取小值； 到这里t暂时表示HashMap的容量大小。如果是将ft浮点型赋值给t整形，因为前面加了1.0f,这里也就实现了向上取整int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 只有在算出来的容量t > 当前暂存的容量(容量可能会暂放到阈值上的,刚使用构造函数构造出来的HashMap并且没有存入元素时，容量大小就会被暂时存在threshold中)时// 才会用t计算出新容量，暂时存放到阈值上,在后面触发resize()扩容的时候会对threshold重新计算正确的阈值if (t > threshold)threshold = tableSizeFor(t);}//如果当前Map已经初始化,且这个map中的元素个数大于扩容的阀值就得扩容//这种情况属于预先扩大容量，再put元素else if (s > threshold)resize();//遍历map,将map中的key和value都添加到HashMap中for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();// 调用HashMap的put方法的具体实现方法putVal来对数据进行存放。该方法的具体细节在后面会进行讲解// putVal可能也会触发resizeputVal(hash(key), key, value, false, evict);}}
}

注释里已经解释得很清楚了，这里再提几点重要的：

if (table == null)分支，说明是HashMap的拷贝构造函数来调用的putMapEntries，或者是构造以后还没有放过任何元素，然后再调用putAll。
float ft = ((float)s / loadFactor) + 1.0F这里的加1是因为，size / loadFactor = capacity，但如果算出来的capacity是小数，却又向下取整，会造成容量不够大，所以，如果是小数的capacity，那么必须向上取整。
算出来的容量必须小于最大容量MAXIMUM_CAPACITY，否则直接让capacity等于MAXIMUM_CAPACITY。
if (t > threshold)这里的threshold成员实际存放的值是capacity的值。因为在table还没有初始化时（table还是null），用户给定的capacity会暂存到threshold成员上去（毕竟HashMap没有一个成员叫做capacity，capacity是作为table数组的大小而隐式存在的）。
else if (s > threshold)说明传入map的size都已经大于当前map的threshold了，即当前map肯定是装不下两个map的并集的，所以这里必须要执行resize操作。
最后循环里的putVal可能也会触发resize操作。

三、put()方法

3.1 put()方法的作用和执行流程

HashMap 只提供了 put 用于添加元素，putval也是使用的默认修饰符，因此只能被本类或者该包下的类访问到，所以putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。

对 putVal 方法添加元素的分析如下：

如果定位到的数组位置没有元素，就直接插入。
如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

3.2 put()和putVal()源码

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}/*** Implements Map.put and related methods.* 实现了map的put和相关方法* @param hash  key的hash值（key的hash高16位+高16位与低16位的异或运算）* @param key 键* @param value 值  * @param onlyIfAbsent onlyIfAbsent为true的时候不要修改已经存在的值，如果onlyIfAbsent为false，当插入的元素已经在HashMap中已经拥有了与其key值和hash值相同的元素，仍然需要把新插入的value值覆盖到旧value上。如果nlyIfAbsent为true，则不需要修改* @param evict evict如果为false表示构造函数调用* @return 返回旧的value值（在数组桶或链表或红黑树中找到存在与插入元素key值和hash值相等的元素，就返回这个旧元素的value值），如果没有发现相同key和hash的元素则返回null*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab用来临时存放数组table引用   p用来临时存放数组table桶中的bin// n存放HashMap容量大小   i存放当前put进HashMap的元素在数组中的位置下标Node<K,V>[] tab; Node<K,V> p; int n, i;// table未初始化或者长度为0，进行扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已经存在元素else {// e记录当前节点  k记录key值Node<K,V> e; K k;// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 将第一个元素赋值给e，用e来记录。直接将插入的新元素覆盖旧元素e = p;// hash值不相等，即key不相等并且该节点为红黑树结点，将元素插入红黑树else if (p instanceof TreeNode)// 放入树中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 为链表结点else {// 在链表最末插入结点（尾插法）for (int binCount = 0; ; ++binCount) {// 到达链表的尾部if ((e = p.next) == null) {// 在尾部插入新结点p.next = newNode(hash, key, value, null);// 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法// 这个treeifyBin()方法会根据 HashMap 数组情况来决定是否转换为红黑树。// 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少执行效率。否则，就是只是对数组扩容。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 树化操作treeifyBin(tab, hash);// 跳出循环  此时e=null，表示没有在链表中找到与插入元素key和hash值相同的节点break;}// 判断链表中结点的key值和Hash值与插入的元素的key值和Hash值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 若相等，则不用将其插入了，直接跳出循环break;// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表p = e;}}// 当e!=null时，表示在数组桶或链表或红黑树中存在key值、hash值与插入元素相等的结点。此时就直接用原有的节点就可以了，不用插入新的元素了。此时e就代表原本就存在于HashMap中的元素if (e != null) {// 记录e的value，也就是旧value值V oldValue = e.value;// onlyIfAbsent为false或者旧值为null，则需要用新的value值对旧value值进行覆盖if (!onlyIfAbsent || oldValue == null)//用新值替换旧值e.value = value;// 替换旧值时会调用的方法（默认实现为空）afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改，记录HashMap被修改的次数，主要用于多线程并发时候++modCount;// 实际大小大于阈值则扩容    ++size只有在插入新元素才会执行，如果发现HashMap中已经存在了相同key和hash的元素，就不会插入新的元素，在上面就已经执行return了，也就不会改变size大小if (++size > threshold)resize();// 插入成功时会调用的方法（默认实现为空）afterNodeInsertion(evict);// 没有找到原有相同key和hash的元素，则直接返回Nullreturn null;
}

3.2.1 实现为空的方法

这里顺带说一下下面三个方法

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

在putVal()方法中替换旧值和插入成功的时候都调用了上面其中的两个方法，这三个方法是HashMap类中的方法，但是我们查看源码后会发现这三个方法都是空的方法。其实这三个方法是为继承HashMap的LinkedHashMap类服务的。

LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。

比如LinkedHashMap中被覆盖的afterNodeInsertion方法，用来回调移除最早放入Map的对象。这三个方法会在以后的LinkedHashMap章节里面讲到。

3.2.2 treeifyBin()方法

将所有的节点转换成树形节点，并且将链接的链表线索化，即为每个二叉树的节点添加前驱和后继节点，形成线索，构造出双链表结构。再调用treeify()方法构造红黑树结构关系。

/*** 将数组指定位置的索引里的链表转为红黑树。通过两步完成：* 1、为每个节点添加前驱和后继节点，形成双向链表结构，并且将每个节点都转换成红黑树节点TreeNode* 2、调用treeify()方法构造红黑树结构关系* * @param tab：数组* @param hash：要将这个hash值所在的索引上的链表转换为红黑树*/
final void treeifyBin(Node<K,V>[] tab, int hash) {// n：当前数组长度，index：hash经过计算得到的索引，e：index索引位置的元素int n, index; Node<K,V> e;// 当前数组为空或者当前数组长度小于数组转为红黑树的阈值64时，需要扩容if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();// 计算得到索引index，并且取出来index索引对应的节点e，并且 e 不是null，else if ((e = tab[index = (n - 1) & hash]) != null) { // hd 存头节点，e表示当前遍历到的链表节点，p表示当前遍历到的已经转换成树节点的节点,tl表示当前遍历到的已经转换成树节点的上一个节点TreeNode<K,V> hd = null, tl = null;// 从e节点开始遍历链表do {// 将链表节点e转红黑树节点pTreeNode<K,V> p = replacementTreeNode(e, null);// 如果是第一次遍历，将头节点赋值给hdif (tl == null)hd = p;// 如果不是第一次遍历，则处理当前节点的prev属性和上一个节点的next属性else {// 当前节点的prev属性设为上一个节点p.prev = tl; // 上一个节点的next属性设置为当前节点   tl.next = p;    }// 将p节点赋值给tltl = p;} while ((e = e.next) != null); //后移，找下一个节点，再继续遍历// 将table该索引位置赋值为hd头节点，如果该节点不为空，则以头节点(hd)为根节点, 构建红黑树if ((tab[index] = hd) != null)// treeify()是内部类TreeNode的方法，这个在TreeNode那篇文章里有详细的讲解hd.treeify(tab);}
}// For treeifyBin 将指定的链表节点转为树节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);
}

3.3 对比JDK1.7的put()方法源码

3.3.1 JDK1.7的put()方法执行流程

对于JDK1.7的 put 方法的分析如下：

如果定位到的数组位置没有元素就直接插入。
如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和链表上的 key 比较，如果存在key 相同的节点就直接覆盖，没有相同的节点就采用头插法将元素插入链表。与JDK1.8链表插入元素的不同点就在于1.8是尾插法，1.7是头插法

流程图：

3.3.2 JDK1.7的put()方法源码

首先贴一下JDK1.7中HashMap成员属性与1.8相比不同的两个，在put()源码中会出现

//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态  
static final Entry<?,?>[] EMPTY_TABLE = {};  
//空的存储实体  table是真正存储元素的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

put()方法源码：

/*** 将“key-value”添加到HashMap中 * @return 如果插入的key在HashMap中已存在，将新插入的value替换旧value，并且返回旧value*         如何插入的key在HashMap中不存在，则返回Null*/
public V put(K key, V value) {// 1. 若 哈希表未初始化（即 table为空) // 则使用构造函数进行初始化 数组table  if (table == EMPTY_TABLE) {// 分配数组空间// 入参为threshold，此时threshold为initialCapacity initialCapacity可以是构造方法中传入的大小，如果构造方法没有指定HashMap容量大小，则使用默认值1<<4(=16)inflateTable(threshold);}// 2. 判断key是否为空值null// 2.1 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0]// （本质：key = Null时，hash值 = 0，故存放到table[0]中）// 该位置永远只有1个value，新传进来的value会覆盖旧的valueif (key == null)return putForNullKey(value);// 2.2 若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）// a. 根据键值key计算hash值int hash = hash(key);    // b. 根据hash值 最终获得 key对应存放的数组Table中位置int i = indexFor(hash, table.length);// 3. 判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）for (Entry<K,V> e = table[i]; e != null; e = e.next) {// 3.1 若该key已存在（即 key-value已存在 ），则用新value替换旧value，并返回旧valueObject k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;// 调用value的回调函数，该函数为空实现e.recordAccess(this);return oldValue;}}// 结构性修改，记录HashMap被修改的次数。保证并发访问时，若HashMap内部结构发生变化，快速响应失败modCount++;// 3.2 若 该key不存在，则将“key-value”添加到table中addEntry(hash, key, value, i);return null;
}

1. 初始化哈希表

真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put（）时，而不是在构造函数中。

inflateTable()方法用于初始化HashMap，即初始化数组（table）、扩容阈值（threshold）。

inflateTable的源码如下：

/*** 初始化hash表* @param toSize 指定HashMap容量大小*/
private void inflateTable(int toSize) {// 1. capacity必须是2的次幂，将传入的容量大小toSize转化为：大于传入容量大小toSize的最小的2的次幂// 即如果传入的是容量大小是19，那么转化后，初始化容量大小为32（即2的5次幂）int capacity = roundUpToPowerOf2(toSize);// 2. 重新计算阈值 threshold = 容量 * 加载因子  // 取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);// 3. 使用计算后的初始容量（已经是2的次幂） 为table分配空间，即初始化数组table（作为数组长度）// 即 哈希表的容量大小 = 数组大小（长度）table = new Entry[capacity];// 选择合适的Hash因子（即Hash种子），好的Hash种子能提高计算Hash时结果的散列性initHashSeedAsNeeded(capacity);
}

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17,capacity=32。其实现如下：

/*** 找到大于传入容量大小的最小的2的次幂*/
private static int roundUpToPowerOf2(int number) {  
//若 容量超过了最大值，初始化容量设置为最大值 ；否则，设置为：大于传入容量大小的最小的2的次幂
return number >= MAXIMUM_CAPACITY  ? MAXIMUM_CAPACITY  : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值。

2.当 key ==null时，将该 key-value 的存储位置规定为数组table 中的第1个位置，即table [0]

 /*** 将key为null的value值放入table[0]上*/
private V putForNullKey(V value) {  // 遍历以table[0]为首的链表，寻找是否存在key==null 对应的键值对// 1. 若有：则用新value 替换 旧value；同时返回旧的value值for (Entry<K,V> e = table[0]; e != null; e = e.next) {  if (e.key == null) {   V oldValue = e.value;  e.value = value;  e.recordAccess(this);  return oldValue;  }  } 
}

从此处可以看出：

HashMap的键key 可为null（区别于 HashTable的key 不可为null）
HashMap的键key 可为null且只能为1个，但值value可为null且为多个

3.当key≠null的时候，计算key的Hash并根据Hash值计算对应在table中的下标

hash()方法：

/*** 源码分析1：hash(key)* 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）* JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算* JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算*/
// JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
static final int hash(int h) {h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

通过hash函数得到散列值后，再通过indexFor进一步处理来获取实际的存储位置，其实现如下：

/*** 函数源码分析2：indexFor(hash, table.length)* JDK 1.8中实际上无该函数，但原理相同，即具备类似作用的函数*/
static int indexFor(int h, int length) {  // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）return h & (length-1); 
}

4.当key≠null时，得到存储的下标位置后，我们就可以将元素放入HashMap中

先判断链表中是否已经存在与要插入元素的key相同的元素，如果有，直接用要插入的新value覆盖旧value。如果没有，则调用addEntry()方法将元素插入：

/*** 添加链表元素   * 作用：添加键值对（Entry ）到 HashMap中* @param bucketIndex 元素要插入到数组table的索引位置（下标）*/
void addEntry(int hash, K key, V value, int bucketIndex) {  // 1. 插入前，先判断容量是否足够// 1.1 若不足够，则进行扩容（2倍）、重新计算Hash值、重新计算存储数组下标if ((size >= threshold) && (null != table[bucketIndex])) {  resize(2 * table.length); // a. 扩容2倍hash = (null != key) ? hash(key) : 0;  // b. 重新计算该Key对应的hash值bucketIndex = indexFor(hash, table.length);  // c. 重新计算该Key对应的hash值的存储数组下标位置}  // 1.2 若容量足够，则创建1个新的数组元素（Entry） 并放入到数组中createEntry(hash, key, value, bucketIndex);  
}  /*** 创建元素，并将新元素添加到HashMap中 * 作用： 若容量足够，则创建1个新的数组元素（Entry） 并放入到数组中*/  
void createEntry(int hash, K key, V value, int bucketIndex) { // 1. 把table中该位置原来的Entry保存  Entry<K,V> e = table[bucketIndex];// 2. 使用头插法讲元素插入到链表中，新元素成为链表头节点，新元素的next节点为原链表头节点。这保证了新插入的元素总是在链表的头  table[bucketIndex] = new Entry<>(hash, key, value, e);  // 3. 哈希表的键值对数量计数增加size++;  
}

通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。扩容会在后面的章节讲解。

3.3.3 jdk1.7和jdk1.8的区别

四、resize()方法

下面看一下 resize 方法，面试时最经常问的hashmap扩容机制就在这个地方，注意newCap = oldCap << 1这句，扩容就在这，扩大两倍。

进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

4.1 resize()方法执行流程

4.2 resize()方法源码

/*** Initializes or doubles table size.  If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.* 初始化或把table容量翻倍。如果table是空，则根据threshold属性的值去初始化HashMap的容                * 量。如果不为空，则进行扩容，因为我们使用2的次幂来给HashMap进行扩容，所以每个桶里的元素 * 必须保持在原来的位置或在新的table中以2的次幂作为偏移量进行移动* @return 返回Node<K, V>数组*/
final Node<K,V>[] resize() {// 创建一个临时变量，用来存储当前的tableNode<K,V>[] oldTab = table;// 获取原来的table的长度（大小），判断当前的table是否为空，如果为空，则把0赋值给新定义的oldCap,否则以table的长度作为oldCap的大小int oldCap = (oldTab == null) ? 0 : oldTab.length;// 创建临时变量用来存储旧的阈值，把旧table的阈值赋值给oldThr变量int oldThr = threshold;// 定义变量newCap和newThr来存放新的table的容量和阈值，默认都是0int newCap, newThr = 0;    // 判断旧容量是否大于0            if (oldCap > 0) {                            // 判断旧容量是否大于等于 允许的最大值，2^30if (oldCap >= MAXIMUM_CAPACITY) {    // 以int的最大值作为原来HashMap的阈值，这样永远达不到阈值就不会扩容了threshold = Integer.MAX_VALUE; // 因为旧容量已经达到了最大的HashMap容量，不可以再扩容了，将阈值变成最大值之后，将原table返回       return oldTab;}// 如果原table容量不超过HashMap的最大容量，将原容量*2 赋值给变量newCap，如果newCap不大于HashMap的最大容量，并且原容量大于HashMap的默认容量else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 将newThr的值设置为原HashMap的阈值*2newThr = oldThr << 1; // double threshold}// 如果原容量不大于0，即原table为null,则判断旧阈值是否大于0 else if (oldThr > 0) // 如果原table为Null且原阈值大于0，说明当前是使用了构造方法指定了容量大小，只是声明了HashMap但是还没有真正的初始化HashMap（创建table数组），只有在向里面插入数据才会触发扩容操作进而进行初始化// 将原阈值作为容量赋值给newCap当做newCap的值。由之前的源码分析可知，此时原阈值存储的大小就是调用构造函数时指定的容量大小，所以直接将原阈值赋值给新容量newCap = oldThr;// 如果原容量不大于0，并且原阈值也不大于0。这种情况说明调用的是无参构造方法，还没有真正初始化HashMap，只有put()数据的时候才会触发扩容操作进而进行初始化else {               // zero initial threshold signifies using defaults// 则以默认容量作为newCap的值newCap = DEFAULT_INITIAL_CAPACITY;// 以初始容量*默认负载因子的结果作为newThr值newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 经过上面的处理过程，如果newThr值为0，说明上面是进入到了原容量不大于0，旧阈值大于0的判断分支。需要单独给newThr进行赋值if (newThr == 0) {// 临时阈值 = 新容量 * 负载因子float ft = (float)newCap * loadFactor;// 设置新的阈值 保证新容量小于最大总量   阈值要小于最大容量，否则阈值就设置为int最大值newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 将新的阈值newThr赋值给threshold，为新初始化的HashMap来使用threshold = newThr;// 初始化一个新的容量大小为newCap的Node数组@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 将新创建的数组赋值给table，完成扩容后的新数组创建table = newTab;// 如果旧table不为null，说明旧HashMap中有值if (oldTab != null) {// 如果原来的HashMap中有值，则遍历oldTab，取出每一个键值对，存入到新table        for (int j = 0; j < oldCap; ++j) {// 创建一个临时变量e用来指向oldTab中的第j个键值对，Node<K,V> e;// 将oldTab[j]赋值给e并且判断原来table数组中第j个位置是否不为空if ((e = oldTab[j]) != null) {    // 如果不为空，则将oldTab[j]置为null，释放内存，方便gcoldTab[j] = null;   // 如果e.next = null，说明该位置的数组桶上没有连着额外的数组          if (e.next == null)// 此时以e.hash&(newCap-1)的结果作为e在newTab中的位置，将e直接放置在新数组的新位置即可          newTab[e.hash & (newCap - 1)] = e; // 否则说明e的后面连接着链表或者红黑树，判断e的类型是TreeNode还是Node,即链表和红黑树判断else if (e instanceof TreeNode)  // 如果是红黑树，则进行红黑树的处理。将Node类型的e强制转为TreeNode，之所以能转换是因为TreeNode 是Node的子类// 拆分树，具体源码解析会在后面的TreeNode章节中讲解((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 当前节不是红黑树，不是null，并且还有下一个元素。那么此时为链表   else { // preserve order /*这里定义了五个Node变量，其中lo和hi是，lower和higher的缩写，也就是高位和低位,因为我们知道HashMap扩容时，容量会扩到原容量的2倍，也就是放在链表中的Node的位置可能保持不变或位置变成 原位置+oldCap,在原位置基础上又加了一个数，位置变高了，这里的高低位就是这个意思，低位指向的是保持原位置不变的节点，高位指向的是需要更新位置的节点*/// Head指向的是链表的头节点，Tail指向的是链表的尾节点Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;// 指向当前遍历到的节点的下一个节点Node<K,V> next;// 循环遍历链表中的Nodedo {                   next = e.next;/*如果e.hash & oldCap == 0，注意这里是oldCap，而不是oldCap-1。我们知道oldCap是2的次幂，也就是1、2、4、8、16...转化为二进制之后，都是最高位为1，其它位为0。所以oldCap & e.hash 也是只有e.hash值在oldCap二进制不为0的位对应的位也不为0时，才会得到一个不为0的结果。举个例子，我们知道10010 和00010 与1111的&运算结果都是 0010  ，但是110010和010010与10000的运算结果是不一样的，所以HashMap就是利用这一点，来判断当前在链表中的数据，在扩容时位置是保持不变还是位置移动oldCap。*/// 如果结果为0，即位置保持不变  if ((e.hash & oldCap) == 0) {  // 如果是第一次遍历    if (loTail == null)      // 让loHead = e，设置头节点     loHead = e;               else// 否则,让loTail的next =  = e;   // 最后让loTail = e       loTail = e;                   }/*其实if 和else 中做的事情是一样的，本质上就是将不需要更新位置的节点加入到loHead为头节点的低位链表中，将需要更新位置的节点加入到hiHead为头结点的高位链表中。我们看到有loHead和loTail两个Node,loHead为头节点，然后loTail是尾节点，在遍历的时候用来维护loHead，即每次循环，更新loHead的next。我们来举个例子，比如原来的链表是A->B->C->D->E。我们这里把->假设成next关系，这五个Node中，只有C的hash & oldCap != 0 ,然后这个代码执行过程就是:第一次循环： 先拿到A，把A赋给loHead,然后loTail也是A第二次循环： 此时e的为B，而且loTail != null,也就是进入上面的else分支，把 =                     B，此时loTail中即A->B,同样反应在loHead中也是A->B,然后把loTail = B第三次循环： 此时e = C，由于C不满足 (e.hash & oldCap) == 0,进入到了我们下面的else分支，其 实做的事情和当前分支的意思一样，只不过维护的是hiHead和hiTail。第四次循环： 此时e的为D，loTail != null,进入上面的else分支，把 =                     D，此时loTail中即B->D,同样反应在loHead中也是A->B->D,然后把loTail = D*/else {if (hiTail == null)hiHead =  = e;hiTail = e;}} while ((e = next) != null);// 遍历结束，即把table[j]中所有的Node处理完// 如果loTail不为空，也保证了loHead不为空if (loTail != null) {    // 此时把loTail的next置空，将低位链表构造完成     = null;    // 把loHead放在newTab数组的第j个位置上，也就是这些节点保持在数组中的原位置不变newTab[j] = loHead;      }// 同理，只不过hiHead中节点放的位置是j+oldCapif (hiTail != null) {        = null;// hiHead链表中的节点都是需要更新位置的节点newTab[j + oldCap] = hiHead;}}}}}// 最后返回newTabreturn newTab;            
}

resize()方法中有几个点需要注意：

一个是计算新索引的位置（e.hash & oldCap），
另一个是红黑树的处理（split）。

下面就就来说一下第一个问题，红黑树处理留到TreeNode的文章讲解。

4.2.1 计算新索引的位置（e.hash & oldCap）

关于e.hash & oldCap == 0 的讲解在之前的HashMap底层原理概要笔记和上面的代码注释中已经说过了，这里再结合图详细说一下。

为什么是e.hash & oldCap 来确定在新数组中的索引位置呢，因为在put 的时候 (n - 1) & hash 得到索引位置

举个例子，扩容前 table 的容量n为16，a 节点和 b 节点在扩容前处于同一索引位置。

扩容后，table 长度n为32，新表的 n - 1 只比老表的 n - 1 在高位多了一个1（图中标红的1）。

因为 2 个节点在老表是同一个索引位置，因此计算新表的索引位置时，只取决于新表在高位多出来的这一位（图中标红1），而这一位的值刚好等于 oldCap。

因此会存在两种情况：

(e.hash & oldCap) == 0 ，则新表索引位置为“原索引位置” ；
(e.hash & oldCap) != 0，则新表索引位置为”原索引 + oldCap 位置”。

4.3 对比JDK1.7的resize()扩容方法源码

JDK1.7中一般是在进行put()数据的时候调用resize()方法进行扩容，由addEntry()方法进行调用。

4.3.1 JDK1.7的resize()方法执行流程

流程图：

扩容过程中的转移数据示意图如下：

在扩容resize（）过程中，在将旧数组上的数据转移到新数组上时，转移操作 = 按旧链表的正序遍历链表，在新链表的使用头插法依次插入，即在转移数据、扩容后，容易出现链表逆序的情况。

此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，容易出现环形链表，从而在获取数据、遍历链表时形成死循环（Infinite Loop），即死锁的状态，所以HashMap线程不安全。

4.3.2 JDK1.7的resize()方法源码

/**
* 分析：resize(2 * table.length)
* 作用：当容量不足时（容量 > 阈值），则扩容（扩到2倍）
*/   
void resize(int newCapacity) {  // 1. 保存旧数组（old table）Entry[] oldTable = table; // 2. 保存旧容量（old capacity ），即数组长度int oldCapacity = oldTable.length;// 3. 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出    if (oldCapacity == MAXIMUM_CAPACITY) {// 修改扩容阀值  threshold = Integer.MAX_VALUE;return;  }  // 4. 根据新容量（2倍容量）新建1个数组，即新table  Entry[] newTable = new Entry[newCapacity];  // 5. 将旧数组上的数据（键值对）转移到新table中，从而完成扩容。initHashSeedAsNeeded(newCapacity)这个方法用来根据新的数组长度来重新初始化Hash种子transfer(newTable, initHashSeedAsNeeded(newCapacity));// 6. 新数组table引用到HashMap的table属性上table = newTable;  // 7. 重新设置阈值,如果阈值超过了HashMap最大容量大小，则直接将阈值设置为 MAXIMUM_CAPACITY + 1threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法：

/**
* 分析：transfer(newTable); 
* 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
* 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
* @param rehash 如果这里传入的是true，说明Hash种子已经更新，需要对所有的元素进行rehash重新计算Hash值。该操作比较消耗资源，这也是JDK1.7相对JDK1.8执行效率较低的原因
*/ 
void transfer(Entry[] newTable, boolean rehash) {  // 获取新数组的大小 = 获取新容量大小   int newCapacity = newTable.length// 通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中for (Entry<K,V> e : table) {// 遍历桶中所有元素while(null != e) {  Entry<K,V> next = e.next;  // 如果是重新Hash，则需要重新计算hash值  if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);  }  // 重新计算每个元素的存储位置，这里再次按照之前计算元素所在位置的方法重新进行一遍 Hash值 &（新数组长度 - 1）的计算，也是相当消耗资源的操作。1.8就采用扩容之后运用运算规律来对元素重新定位，这样相对要高效很多。int i = indexFor(e.hash, newCapacity);// 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将新插入数据的next指向原数组位置的链表头节点，然后将需放入的数据放到数组位置中，这样就实现了头插法将数据插入链表// 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入e.next = newTable[i];// newTable[i]的值总是最新插入的值newTable[i] = e;// 访问下一个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点e = next;}  }  
}

4.3.3 initHashSeedAsNeeded()方法源码

这个方法在JDK1.7中inflateTable()初始化哈希表方法和resize()扩容方法中都有出现。这个方法作用是初始化Hash种子。在JDK1.7中计算hash值的方法需要使用Hash种子来参与运算，进而提高计算出来的hash值的散列性，最大限度减少哈希冲突。下面就来简单讲一下这个方法。

/*** 这个方法用来根据新的数组长度来重新初始化Hash种子，好的Hash种子能提高计算Hash时结果的散列性，最大限度减少哈希冲突。* @param capacity 根据传入的容量大小来进行重新初始化Hash种子* @return 返回true说明已经根据传入的容量大小重新初始化了Hash种子，此时以前根据旧的Hash种子计算出来的Hash值就需要进行rehash了。*         返回false说明并没有根据传入的容量大小进行重新初始化Hash种子*/
final boolean initHashSeedAsNeeded(int capacity) {// 首先会判断hashSeed是否不等于0，因为hashSeed一开始是0，所以此处是falseboolean currentAltHashing = hashSeed != 0;// 这行代码是判断vm是否启动 且 容量到达一个值ALTERNATIVE_HASHING_THRESHOLD，这个值是可以自己去设定，不设定的话是默认的Integer.MaxValue 。 假设我们初始化容量capacity = 16，设置ALTERNATIVE_HASHING_THRESHOLD值为 3，那么这行代码会为trueboolean useAltHashing = sun.misc.VM.isBooted() &&(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//亦或 ^ 的意思是 不相同则返回true，此时switching=true，那么hashSeed就会重新去计算hash种子，以便计算hash时增加散列性，boolean switching = currentAltHashing ^ useAltHashing;if (switching) {// 重新设置了Hash种子hashSeed = useAltHashing? sun.misc.Hashing.randomHashSeed(this): 0;}return switching;
}final int hash(Object k) {// 设置了哈希种子int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}// Hash种子参与到了key的Hash值计算当中h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

4.3.4 jdk1.7和jdk1.8的区别

五、get()方法

5.1 get()方法的执行流程

查找主要分为三个步骤：

根据hash算法定位数组的索引位置，找到key及其第一个元素。
通过equals方法判断第一个节点是否是我们需要的key,是的话直接返回，不是的话，往后遍历
判断当前节点的next是不是null，如果不是的话，再判断属于哪个类型，如果是红黑树就采用遍历红黑树的方法查找节点，否则就以遍历链表的方式查找。

流程图：

5.2 get()方法的源码

根据指定的key，查找对应的value值，找不到返回null，后续操作get()方法返回的结果时一定要判断非null，否则会出现空指针异常。

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

根据key的hash和key，查找节点。找不到返回null

/***  and related methods** @param hash hash for key* @param key the key* @return the node, or null if none*/
final Node<K,V> getNode(int hash, Object key) {// tab：当前map的数组，first：当前hash对应的索引位置上的节点，e：遍历过程中临时存储的节点，// n：tab数组的长度，k：first节点的key/遍历链表时遍历到的节点e的key值Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 1.对table进行校验：table不为空 && table长度大于0 && // hash对应的索引位置上的节点不为空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 判断第一个节点是不是要找的元素，比较hash值和key是否和入参的一样，如果一样，直接返回第一个节点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k)))){return first;}// 第一个节点不是要找的元素，// 取出来第二个节点，并且第二个节点不为null，说明还没走到该节点链的最后if ((e = ) != null) {// 如果第一个节点是红黑树类型if (first instanceof TreeNode){// 调用红黑树的查找目标节点方法getTreeNodereturn ((TreeNode<K,V>)first).getTreeNode(hash, key);}// 前提条件：第一个节点不为null，并且也不是红黑树，而且还有下一个节点，那么该索引位置的元素类型就是链表，从第二个节点开始遍历该链表，do {// hash值和key值与入参一致，说明找到要查询的节点，返回节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);// e指针后移，并且下一个节点不为null则继续遍历，不为null表示没到链表最后}}// 没找到返回nullreturn null;
}

5.3 对比JDK1.7的get()方法源码

5.3.1 JDK1.7的get()方法执行流程

5.3.2 JDK1.7的get()方法源码

/**
* 源码分析
*/ 
public V get(Object key) {  // 1. 当key == null时，则到 以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键if (key == null)  return getForNullKey(); // --> 分析1// 2. 当key ≠ null时，去获得对应值 -->分析2Entry<K,V> entry = getEntry(key);return null == entry ? null : Value();  
}  /**
* 分析1：getForNullKey()
* 作用：当key == null时，则到 以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
*/ 
private V getForNullKey() { // HashMap为空，直接返回nullif (size == 0) {  return null;  }  // 遍历以table[0]为头结点的链表，寻找 key==null 对应的值for (Entry<K,V> e = table[0]; e != null; e = e.next) {  // 从table[0]中取key==null的value值 if (e.key == null)  return e.value; }  return null;  
}  /**
* 分析2：getEntry(key)
* 作用：当key ≠ null时，去获得对应值
*/  
final Entry<K,V> getEntry(Object key) {  // HashMap为空，直接返回nullif (size == 0) {  return null;  }  // 1. 根据key值，通过hash（）计算出对应的hash值int hash = (key == null) ? 0 : hash(key);  // 2. 根据hash值计算出对应的数组下标// 3. 遍历 以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  Object k;  // 若 hash值 & key 相等，则证明该Entry = 我们要的键值对// 通过equals（）判断key是否相等if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k))))  return e;  }  return null;  
}

六、remove()方法

6.1 remove()方法的执行流程

流程图：

6.2 remove()方法源码

HashMap中有两个remove()方法,一般常用的是第一个

1、以key为参数的remove方法输入key–>key存在就删除，若删除成功则返回被删除的元素的value，删除失败返回null

public V remove(Object key) {// 被删除的元素Node<K,V> e;// 返回移除的节点的value值return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}

2、以key+value为参数的remove方法必须key和value都相同才删除

public boolean remove(Object key, Object value) {// 返回是否成功移除节点return removeNode(hash(key), key, value, true, true) != null;
}

ve(key) 不去判断值相不相等。

ve(key)、ve(key,value)、ve(key)需要判断value相不相等

但是两个方法都是在调用removeNode()方法

/**移除某个节点，根据下面四个条件进行移除hash - key 的hash值 key - keymatchValue - 如果为true，则仅在值相等时删除；如果是false，则值不管相不相等，只要key和hash值一致就移除该节点。movable - 如果为false，则在删除时不移动其他节点return - 返回被移除节点，未找到则返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {// tab：当前map 的数组，p：hash对应的数组索引index位置上的节点/遍历链表时表示当前遍历到的节点的前一个节点，n：数组长度，index：hash对应的数组索引// 这几个值在hashMap的源码中很常见Node<K,V>[] tab; Node<K,V> p; int n, index;// 前提判断 数组不为空，并且长度大于0 并且// hash对应的数组索引位置上的节点p也不为nullif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {// node：被移除的节点，e：当前头节点的下一个节点/遍历链表时表示当前遍历到的节点，// k：e节点的key，v：被移除节点node 的valueNode<K,V> node = null, e; K k; V v;// 如果第一个节点p就是目标节点，则将node指向第一个节点pif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))){node = p;}// 第一个节点不是，那就看看第一个节点还有没有下一个元素。// 如果有第二个节点else if ((e = p.next) != null) {// 如果刚刚第一个节点是红黑树if (p instanceof TreeNode){// 调用红黑树的查询节点的方法，getTreeNode()node = ((TreeNode<K,V>)p).getTreeNode(hash, key);}// 第一个节点不是红黑树，并且还有第二个节点，那就说明，这里是链表了else {// 那么开始循环链表，从第二个节点开始循环，因为第一个节点已经处理过了do {// 判断e节点是不是目标节点，是的话就将node指向e，并且终止循环if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}// e节点不是目标节点，那就将p节点指向e节点，// 然后while里面e节点后移，在进入循环后发现e是目标节点了，退出循环，退出后此时p节点还是e节点的前一个节点，也就保证了在整个循环的过程中，p节点始终是e节点的前一个节点。p = e;} while ((e = e.next) != null);// e指针后移，并且下一个节点不为null则继续遍历，不为null表示没到链表最后。}}// 找到目标节点了  matchValue为true，则仅在值相等时删除。如果是false，则值不管相不相等，只要key和hash值一致就移除该节点。if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {// 如果目标节点是红黑树if (node instanceof TreeNode){// 调用红黑树的删除节点方法((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);}// 目标节点是p节点，// 还记得之前 如果第一个节点p（数组桶中的节点）就是目标节点，则将node指向第一个节点pelse if (node == p){// 将目标节点的下一个节点作为该索引位置的第一个元素// 也就是跳过目标节点，指向目标节点的下一位tab[index] = ;}// 这里就是遍历链表找到了目标节点else{// p节点始终作为node的上一个节点&#始终指向目标节点node// 现在将p.next 指向目标节点node的next，这样跳过了目标节点node，就把node移除掉了p.next = ;}// 记录map结构被修改的次数，主要用于并发编程++modCount;// 记录table存储了多少键值对，因为移除了一个，所以此处就减一--size;// 该方法在hashMap中是空方法，主要是供LinkedHashMap使用，因为LinkedHashMap重写了该方法afterNodeRemoval(node);// 返回被移除的节点return node;}}// 没找到 返回nullreturn null;
}

6.3 JDK1.7的remove()方法源码

流程与JDK1.8基本一致，只是没有红黑树结构

/*** 函数：remove(Object key)* 作用：删除该键值对* @return 返回被删除的value值，如果删除失败返回Null */ 
public V remove(Object key) {  Entry<K,V> e = removeEntryForKey(key);  // 返回移除的节点的value值return (e == null ? null : e.value);  
}  final Entry<K,V> removeEntryForKey(Object key) {// HashMap为空，直接返回Null  if (size == 0) {  return null;  }  // 1. 计算hash值int hash = (key == null) ? 0 : hash(key);  // 2. 计算存储的数组下标位置int i = indexFor(hash, table.length);  // 定位到key值对应的数组位置// prev在后面遍历链表时指向当前节点的前一个节点，e表示当前遍历到的节点Entry<K,V> prev = table[i];  Entry<K,V> e = prev;  // 遍历链表，找到key和hash值与传入参入相同的节点，即为要删除的节点while (e != null) { // 记录当前节点的下一个节点 Entry<K,V> next = e.next;  Object k;  // 如果key值和hash值相同，则找到目标节点。执行移除操作if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k)))) {  // 记录map结构被修改的次数，主要用于并发编程modCount++;  // 记录table存储了多少键值对，因为移除了一个，所以此处就减一size--; // 若删除的是table数组中的元素（即链表的头结点） // 则删除操作 = 将头结点的next引用存入table[i]中  if (prev == e) table[i] = next;//否则 将以table[i]为头结点的链表中，当前Entry的前1个Entry中的next 设置为 当前Entry的next（即删除当前Entry = 直接跳过当前Entry）else   = next;   e.recordRemoval(this);  return e;  }  prev = e;  e = next;  }  // 返回删除的节点return e;  
}

七、HashMap其他操作方法

7.1 containsKey()方法

7.1.1 JDK1.8

判断key是否存在，实际上调用的就是get()方法使用的getNode()方法，找到就返回ture，找不到返回false

public boolean containsKey(Object key) {return getNode(hash(key), key) != null;
}

7.1.2 JDK1.7

/*** 函数：containsKey(Object key)* 作用：判断是否存在该键的键值对；是 则返回true* 原理：调用getEntry()，判断是否为Null*/
public boolean containsKey(Object key) {  return getEntry(key) != null; 
}

7.2 containsValue()方法

7.2.1 JDK1.8

判断value是否存在，根据给定的value查找当前map中是否有和value相同的节点，有的话返true，没有返回false；

public boolean containsValue(Object value) {// tab：当前map的数组，v：目标元素的valueNode<K,V>[] tab; V v;// 首先判断当前数组不为null 并且含有的元素数量大于0if ((tab = table) != null && size > 0) {// 遍历该数组for (int i = 0; i < tab.length; ++i) {// 遍历数组中每个索引位置的的链表/红黑树，这里需要注意，HashMap红黑树TreeNode节点在维护红黑树结构的同时，也维护了链表结构。// 也就是说TreeNode的红黑树也可以当成链表来进行遍历，其继承了LinkedHashMap.Entry<K,V>，有next属性// 因为这里需要遍历HashMap中的全部节点，所以直接使用链表结构进行遍历for (Node<K,V> e = tab[i]; e != null; e = e.next) {// 如果节点的value与入参value相等，就直接返回true，return 会停止循环并且退出方法。// 这种写法，即使传入的value是null也能进行查找，通过(v = e.value) == value即可查找value值为null的元素。不用向JDK1.7那样还要为传入value为null单独写一个遍历查询方法if ((v = e.value) == value || (value != null && value.equals(v)))// 存在该节点，返回truereturn true;}}}// 找不到则返回falsereturn false;
}

7.2.2 JDK1.7

/*** 函数：containsValue(Object value)* 作用：判断是否存在该值的键值对；是 则返回true*/   
public boolean containsValue(Object value) {  // 若value为空，则调用containsNullValue()  if (value == null)return containsNullValue();  // 若value不为空，则遍历链表中的每个Entry，通过equals()比较values 判断是否存在Entry[] tab = table;for (int i = 0; i < tab.length ; i++)  for (Entry e = tab[i] ; e != null ; e = e.next)  if (value.equals(e.value)) // 找到节点，返回true return true; return false;  
}  // value为空时调用的方法  
private boolean containsNullValue() {  Entry[] tab = table;  // 遍历所有节点，查找value为null的节点for (int i = 0; i < tab.length ; i++)  for (Entry e = tab[i] ; e != null ; e = e.next)  if (e.value == null)return true;  return false;  
}

  相关文章：【Java集合】HashMap系列（一）——底层数据结构分析
【Java集合】HashMap系列（三）——TreeNode内部类源码分析
  【Java集合】一文快速了解HashMap底层原理
  【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树