PS: 本文章已收录 开源项目《原理与源码解析》，如需要源文件或更多信息,请访问以下项目。

最佳阅读地址：

• http://hnov.gitee.io/sourcecodeanalysis

• https://hnov.github.io/sourceCodeAnalysis

put方法解析

• put(K key, V value)

• putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

• get(Object key)

• getNode(int hash, Object key)

• resize()

• treeifyBin(Node[] tab, int hash)

• containsKey(Object key)

• containsValue(Object value)

put()

概述

Map的put方法接受两个参数，key和value，该方法用于存储键值对。

HashMap的put方法只有一行代码

return putVal(hash(key), key, value, false, true); //参见：hash方法解析

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

首选对key值进行hash算法，key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。(h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位是不变的。)

方法解析

put方法是一个方便用户使用的快捷方式，具体逻辑都是在putVal方法中实现的，我们就针对putVal方法的实现来做解析。

首先判断table是不是为空，如果为空，说明是第一次执行put操作，需要确认数组的大小，从源码中可以看到，数组的初始大小是16，最大值为Integer.max_value。数组的大小必须是2的n次方。然后需要确认数据落在数组的哪一个位置上，也就是确认数组下标，确认数组下标是通过hash&(数组大小-1)相当于取余数的方式，如果数组下标位置没有存在其他节点，那么直接放入数组桶中(如图中的node0、node2)，如果发生了碰撞(数组下标位置存在其他节点)，如果key已经存在，说明节点已经存在，将对应节点的旧value换成新value，如果不存在将node链接到链表的后面(如图中的node1和node3)。

hashmap如果数据变大，数组是可以扩充的，常量定义了一个负载因子，默认是0.75，也就是说当数组的元素个数大于了扩容阀值(16*0.75=12)的时候，数组就开始扩充，扩充的大小是原来的两倍，因为要保证数组大小是2的n次方。如果链表过长会影响查询速度，jdk1.8对此做了改进，有一个常量 TREEIFY_THRESHOLD=8和 UNTREEIFY_THRESHOLD=6，如果链表的长度大于TREEIFYTHRESHOLD=8时，链表会转换成红黑树。如果执行remove操作的时候，红黑树节点又会变少，如果节点小于UNTREEIFYTHRESHOLD=6时，又会从红黑树转成链表。

static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子

/**

* @param hash key的hash值

* @param key 键

* @param value 值

* @param onlyIfAbsent 设为true表示如果键不存在，才会写入值。

* @param evict

* @return 返回value

*/

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K, V>[] tab;

Node<K, V> p;

int n, i; // 定义元素数组、当前元素变量

// 如果当前Map的元素数组为空 或者 数组长度为0，那么需要初始化元素数组

// tab = resize() 初始化了元素数组，resize方法同时也可以实现数组扩容，可参见：resize方法解析

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length; // n 设置为 数组长度

// 根据hash值和数组长度取摸计算出数组下标

if ((p = tab[i = (n - 1) & hash]) == null) // 如果该位置不存在元素，那么创建一个新元素存储到数组的该位置。

tab[i] = newNode(hash, key, value, null); // 此处单独解析

//如果当前位置已经有元素了，分为三种情况。

else {

// e 用来指向根据key匹配到的元素

Node<K, V> e;

K k;

//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，

//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p; // 用e指向到当前元素

//2.如果当前是红黑树结构，则把它加入到红黑树

// 如果要写入的key的hash值和当前元素的key的hash值不同，或者key不相等，说明不是同一个key，要通过其他数据结构来存储新来的数据

else if (p instanceof TreeNode)

e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); // 参见：putTreeVal方法解析

