JDK11源码分析之集合类（一)----HashMap

一，首先需要拉取JDK11源码：

方便起见我给出芋道源码作者已经拉取好的openJDK11的GitHub地址只需要fork一下克隆到本地导入IDEA中就可以对源码分析了：

https://github.com/YunaiV/openjdk

二，拉取成功导入项目成功后就开始分析源码了：

我们今天先分析HashMap源码：

HashMap所属的包在：openjdksrcjava.baseshareclassesjavautil 下,如图：

 

 三，HashMap源码分析详细注释：

复制代码package java.util; import java.io.IOException; import java.io.InvalidObjectException; import java.io.Serializable; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Consumer; import java.util.function.Function; import jdk.internal.misc.SharedSecrets; /** * * 基于哈希表实现的{Map}接口。这个实现提供了所有可选的映射操作，并允许{ null}值 * 和{ null}键。({ HashMap}类大致相当于{ Hashtable}，只是它是不同步的， * 并且允许为空。)该类不保证映射的顺序; * * * <p>这个实现为基本操作({ get}和{ put})提供了常量时间性能，假设散列函数正确地将元素分散到各个桶中。 * 集合视图的迭代需要与{ HashMap}实例的“容量”(桶的数量)及其大小(键值映射的数量)成比例的时间。 * 因此，如果迭代性能很重要，那么不要将初始容量设置得太高(或负载因子过低)。 { HashMap}的一个实例有两个影响其性能的参数:<i>初始容量</i>和<i>负载因子</i>。 <i>capacity</i>是哈希表中的桶数，初始容量就是建哈希表时的容量。 <i>load factor</i>是在哈希表的容量自动增加之前允许它获得的满值的度量。 当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表是<i>rehash </i>(即重新构建内部数据结构)， 因此哈希表的桶数大约是桶数的两倍。 */ public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { /** * 序列号 */ private static final long serialVersionUID = 362498820763181265L; /** * 默认的初始容量，必须是2的整数次方 * 初始化状态长度是16。数组中每个元素我们这里称之为桶， * 桶存储的是key的hash值，每个桶后面挂载着链表， * 链表中存储的是具体的数据value。 * */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量，如果大于这个值则使用这个值 * 必须是2的幂 <= 1<<30。 * MAXIMUM_CAPACITY为什么设置成1 << 30 ？ * MAXIMUM_CAPACITY含义是map的最大容量。 * 它是int类型，使用<<移位运算符的结果不能超过int可以表示的最大值。 * 固最大只能左移30，再大就溢出了。 * * java中的int占4个字节，每个字节8位，所以总共是占用32位。int是有符号的， * 其中第一位是符号位。所以还剩下31位。那么最多就是左移30了。 * 1 << 2 = 4(十进制) = 100(二进制) */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认负载因子为 0.75，即：如果数组长度为16当有16*0.15=12个占满，则考虑扩容 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 链表长度大于 8 时，转换为红黑树 */ static final int TREEIFY_THRESHOLD = 8; /** * 扩容时，如果发现树中节点数量小于6，则将树还原为链表 */ static final int UNTREEIFY_THRESHOLD = 6; /** * map容器中某个箱子（bin）再有链表转为树之前还要满足键值对数量大于 64 才会发生转换。 * 目的是为了避免 resizing（扩容） 和 treeification（链表转树结构）之间的冲突 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } /* ---------------- Static utilities -------------- */ /** * 哈希算法： *首先获取对象的hashCode()值，然后将hashCode值右移16位， * 然后将右移后的值与原来的hashCode做异或运算，返回结果。 * （其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展， * 无论正数还是负数，都在高位插入0）。 * * */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * Returns x's Class if it is of the form "class C implements * Comparable<C>", else null. */ static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (Type t : ts) { if ((t instanceof ParameterizedType) && ((p = (ParameterizedType) t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } /** * Returns k.compareTo(x) if x matches kc (k's screened comparable * class), else 0. */ @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable static int compareComparables(Class<?> kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); } /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } /* ---------------- Fields -------------- */ /** * 存储hash的数组，首次使用时初始化，长度总是2的幂次方 */ transient Node<K,V>[] table; /** * 存放实际的键值对 */ transient Set<Map.Entry<K,V>> entrySet; /** * HashMap中实际存在的键值对数量,注意和table的长度length、容纳最大键值对数量threshold的区别 */ transient int size; /** * 用来记录HashMap内部结构发生变化的次数（计数器） */ transient int modCount; /** * 当前 HashMap 所能容纳键值对数量的最大值,超过这个,则需扩容 * @serial */ int threshold; /** * 负载因子 * * @serial */ final float loadFactor; /* ---------------- Public operations -------------- */ /** * 构造函数 */ /** * （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或等于0，不能为非数字 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //初始化填充因子 this.loadFactor = loadFactor; //初始化threshold大小 this.threshold = tableSizeFor(initialCapacity); } /** * （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); } /** * 说明：putMapEntries(Map<? extends K, ? extends V> m, * boolean evict)函数将m的所有元素存入本HashMap实例中。 */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //获取该map的实际长度 int s = m.size(); if (s > 0) { //判断table是否已经初始化 if (table == null) { // pre-size //未初始化，s 为 m 的实际元素个数 /**求出需要的容量，因为实际使用的长度=容量*0.75得来的，+1是因为小数相除， * 基本都不会是整数，容量大小不能为小数的，后面转换为int，多余的小数就要 * 被丢掉，所以+1，例如，map实际长度22，22/0.75=29.3,所需要的容量肯定为30， * 有人会问如果刚刚好除得整数呢，除得整数的话，容量大小多1也没什么影响**/ float ft = ((float)s / loadFactor) + 1.0F; //判断该容量大小是否超出上限。 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //计算得到的t大于阈值，则初始化阈值 if (t > threshold) threshold = tableSizeFor(t); } //如果已经初始化，并且m元素个数大于阈值，进行扩容处理 else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } /** * Returns the number of key-value mappings in this map. * * @return the number of key-value mappings in this map */ public int size() { return size; } /** * Returns {@code true} if this map contains no key-value mappings. * * @return {@code true} if this map contains no key-value mappings */ public boolean isEmpty() { return size == 0; } /** * Get方法： * HashMap并没有直接提供getNode接口给用户调用，而是提供的get方法， * 而get方法就是通过getNode来取得元素的。 * @see #put(Object, Object) */ /** * HashMap的数据存储实现原理 * * 流程： * * 1. 根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)； * * 2. 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)，这样就找到该key的存放位置了： * * ① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null； * * ② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作； * * ③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样： * * 如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null；如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。 */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get 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) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //table已经初始化，长度大于0，根据hash寻找table中的项也不为空 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //桶中第一项（数组元素）相等 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //桶中不止一个节点 if ((e = first.next) != null) { //为红黑树节点 if (first instanceof TreeNode) //在红黑树中查找 return ((TreeNode<K,V>)first).getTreeNode(hash, key); //否则，在链表中查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } /** * Returns {@code true} if this map contains a mapping for the * specified key. * * @param key The key whose presence in this map is to be tested * @return {@code true} if this map contains a mapping for the specified * key. */ public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with {@code key}, or * {@code null} if there was no mapping for {@code key}. * (A {@code null} return can also indicate that the map * previously associated {@code null} with {@code key}.) */ public V put(K key, V value) { //对key的hashCode()作再hash处理，目的是减少hash冲突的概率 /**四个参数，第一个hash值，第四个参数表示如果该key存在值， * 如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用， * 可以不用管，使用默认的即可 * **/ return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods. *putVal()方法，插入操作： * ①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标 Node<K,V>[] tab; Node<K,V> p; int n, i; //步骤一：tab为空则创建 //table未初始化或者长度为0，进行扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //步骤二：计算index，并对null做处理 //(n -1) & hash 确定元素存放在哪个桶中，桶为空，新生成节点放入桶中（此时这个节点存放在数组中） if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //桶中已经存在元素 /** * 发生hash冲突的几种情况： */ else { Node<K,V> e; K k; /** * 第一种，插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点 */ //步骤三：节点key存在，直接覆盖value //比较桶中第一个元素（数组中的节点）的hash值相等，key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //将第一个元素赋给e，用e来记录 e = p; /** * 第二种：hash值不等于首节点，不为红黑树的节点，则为链表的节点 */ //步骤四：判断链表为红黑树 //hash值不相等，即key不相等：为红黑树 else if (p instanceof TreeNode) //放入树中 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); /** * 第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点 */ //步骤五：该链为链表 //为链表节点 else { //遍历该链表，在链表最末尾插入节点 for (int binCount = 0; ; ++binCount) { //到达链表的尾部 if ((e = p.next) == null) { //在尾部插入新节点 p.next = newNode(hash, key, value, null); //节点数量达到阈值，转化为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); //跳出循环 break; } //判断链表中节点的key值与插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //相等，跳出循环 break; //用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 p = e; } } //表示在桶中找到key值，hash值与插入元素相等的节点 if (e != null) { // existing mapping for key //记录e的value V oldValue = e.value; //onlyIfAbsent为false或者旧值为null if (!onlyIfAbsent || oldValue == null) //用新值替换旧值 e.value = value; //访问后回调 afterNodeAccess(e); //返回旧值 return oldValue; } } //结构性修改 ++modCount; //步骤六：超过最大容量，就扩容 //实际大小大于阈值则扩容 if (++size > threshold) resize(); //插入后回调 afterNodeInsertion(evict); return null; } /** * 扩容： * @return the table */ /** * ①.1.8中resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容； * ②.每次扩展的时候，都是扩展2倍； * ③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。 * @return */ final Node<K,V>[] resize() { //oldTab指向hash桶数组 Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //如果oldCap不为空的话，就是hash桶数组不为空 if (oldCap >= MAXIMUM_CAPACITY) {//如果数组容量大于最大容量，就赋值为整数最大的阈值，不再扩容 threshold = Integer.MAX_VALUE; return oldTab;//返回 } //如果当前hash桶数组的长度在扩容后仍然小于最大容量，并且oldCap大于默认值16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //将当前数组扩大一倍 newThr = oldThr << 1; // double threshold 双倍扩容阈值 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr;//设置新的阈值 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组 table = newTab;//将新数组的值赋值给旧的hash桶数组 if (oldTab != null) { //循环遍历老map中的所有数据，迁移到新数组中对应位置，进行扩容操作 //进行扩容操作，复制Node对象到新的hash桶数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j节点处不为空，复制给e oldTab[j] = null;//将旧的hash桶数组在j节点处设置为空，方便gc if (e.next == null)//如果e后面没有Node节点 newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得储存位置 else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中 ((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; Node<K,V> next; do { next = e.next;//将Node节点的next赋值给next if ((e.hash & oldCap) == 0) {//如果节点e的hash值与原来hash桶数组的长度做与运算为0 if (loTail == null)//如果loTail为null loHead = e;//将e节点赋值给loHead else loTail.next = e;//否则将赋值给loTail.next loTail = e;//然后将e赋值给loTail } else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0 if (hiTail == null)//如果hiTail为null hiHead = e;//将e赋值给hiHead else hiTail.next = e;//如果hiTail不为空，将e复制给hiTail.next hiTail = e;//将e复制个hiTail } } while ((e = next) != null);//直到e为空 if (loTail != null) {//如果loTail不为空 loTail.next = null;//将loTail.next设置为空 newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处 } if (hiTail != null) {//如果hiTail不为空 hiTail.next = null;//将hiTail.next赋值为空 newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度] } } } } } return newTab; } /** * treeifyBin（）链表转为红黑树 */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();//为空或者容量小于MIN_TREEIFY_CAPACITY（默认64）则不进行转换，而是进行resize扩容 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do {//循环遍历链表，切换为红黑树 TreeNode<K,V> p = replacementTreeNode(e, null);//根据链表的node常见treenode if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } } /** * Copies all of the mappings from the specified map to this map. * These mappings will replace any mappings that this map had for * any of the keys currently in the specified map. * * @param m mappings to be stored in this map * @throws NullPointerException if the specified map is null */ public void putAll(Map<? extends K, ? extends V> m) { putMapEntries(m, true); } /** * 删除元素： */ public V remove(Object key) { //临时变量 Node<K,V> e; /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示， * 把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作 */ return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * 第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value， * 不删除key,第四个如果为false，则表示删除后，不移动节点 **/ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标 Node<K,V>[] tab; Node<K,V> p; int n, index; //哈希数组不为null，且长度大于0，然后获得到要删除key的节点所在是数组下标位置 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { //nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value Node<K,V> node = null, e; K k; V v; //如果数组下标的节点正好是要删除的节点，把值赋给临时变量node if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; //也就是要删除的节点，在链表或者红黑树上，先判断是否为红黑树的节点 else if ((e = p.next) != null) { if (p instanceof TreeNode) //遍历红黑树，找到该节点并返回 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { //表示为链表节点，一样的遍历找到该节点 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } /**注意，如果进入了链表中的遍历，那么此处的p不再是数组下标的节点，而是要删除结点的上一个结点**/ p = e; } while ((e = e.next) != null); } } //找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true 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); //如果是链表结构，且删除的节点为数组下标节点，也就是头结点，直接让下一个作为头 else if (node == p) tab[index] = node.next; else /**为链表结构，删除的节点在链表中，把要删除的下一个结点设为上一个结点的下一个节点**/ p.next = node.next; //修改计数器 ++modCount; //长度减一 --size; /**此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理**/ afterNodeRemoval(node); //返回删除的节点 return node; } } //返回null则表示没有该节点，删除失败 return null; } /** * Removes all of the mappings from this map. * The map will be empty after this call returns. */ public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } } /** * Returns {@code true} if this map maps one or more keys to the * specified value. * * @param value value whose presence in this map is to be tested * @return {@code true} if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (Node<K,V> e : tab) { for (; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; ................　　................　　................//后序代码不是太重要，不再分析 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import jdk.internal.misc.SharedSecrets;
/**
*
* 基于哈希表实现的{Map}接口。这个实现提供了所有可选的映射操作，并允许{ null}值
* 和{ null}键。({ HashMap}类大致相当于{ Hashtable}，只是它是不同步的，
* 并且允许为空。)该类不保证映射的顺序;
*
*
* <p>这个实现为基本操作({ get}和{ put})提供了常量时间性能，假设散列函数正确地将元素分散到各个桶中。
* 集合视图的迭代需要与{ HashMap}实例的“容量”(桶的数量)及其大小(键值映射的数量)成比例的时间。
* 因此，如果迭代性能很重要，那么不要将初始容量设置得太高(或负载因子过低)。
{ HashMap}的一个实例有两个影响其性能的参数:<i>初始容量</i>和<i>负载因子</i>。
<i>capacity</i>是哈希表中的桶数，初始容量就是建哈希表时的容量。
<i>load factor</i>是在哈希表的容量自动增加之前允许它获得的满值的度量。
当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表是<i>rehash </i>(即重新构建内部数据结构)，
因此哈希表的桶数大约是桶数的两倍。
*/
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/**
* 序列号
*/
private static final long serialVersionUID = 362498820763181265L;
/**
* 默认的初始容量，必须是2的整数次方
* 初始化状态长度是16。数组中每个元素我们这里称之为桶，
* 桶存储的是key的hash值，每个桶后面挂载着链表，
* 链表中存储的是具体的数据value。
*
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，如果大于这个值则使用这个值
* 必须是2的幂 <= 1<<30。
* MAXIMUM_CAPACITY为什么设置成1 << 30 ？
* MAXIMUM_CAPACITY含义是map的最大容量。
* 它是int类型，使用<<移位运算符的结果不能超过int可以表示的最大值。
* 固最大只能左移30，再大就溢出了。
*
* java中的int占4个字节，每个字节8位，所以总共是占用32位。int是有符号的，
* 其中第一位是符号位。所以还剩下31位。那么最多就是左移30了。
* 1 << 2 = 4(十进制) = 100(二进制)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子为 0.75，即：如果数组长度为16当有16*0.15=12个占满，则考虑扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表长度大于 8 时，转换为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 扩容时，如果发现树中节点数量小于6，则将树还原为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* map容器中某个箱子（bin）再有链表转为树之前还要满足键值对数量大于 64 才会发生转换。
* 目的是为了避免 resizing（扩容） 和 treeification（链表转树结构）之间的冲突
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Basic hash bin node, used for most entries.
(See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey()
{ return key; }
public final V getValue()
{ return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
/* ---------------- Static utilities -------------- */
/**
* 哈希算法：
*首先获取对象的hashCode()值，然后将hashCode值右移16位，
* 然后将右移后的值与原来的hashCode做异或运算，返回结果。
* （其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，
* 无论正数还是负数，都在高位插入0）。
*
*
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (Type t : ts) {
if ((t instanceof ParameterizedType) &&
((p = (ParameterizedType) t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/* ---------------- Fields -------------- */
/**
* 存储hash的数组，首次使用时初始化，长度总是2的幂次方
*/
transient Node<K,V>[] table;
/**
* 存放实际的键值对
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* HashMap中实际存在的键值对数量,注意和table的长度length、容纳最大键值对数量threshold的区别
*/
transient int size;
/**
* 用来记录HashMap内部结构发生变化的次数（计数器）
*/
transient int modCount;
/**
* 当前 HashMap 所能容纳键值对数量的最大值,超过这个,则需扩容
* @serial
*/
int threshold;
/**
* 负载因子
*
* @serial
*/
final float loadFactor;
/* ---------------- Public operations -------------- */
/**
* 构造函数
*/
/**
* （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或等于0，不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//初始化填充因子
this.loadFactor = loadFactor;
//初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
/**
* （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);
}
/**
* 说明：putMapEntries(Map<? extends K, ? extends V> m,
* boolean evict)函数将m的所有元素存入本HashMap实例中。
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取该map的实际长度
int s = m.size();
if (s > 0) {
//判断table是否已经初始化
if (table == null) { // pre-size
//未初始化，s 为 m 的实际元素个数
/**求出需要的容量，因为实际使用的长度=容量*0.75得来的，+1是因为小数相除，
* 基本都不会是整数，容量大小不能为小数的，后面转换为int，多余的小数就要
* 被丢掉，所以+1，例如，map实际长度22，22/0.75=29.3,所需要的容量肯定为30，
* 有人会问如果刚刚好除得整数呢，除得整数的话，容量大小多1也没什么影响**/
float ft = ((float)s / loadFactor) + 1.0F;
//判断该容量大小是否超出上限。
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//计算得到的t大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果已经初始化，并且m元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* Returns the number of key-value mappings in this map.
*
* @return the number of key-value mappings in this map
*/
public int size() {
return size;
}
/**
* Returns {@code true} if this map contains no key-value mappings.
*
* @return {@code true} if this map contains no key-value mappings
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Get方法：
* HashMap并没有直接提供getNode接口给用户调用，而是提供的get方法，
* 而get方法就是通过getNode来取得元素的。
* @see #put(Object, Object)
*/
/**
* HashMap的数据存储实现原理
*
* 流程：
*
* 1. 根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)；
*
* 2. 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)，这样就找到该key的存放位置了：
*
* ① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；
*
* ② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作；
*
* ③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样：
*
* 如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null；如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get 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) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//table已经初始化，长度大于0，根据hash寻找table中的项也不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//桶中第一项（数组元素）相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//桶中不止一个节点
if ((e = first.next) != null) {
//为红黑树节点
if (first instanceof TreeNode)
//在红黑树中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否则，在链表中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
/**
* Returns {@code true} if this map contains a mapping for the
* specified key.
*
* @param
key
The key whose presence in this map is to be tested
* @return {@code true} if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
*
{@code null} if there was no mapping for {@code key}.
*
(A {@code null} return can also indicate that the map
*
previously associated {@code null} with {@code key}.)
*/
public V put(K key, V value) {
//对key的hashCode()作再hash处理，目的是减少hash冲突的概率
/**四个参数，第一个hash值，第四个参数表示如果该key存在值，
* 如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用，
* 可以不用管，使用默认的即可
* **/
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*putVal()方法，插入操作：
*
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
//步骤一：tab为空则创建
//table未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//步骤二：计算index，并对null做处理
//(n -1) & hash 确定元素存放在哪个桶中，桶为空，新生成节点放入桶中（此时这个节点存放在数组中）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//桶中已经存在元素
/**
* 发生hash冲突的几种情况：
*/
else {
Node<K,V> e; K k;
/**
* 第一种，插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点
*/
//步骤三：节点key存在，直接覆盖value
//比较桶中第一个元素（数组中的节点）的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将第一个元素赋给e，用e来记录
e = p;
/**
* 第二种：hash值不等于首节点，不为红黑树的节点，则为链表的节点
*/
//步骤四：判断链表为红黑树
//hash值不相等，即key不相等：为红黑树
else if (p instanceof TreeNode)
//放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
/**
* 第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点
*/
//步骤五：该链为链表
//为链表节点
else {
//遍历该链表，在链表最末尾插入节点
for (int binCount = 0; ; ++binCount) {
//到达链表的尾部
if ((e = p.next) == null) {
//在尾部插入新节点
p.next = newNode(hash, key, value, null);
//节点数量达到阈值，转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);
//跳出循环
break;
}
//判断链表中节点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//相等，跳出循环
break;
//用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
//表示在桶中找到key值，hash值与插入元素相等的节点
if (e != null) { // existing mapping for key
//记录e的value
V oldValue = e.value;
//onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
//访问后回调

afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//结构性修改
++modCount;
//步骤六：超过最大容量，就扩容
//实际大小大于阈值则扩容
if (++size > threshold)
resize();
//插入后回调

afterNodeInsertion(evict);
return null;
}
/**
* 扩容：
* @return the table
*/
/**
* ①.1.8中resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
* ②.每次扩展的时候，都是扩展2倍；
* ③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
* @return
*/
final Node<K,V>[] resize() {
//oldTab指向hash桶数组
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果oldCap不为空的话，就是hash桶数组不为空
if (oldCap >= MAXIMUM_CAPACITY) {//如果数组容量大于最大容量，就赋值为整数最大的阈值，不再扩容
threshold = Integer.MAX_VALUE;
return oldTab;//返回

}
//如果当前hash桶数组的长度在扩容后仍然小于最大容量，并且oldCap大于默认值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//将当前数组扩大一倍
newThr = oldThr << 1; // double threshold 双倍扩容阈值

}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//设置新的阈值
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
table = newTab;//将新数组的值赋值给旧的hash桶数组
if (oldTab != null) {
//循环遍历老map中的所有数据，迁移到新数组中对应位置，进行扩容操作
//进行扩容操作，复制Node对象到新的hash桶数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j节点处不为空，复制给e
oldTab[j] = null;//将旧的hash桶数组在j节点处设置为空，方便gc
if (e.next == null)//如果e后面没有Node节点
newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得储存位置
else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中
((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;
Node<K,V> next;
do {
next = e.next;//将Node节点的next赋值给next
if ((e.hash & oldCap) == 0) {//如果节点e的hash值与原来hash桶数组的长度做与运算为0
if (loTail == null)//如果loTail为null
loHead = e;//将e节点赋值给loHead
else
loTail.next = e;//否则将赋值给loTail.next
loTail = e;//然后将e赋值给loTail

}
else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0
if (hiTail == null)//如果hiTail为null
hiHead = e;//将e赋值给hiHead
else
hiTail.next = e;//如果hiTail不为空，将e复制给hiTail.next
hiTail = e;//将e复制个hiTail

}
} while ((e = next) != null);//直到e为空
if (loTail != null) {//如果loTail不为空
loTail.next = null;//将loTail.next设置为空
newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处

}
if (hiTail != null) {//如果hiTail不为空
hiTail.next = null;//将hiTail.next赋值为空
newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度]

}
}
}
}
}
return newTab;
}
/**
* treeifyBin（）链表转为红黑树
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//为空或者容量小于MIN_TREEIFY_CAPACITY（默认64）则不进行转换，而是进行resize扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {//循环遍历链表，切换为红黑树
TreeNode<K,V> p = replacementTreeNode(e, null);//根据链表的node常见treenode
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
/**
* Copies all of the mappings from the specified map to this map.
* These mappings will replace any mappings that this map had for
* any of the keys currently in the specified map.
*
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
/**
* 删除元素：
*/
public V remove(Object key) {
//临时变量
Node<K,V> e;
/**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，
* 把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作
*/
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value，
* 不删除key,第四个如果为false，则表示删除后，不移动节点
**/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标
Node<K,V>[] tab; Node<K,V> p; int n, index;
//哈希数组不为null，且长度大于0，然后获得到要删除key的节点所在是数组下标位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value
Node<K,V> node = null, e; K k; V v;
//如果数组下标的节点正好是要删除的节点，把值赋给临时变量node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//也就是要删除的节点，在链表或者红黑树上，先判断是否为红黑树的节点
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//遍历红黑树，找到该节点并返回
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { //表示为链表节点，一样的遍历找到该节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
/**注意，如果进入了链表中的遍历，那么此处的p不再是数组下标的节点，而是要删除结点的上一个结点**/
p = e;
} while ((e = e.next) != null);
}
}
//找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true
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);
//如果是链表结构，且删除的节点为数组下标节点，也就是头结点，直接让下一个作为头
else if (node == p)
tab[index] = node.next;
else /**为链表结构，删除的节点在链表中，把要删除的下一个结点设为上一个结点的下一个节点**/
p.next = node.next;
//修改计数器
++modCount;
//长度减一
--size;
/**此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理**/
afterNodeRemoval(node);
//返回删除的节点
return node;
}
}
//返回null则表示没有该节点，删除失败
return null;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
/**
* Returns {@code true} if this map maps one or more keys to the
* specified value.
*
* @param value value whose presence in this map is to be tested
* @return {@code true} if this map maps one or more keys to the
*
specified value
*/
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (Node<K,V> e : tab) {
for (; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
................
　　................
　　................
//后序代码不是太重要，不再分析

}

四，参考链接：

https://www.cnblogs.com/xiaoxi/p/7233201.html

https://blog.csdn.net/liubenlong007/article/details/87937209

https://www.jianshu.com/p/19b62f510908

我的JDK代码仓库GitHub链接：

https://github.com/Tom-shushu/JDK-

由于我只分析Java相关夹包下的源代码所以我只保留了src的目录