前言：由于笔者所在的公司用的是jdk1.8，故该源码是针对1.8分析的。
首先：我们看一张长的很丑的HashMap的结构图：
再看看几个核心的常量：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始化容器大小，当自己指定容器大小时，必须为2的幂次方 static final int MAXIMUM_CAPACITY = 1 << 30; //容器的最大容量值 static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载因子 static final int TREEIFY_THRESHOLD = 8; //把桶中链表转换为红黑树的阈值 static final int UNTREEIFY_THRESHOLD = 6; //把红黑树转换成链表的阈值 static final int MIN_TREEIFY_CAPACITY = 64; //最小的表容量使桶被树化，当表的容量小于该值时，先扩容解决hash冲突而不是树化
putVal（）方法：
1 /** 2 * 实现Map.put和相关方法 3 * 4 * @param hash 根据key计算出来的hash值 5 * @param key 键 6 * @param value 值 7 * @param onlyIfAbsent 如果为true则不改变value值，即如果不存在则添加。 8 * @param evict 如果false，表处于创建模式，put方法给的是true 9 * @return 返回旧值，如果不存在则返回null 10 */ 11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 12 boolean evict) { 13 Node<K,V>[] tab; Node<K,V> p; int n, i; 14 if ((tab = table) == null || (n = tab.length) == 0) //如果表为空，调用resize（）初始化，该方法的分析在下面，建议先把putValue方法看完 15 n = (tab = resize()).length; 16 if ((p = tab[i = (n - 1) & hash]) == null) //根据当前key的hashcode定位到具体的桶中并判断是否为空，如果为空，创建一个节点并复制给该桶 17 tab[i] = newNode(hash, key, value, null); 18 else { 19 Node<K,V> e; K k; 20 if (p.hash == hash && 21 ((k = p.key) == key || (key != null && key.equals(k)))) //如果当前桶的key的hashcode与要设置的key的相同，且键值相等，用要插入的key对应的value覆盖原来key的value 22 e = p; 23 else if (p instanceof TreeNode) //如果当前桶为红黑树，则按照红黑树的方式写入数据，分析在下 24 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 25 else { //表示当前桶为链表，不是红黑树 26 for (int binCount = 0; ; ++binCount) { //遍历链表 27 if ((e = p.next) == null) { //当遍历到链表中的最后一个元素 28 p.next = newNode(hash, key, value, null); //把要插入的key、value封装成一个新的节点写入当前桶的后面 29 if (binCount >= TREEIFY_THRESHOLD - 1) // 当该链表的值大于树形化的预设阈值时，需要将该链表转换为红黑树 30 treeifyBin(tab, hash); //树形化方法 31 break; 32 } 33 if (e.hash == hash && //在遍历链表的过程中发现有与要设置的key相同hashcode和键值的key，直接覆盖原来的key中的value，即更新value 34 ((k = e.key) == key || (key != null && key.equals(k)))) 35 break; 36 p = e; 37 } 38 } 39 if (e != null) { // 用要插入的key称为key1的value值覆盖原来桶中与key1的hashcode和键值相等的key的value 40 V oldValue = e.value; 41 if (!onlyIfAbsent || oldValue == null) 42 e.value = value; 43 afterNodeAccess(e); 44 return oldValue; 45 } 46 } 47 ++modCount; 48 if (++size > threshold) //当前表中的桶的个数大于阈值时，扩容当前表 49 resize(); //扩容（resize方法中包含了初始化和扩容） 50 afterNodeInsertion(evict); 51 return null; 52 }
resize()方法：
1 /** 2 *初始化或增加表大小。 如果为空，则根据字段阈值中保持的初始容量目标进行分配。 3 *即初始化 。扩容时，因为表的容量使用的是2的幂，所以每个桶中的元素必须保持相 4 *同的索引，或者在新表中以2的幂偏移，即扩容的操作。 5 * @return the table 6 */ 7 final Node<K,V>[] resize() { 8 Node<K,V>[] oldTab = table; 9 int oldCap = (oldTab == null) ? 0 : oldTab.length; 10 int oldThr = threshold; // threshold表示阈值，当new HashMap时未指定容量大小时，该值为DEFAULT_INITIAL_CAPACITY 11 int newCap, newThr = 0; 12 if (oldCap > 0) { // 原始hash表的容量不为零，即进行扩容操作 13 if (oldCap >= MAXIMUM_CAPACITY) { // 原始hash表的容量已经达到最大容量 14 threshold = Integer.MAX_VALUE; 15 return oldTab; 16 } 17 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 把原始hash表的容量扩大一倍得到新的容量 18 oldCap >= DEFAULT_INITIAL_CAPACITY) 19 newThr = oldThr << 1; // 把旧的阈值扩大一倍赋值给新的阈值 20 } 21 else if (oldThr > 0) // 原始hash表的容量为0且指定了阈值时，初始化时把hash表的容量设置为初始阈值 22 newCap = oldThr; 23 else { // 未指定初始化阈值时，使用默认的值 24 newCap = DEFAULT_INITIAL_CAPACITY; 25 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 26 } 27 if (newThr == 0) { 28 float ft = (float)newCap * loadFactor; 29 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 30 (int)ft : Integer.MAX_VALUE); 31 } 32 threshold = newThr; 33 @SuppressWarnings({"rawtypes","unchecked"}) 34 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 35 table = newTab; 36 if (oldTab != null) { // 扩容操作 37 for (int j = 0; j < oldCap; ++j) { // 遍历原始hash表的每一个桶 38 Node<K,V> e; 39 if ((e = oldTab[j]) != null) { 40 oldTab[j] = null; // 把原始hash表的桶置为空 41 if (e.next == null) 42 newTab[e.hash & (newCap - 1)] = e; // 如果hash表中的第j个桶为空，通过hash算法计算出e在新的hash表中的位置，并把e放入该桶中 43 else if (e instanceof TreeNode) // 如果hash表中的第j个桶是红黑树，则以红黑树的规则添加元素 44 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 45 else { // 保留顺序 46 Node<K,V> loHead = null, loTail = null; // loHead：用于指向原 47 Node<K,V> hiHead = null, hiTail = null; 48 Node<K,V> next; 49 do { 50 next = e.next; 51 if ((e.hash & oldCap) == 0) { // (e.hash & oldCap) == 0表示元素位置在扩容后不变 52 if (loTail == null) //该段逻辑的主要作用是让loHead指向不需移动位置的元素组成的链表的头，loTail指向尾 53 loHead = e; 54 else 55 loTail.next = e; 56 loTail = e; 57 } 58 else { // 元素位置在扩容后位置发生变化，新的下标位置为原下标位置+原数组长度 59 if (hiTail == null) // 该段逻辑主要作用是让hiHead指向需要移动位置的元素组成的链表的头，hiTail指向尾 60 hiHead = e; 61 else 62 hiTail.next = e; 63 hiTail = e; 64 } 65 } while ((e = next) != null); 66 if (loTail != null) { 67 loTail.next = null; // 链表的最后一个元素指向null 68 newTab[j] = loHead; // 把不需要改变位置的链表赋值到新的hash表中，位置为原数组下标 69 } 70 if (hiTail != null) { 71 hiTail.next = null; // 链表的最后一个元素指向null 72 newTab[j + oldCap] = hiHead; // 把需要改变位置的链表赋值到新的hash表中，位置为原下标位置+原数组长度 73 } 74 } 75 } 76 } 77 } 78 return newTab; 79 }
*注：以上代码中loHead用来指向hash表扩容后元素位置不变的链表头，loTail指向链表尾；hiHead用来指向hash表扩容后元素位置变化的链表头，hiTail指向链表尾。
*例子：假设有一个hash表h，长度为8（oldcap）,现有hashcode分别为3，11 ， 19 的三个元素要插入hash表中，通过hash算法 （e.hashcode & (oldCap - 1))得到元素下标位置都为3。扩容后通过
（e.hashcode & oldcap)得到的是元素是否需要移动（0表示需要，1表示不需要），以上三个元素经过计算得到的值分别为0，1，0，此时3和19组成新的链表,而loHead指向该链表的头，liTail指向该
链表的尾；11单独成一个新的链表，hiHead指向该链表的头，hiTail指向该链表的尾部。
putTreeVal（）方法：
1 /** 2 * 当存在hash碰撞的时候，且元素数量大于8个（hash表的容量也需要大于64，否则会做扩容操作）时候，就会以红黑树的方式将这些元素组织起来 3 * map 当前节点所在的HashMap对象 4 * tab 当前HashMap对象的元素数组 5 * h 指定key的hash值 6 * k 指定key 7 * v 指定key上要写入的值 8 * 返回：指定key所匹配到的节点对象，针对这个对象去修改V（返回空说明创建了一个新节点） 9 */ 10 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, 11 int h, K k, V v) { 12 Class<?> kc = null; // 定义k的Class对象 13 boolean searched = false; // 标识是否已经遍历过一次树，未必是从根节点遍历的，但是遍历路径上一定已经包含了后续需要比对的所有节点。 14 TreeNode<K,V> root = (parent != null) ? root() : this; // 父节点不为空那么查找根节点，为空那么自身就是根节点 15 for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历，没有终止条件，只能从内部退出 16 int dir, ph; K pk; // 声明方向、当前节点hash值、当前节点的键对象 17 if ((ph = p.hash) > h) // 如果当前节点hash 大于 指定key的hash值 18 dir = -1; // 要添加的元素应该放置在当前节点的左侧 19 else if (ph < h) // 如果当前节点hash 小于 指定key的hash值 20 dir = 1; // 要添加的元素应该放置在当前节点的右侧 21 else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 如果当前节点的键对象 和 指定key对象相同 22 return p; // 那么就返回当前节点对象，在外层方法会对v进行写入 23 24 // 走到这一步说明 当前节点的hash值 和 指定key的hash值 是相等的，但是equals不等 25 else if ((kc == null && 26 (kc = comparableClassFor(k)) == null) || 27 (dir = compareComparables(kc, k, pk)) == 0) { 28 29 // 走到这里说明：指定key没有实现comparable接口 或者 实现了comparable接口并且和当前节点的键对象比较之后相等（仅限第一次循环） 30 31 32 /* 33 * searched 标识是否已经对比过当前节点的左右子节点了 34 * 如果还没有遍历过，那么就递归遍历对比，看是否能够得到那个键对象equals相等的的节点 35 * 如果得到了键的equals相等的的节点就返回 36 * 如果还是没有键的equals相等的节点，那说明应该创建一个新节点了 37 */ 38 if (!searched) { // 如果还没有比对过当前节点的所有子节点 39 TreeNode<K,V> q, ch; // 定义要返回的节点、和子节点 40 searched = true; // 标识已经遍历过一次了 41 /* 42 * 红黑树也是二叉树，所以只要沿着左右两侧遍历寻找就可以了 43 * 这是个短路运算，如果先从左侧就已经找到了，右侧就不需要遍历了 44 * find 方法内部还会有递归调用。参见：find方法解析 45 */ 46 if (((ch = p.left) != null && 47 (q = ch.find(h, k, kc)) != null) || 48 ((ch = p.right) != null && 49 (q = ch.find(h, k, kc)) != null)) 50 return q; // 找到了指定key键对应的 51 } 52 53 // 走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点 54 dir = tieBreakOrder(k, pk); // 再比较一下当前节点键和指定key键的大小 55 } 56 57 TreeNode<K,V> xp = p; // 定义xp指向当前节点 58 /* 59 * 如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较 60 * 如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较 61 * 如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较 62 */ 63 if ((p = (dir <= 0) ? p.left : p.right) == null) { 64 // 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点 65 Node<K,V> xpn = xp.next; // 获取当前节点的next节点 66 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建一个新的树节点 67 if (dir <= 0) 68 xp.left = x; // 左孩子指向到这个新的树节点 69 else 70 xp.right = x; // 右孩子指向到这个新的树节点 71 xp.next = x; // 链表中的next节点指向到这个新的树节点 72 x.parent = x.prev = xp; // 这个新的树节点的父节点、前节点均设置为 当前的树节点 73 if (xpn != null) // 如果原来的next节点不为空 74 ((TreeNode<K,V>)xpn).prev = x; // 那么原来的next节点的前节点指向到新的树节点 75 moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根节点置顶 76 return null; // 返回空，意味着产生了一个新节点 77 } 78 } 79 }
以上是对HashMap中putValue的分析，其它的方法需要有空的时候再写了。
原文：https://www.cnblogs.com/noah-sheng/p/12074511.html