else {

//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部

// 运行到这里，说明采用链表结构来存储

for (int binCount = 0; ; ++binCount) { // 要逐一对比看要写入的key是否和链表上的某个key相同

if ((e = p.next) == null) { // 如果当前元素没有下一个节点

// 根据键值对创建一个新节点，挂到链表的尾部

p.next = newNode(hash, key, value, null);

// 如果新增节点前链表上元素的个数已经达到了阀值(可以改变存储结构的临界值)，其实在这这一时刻当前链表上的元素已经达到了9个。

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

// 将该链表上所有元素改为TreeNode方式存储(是为了增加查询性能，元素越多，链表的查询性能越差) 或者 扩容

treeifyBin(tab, hash); // 参见：treeifyBin方法解析

break;// 跳出循环，因为没有可遍历的元素了

}

// 如果下一个节点的 hash值和key值都和要写入的hash 和 key相同

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break; // 跳出循环，因为找到了相同的key对应的元素

p = e;

}

}

//① 此时e有两种情况

//1.说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值

//2.说明e是插入链表或者红黑树，成功后的新节点

if (e != null) { // 说明找了和要写入的key对应的元素，根据情况来决定是否覆盖值

V oldValue = e.value;

//用新值替换旧值，并返回旧值。

//oldValue为空，说明e是新增的节点或者也有可能旧值本来就是空的，因为hashmap可存空值

if (!onlyIfAbsent || oldValue == null) // 如果旧值为空 后者 指定了需要覆盖旧值，那么更改元素的值为新值

e.value = value;

//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，

//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能

afterNodeAccess(e);

return oldValue; // 返回旧值

}

}

// 执行到这里，说明是增加了新的元素，而不是替换了老的元素，所以相关计数需要累加

//fail-fast机制

++modCount; // 修改计数器递增

// 当前map的元素个数递增

if (++size > threshold) // 如果当前map的元素个数大于了扩容阀值，那么需要扩容元素数组了

resize(); // 元素数组扩容

afterNodeInsertion(evict); // 添加新元素之后的后后置处理， LinkedHashMap中有具体实现

return null; // 返回空

}

putTreeVal()

概述

我们都知道，目前HashMap是采用数组+链表+红黑树的方式来存储和组织数据的。

在put数据的时候，根据键的hash值寻址到具体数组位置，如果不存在hash碰撞，那么这个位置就只存储这么一个键值对。参见：put方法分析

如果两个key的hash值相同，那么对应数组位置上就需要用链表的方式将这两个数据组织起来，当同一个位置上链表中的元素达到9个(8+1 原链表上的8个元素+新put的元素 )的时候，就会再将这些元素构建成一个红黑树(参见：treeifyBin方法分析，同时把原来的单链表结构变成了双链表结构，也就是这些元素即维持着红黑树的结构又维持着双链表的结构。当新的相同hash值的键值对put过来时，发现该位置已经是一个树节点了，那么就会调用putTreeVal方法，将这个新的值设置到指定的key上。

方法解析

/**

* 当存在hash碰撞的时候，且元素数量大于8个时候，就会以红黑树的方式将这些元素组织起来

* map 当前节点所在的HashMap对象

* tab 当前HashMap对象的元素数组

* h 指定key的hash值

* k 指定key

* v 指定key上要写入的值

* 返回：指定key所匹配到的节点对象，针对这个对象去修改V(返回空说明创建了一个新节点)

*/

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,

int h, K k, V v) {

Class> kc = null; // 定义k的Class对象

boolean searched = false; // 标识是否已经遍历过一次树，未必是从根节点遍历的，但是遍历路径上一定已经包含了后续需要比对的所有节点。

TreeNode<K,V> root = (parent != null) ? root() : this; // 父节点不为空那么查找根节点，为空那么自身就是根节点

for (HashMap.TreeNode<K,V> p = root;;) {

int dir, ph;

K pk; // 声明方向、当前节点hash值、当前节点的键对象

if ((ph = p.hash) > h) // 如果当前节点hash 大于 指定key的hash值

dir = -1; // 要添加的元素应该放置在当前节点的左侧

else if (ph < h) // 如果当前节点hash 小于 指定key的hash值

dir = 1; // 要添加的元素应该放置在当前节点的右侧

else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 如果当前节点的键对象 和 指定key对象相同

return p; // 那么就返回当前节点对象，在外层方法会对v进行写入

// 走到这一步说明 当前节点的hash值 和 指定key的hash值 是相等的，但是equals不等

else if ((kc == null &&

(kc = comparableClassFor(k)) == null) ||

(dir = compareComparables(kc, k, pk)) == 0) {

// 走到这里说明：指定key没有实现comparable接口 或者 实现了comparable接口并且和当前节点的键对象比较之后相等(仅限第一次循环)

/*

* searched 标识是否已经对比过当前节点的左右子节点了

* 如果还没有遍历过，那么就递归遍历对比，看是否能够得到那个键对象equals相等的的节点

* 如果得到了键的equals相等的的节点就返回

* 如果还是没有键的equals相等的节点，那说明应该创建一个新节点了

*/

if (!searched) { // 如果还没有比对过当前节点的所有子节点

TreeNode<K, V> q, ch; // 定义要返回的节点、和子节点

searched = true; // 标识已经遍历过一次了

/*

* 红黑树也是二叉树，所以只要沿着左右两侧遍历寻找就可以了

* 这是个短路运算，如果先从左侧就已经找到了，右侧就不需要遍历了

* find 方法内部还会有递归调用。参见：find方法解析

*/

if (((ch = p.left) != null &&

(q = ch.find(h, k, kc)) != null) ||

((ch = p.right) != null &&

(q = ch.find(h, k, kc)) != null))

return q; // 找到了指定key键对应的

}

// 走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点

dir = tieBreakOrder(k, pk); // 再比较一下当前节点键和指定key键的大小

}

TreeNode<K, V> xp = p; // 定义xp指向当前节点

/*

* 如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较

* 如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较

* 如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较

*/

if ((p = (dir <= 0) ? p.left : p.right) == null) {

// 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点

Node<K, V> xpn = xp.next; // 获取当前节点的next节点

TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn); // 创建一个新的树节点

if (dir <= 0)

xp.left = x; // 左孩子指向到这个新的树节点

else

xp.right = x; // 右孩子指向到这个新的树节点

xp.next = x; // 链表中的next节点指向到这个新的树节点

x.parent = x.prev = xp; // 这个新的树节点的父节点、前节点均设置为 当前的树节点

if (xpn != null) // 如果原来的next节点不为空

((TreeNode<K, V>) xpn).prev = x; // 那么原来的next节点的前节点指向到新的树节点

moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根节点置顶

return null; // 返回空，意味着产生了一个新节点

}

}

}

treeifyBin()

概述

treeifyBin方法，应该可以解释为：把容器里的元素变成树结构。当HashMap的内部元素数组中某个位置上存在多个hash值相同的键值对，这些Node已经形成了一个链表，当该链表的长度大于等于9(为什么是9？TREEIFY_THRESHOLD默认值为8呀？详见put方法解析的时候，会调用该方法来进行一个特殊处理。

方法解析

/**

* tab：元素数组，

* hash：hash值(要增加的键值对的key的hash值)

*/

final void treeifyBin(Node<K,V>[] tab, int hash) {

int n, index; Node<K,V> e;

/*

* 如果元素数组为空 或者 数组长度小于 树结构化的最小限制

* MIN_TREEIFY_CAPACITY 默认值64，对于这个值可以理解为：如果元素数组长度小于这个值，没有必要去进行结构转换

* 当一个数组位置上集中了多个键值对，那是因为这些key的hash值和数组长度取模之后结果相同。(并不是因为这些key的hash值相同)

* 因为hash值相同的概率不高，所以可以通过扩容的方式，来使得最终这些key的hash值在和新的数组长度取模之后，拆分到多个数组位置上。

*/

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

resize(); // 扩容，可参见resize方法解析

// 如果元素数组长度已经大于等于了 MIN_TREEIFY_CAPACITY，那么就有必要进行结构转换了

// 根据hash值和数组长度进行取模运算后，得到链表的首节点

else if ((e = tab[index = (n - 1) & hash]) != null) {

TreeNode<K,V> hd = null, tl = null; // 定义首、尾节点

do {

TreeNode<K,V> p = replacementTreeNode(e, null); // 将该节点转换为 树节点

if (tl == null) // 如果尾节点为空，说明还没有根节点

hd = p; // 首节点(根节点)指向 当前节点

else { // 尾节点不为空，以下两行是一个双向链表结构

p.prev = tl; // 当前树节点的 前一个节点指向 尾节点

tl.next = p; // 尾节点的 后一个节点指向 当前节点

}

tl = p; // 把当前节点设为尾节点

} while ((e = e.next) != null); // 继续遍历链表

// 到目前为止 也只是把Node对象转换成了TreeNode对象，把单向链表转换成了双向链表

// 把转换后的双向链表，替换原来位置上的单向链表

if ((tab[index] = hd) != null)

hd.treeify(tab);//此处可参见treeify方法解析

}

}

resize()

概述

HashMap的resize方法的作用：在向HashMap里put元素的时候，HashMap基于扩容规则发现需要扩容的时候会调用该方法来进行扩容。

总结：HashMap 扩容后，原来的元素，要么在原位置(低位)，要么在 原位置+原数组长度 那个位置上(高位)。

方法解析

final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table; //当前所有元素所在的数组，称为老的元素数组

int oldCap = (oldTab == null) ? 0 : oldTab.length; //老的元素数组长度

int oldThr = threshold; // 老的扩容阀值设置

int newCap, newThr = 0; // 新数组的容量，新数组的扩容阀值都初始化为0

if (oldCap > 0) { // 如果老数组长度大于0，说明已经存在元素

// PS1

if (oldCap >= MAXIMUM_CAPACITY) { // 如果数组元素个数大于等于限定的最大容量(2的30次方)

// 扩容阀值设置为int最大值(2的31次方 -1 )，因为oldCap再乘2就溢出了。

threshold = Integer.MAX_VALUE;

return oldTab; // 返回老的元素数组

}

/*

* 如果数组元素个数在正常范围内，那么新的数组容量为老的数组容量的2倍(左移1位相当于乘以2)

* 如果扩容之后的新容量小于最大容量 并且 老的数组容量大于等于默认初始化容量(16)，那么新数组的扩容阀值设置为老阀值的2倍。(老的数组容量大于16意味着：要么构造函数指定了一个大于16的初始化容量值，要么已经经历过了至少一次扩容)

*/

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

// PS2

// 运行到这个else if 说明老数组没有任何元素

// 如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值

// 这一步也就意味着构造该map的时候，指定了初始化容量。

else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

else { // zero initial threshold signifies using defaults

// 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素

newCap = DEFAULT_INITIAL_CAPACITY; // 设置新数组容量 为 16

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 设置新数组扩容阀值为 16*0.75 = 12。0.75为负载因子(当元素个数达到容量了4分之3，那么扩容)

}

// 如果扩容阀值为0 (PS2的情况)

if (newThr == 0) {

float ft = (float)newCap * loadFactor;

newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

(int)ft : Integer.MAX_VALUE); // 参见：PS2

}

threshold = newThr; // 设置map的扩容阀值为 新的阀值

@SuppressWarnings({"rawtypes","unchecked"})

// 创建新的数组(对于第一次添加元素，那么这个数组就是第一个数组；对于存在oldTab的时候，那么这个数组就是要需要扩容到的新数组)

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

table = newTab; // 将该map的table属性指向到该新数组

if (oldTab != null) { // 如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作

for (int j = 0; j < oldCap; ++j) { // 遍历老数组

Node<K,V> e;

if ((e = oldTab[j]) != null) { // 如果当前位置元素不为空，那么需要转移该元素到新数组

oldTab[j] = null; // 释放掉老数组对于要转移走的元素的引用(主要为了使得数组可被回收)

if (e.next == null) // 如果元素没有有下一个节点，说明该元素不存在hash冲突

// PS3

// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模

// 【hash值 % 数组长度】 = 【 hash值 & (数组长度-1)】

// 这种与运算求模的方式要求 数组长度必须是2的N次方，但是可以通过构造函数随意指定初始化容量呀，如果指定了17,15这种，岂不是出问题了就？没关系，最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。15 -> 16、17-> 32

newTab[e.hash & (newCap - 1)] = e;

// 如果该元素有下一个节点，那么说明该位置上存在一个链表了(hash相同的多个元素以链表的方式存储到了老数组的这个位置上了)

// 例如：数组长度为16，那么hash值为1(1%16=1)的和hash值为17(17%16=1)的两个元素都是会存储在数组的第2个位置上(对应数组下标为1)，当数组扩容为32(1%32=1)时，hash值为1的还应该存储在新数组的第二个位置上，但是hash值为17(17%32=17)的就应该存储在新数组的第18个位置上了。

// 所以，数组扩容后，所有元素都需要重新计算在新数组中的位置。

else if (e instanceof TreeNode) // 如果该节点为TreeNode类型

((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 此处单独展开讨论

else { // preserve order

Node<K,V> loHead = null, loTail = null; // 按命名来翻译的话，应该叫低位首尾节点

Node<K,V> hiHead = null, hiTail = null; // 按命名来翻译的话，应该叫高位首尾节点

// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1

Node<K,V> next;

// 遍历链表

do {

next = e.next;

// 这一步判断好狠，拿元素的hash值 和 老数组的长度 做与运算

// PS3里曾说到，数组的长度一定是2的N次方(例如16)，如果hash值和该长度做与运算，那么该hash值可参与计算的有效二进制位就是和长度二进制对等的后几位，如果结果为0，说明hash值中参与计算的对等的二进制位的最高位一定为0.

//因为数组长度的二进制有效最高位是1(例如16对应的二进制是10000)，只有*..0**** 和 10000 进行与运算结果才为00000(*..表示不确定的多个二进制位)。又因为定位下标时的取模运算是以hash值和长度减1进行与运算，所以下标 = (*..0**** & 1111) 也= (*..0**** & 11111) 。1111是15的二进制、11111是16*2-1 也就是31的二级制(2倍扩容)。

// 所以该hash值再和新数组的长度取摸的话mod值也不会放生变化，也就是说该元素的在新数组的位置和在老数组的位置是相同的，所以该元素可以放置在低位链表中。

if ((e.hash & oldCap) == 0) {

// PS4

if (loTail == null) // 如果没有尾，说明链表为空

loHead = e; // 链表为空时，头节点指向该元素

else

loTail.next = e; // 如果有尾，那么链表不为空，把该元素挂到链表的最后。

loTail = e; // 把尾节点设置为当前元素

}

// 如果与运算结果不为0，说明hash值大于老数组长度(例如hash值为17)

// 此时该元素应该放置到新数组的高位位置上

// 例：老数组长度16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上，也就是下标为16，那么下标为16已经属于高位了，低位是[0-15]，高位是[16-31]

else { // 以下逻辑同PS4

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ((e = next) != null);

if (loTail != null) { // 低位的元素组成的链表还是放置在原来的位置

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) { // 高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置。

hiTail.next = null;

newTab[j + oldCap] = hiHead; // 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标；hash为 18 在老数组放置在1下标，在新数组÷放置在17下标；

}

}

}

}

}

return newTab; // 返回新数组

}

resize过程图解

经过上面的代码分析可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图(a)表示扩容前的key1和key2两种key确定索引位置的示例，图(b)表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图.

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。

没看过瘾?想要源文件?

  还没开始就结束了？由于微信公众号篇幅限制有限,特在Gitee和Github开源了源文件 以及GitPage。如需查看完整HashMap解析或了解更多，请查看

开源项目《原理与源码解析》，项目地址：

http://hnov.gitee.io/sourcecodeanalysis