Java HashMap底层实现和原理分析(二)

我不是女神ヾ 2023-02-23 05:13 104阅读 0赞

### 文章目录 ###

*   *  HashMap集合底层的数据结构
     *  HashMap继承关系
     *  JDK1.7 HashMap源码分析
     *   *  成员变量
         *  构造方法
         *  \`put()\`方法
         *   *  \`inflateTable(threshold)\`方法
             *  \`putForNullKey(value)\`方法
             *  \`hash(key)\`方法
             *  \`indexFor(int h, int length)\`方法
             *  \`addEntry(int hash, K key, V value, int bucketIndex)\`方法
             *   *  \`createEntry(int hash, K key, V value, int bucketIndex)\`方法
                 *  \`resize(int newCapacity)\`方法
                 *  \`transfer(Entry\[\] newTable, boolean rehash)\`方法
     *  参考

## HashMap集合底层的数据结构 ##

在JDK1.8 之前 HashMap 由 **数组+链表** 数据结构组成的。

在JDK1.8 之后 HashMap 由 **数组+链表 +红黑树**数据结构组成的。

## HashMap继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nja2V2aW5jeWg_size_16_color_FFFFFF_t_70]

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
            //...
        }

说明：

*  Cloneable 空接口，表示可以克隆。 创建并返回HashMap对象的一个副本。
 *  Serializable 序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化。
 *  AbstractMap 父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。

补充：通过上述继承关系我们发现一个很奇怪的现象， 就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样在ArrayList中LinkedList中都是这种结构。

public abstract class AbstractMap<K,V> implements Map<K,V> { 
        //...
    }

> 据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

## JDK1.7 HashMap源码分析 ##

先简单看看它定义的一些成员变量

### 成员变量 ###

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
    { 
    
        /** * The default initial capacity - MUST be a power of two. */
         //定义默认的初始容量为16，必须是2的幂次方(面试常问,之前上一篇博文已经分析过为啥一定是2的幂次方)
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
         //最大的容量
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /** * The load factor used when none specified in constructor. */
         // 定义默认的负载因子是0.75
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /** * An empty table instance to share when the table is not inflated. */
         //定义了一个空的table
        static final Entry<?,?>[] EMPTY_TABLE = { };
    
        /** * The table, resized as necessary. Length MUST Always be a power of two. */
         //定义了一个table(桶或者数组)，其长度必须是2的幂次方，也就是哈希表，存储元素的数组 
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
        
        
    
        /** * The number of key-value mappings contained in this map. */
        //存放元素的个数，注意这个不等于数组的长度
        transient int size;
    
        /** * The next size value at which to resize (capacity * load factor). * @serial */
        // If table == EMPTY_TABLE then this is the initial capacity at which the
        // table will be created when inflated.
        // 扩容的阈值 = capacity * 负载因子
        int threshold;
    
        /** * The load factor for the hash table. * * @serial */
         //负载因子，默认是0.75，可以在创建HashMap时候通过构造函数指定
        final float loadFactor;
        
        
        /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
        // 每次扩容和更改map结构的计数器
        transient int modCount;
    
        /** * The default threshold of map capacity above which alternative hashing is * used for String keys. Alternative hashing reduces the incidence of * collisions due to weak hash code calculation for String keys. * <p/> * This value may be overridden by defining the system property * {@code jdk.map.althashing.threshold}. A property value of {@code 1} * forces alternative hashing to be used at all times whereas * {@code -1} value ensures that alternative hashing is never used. */
        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
        
         /** * A randomizing value associated with this instance that is applied to * hash code of keys to make hash collisions harder to find. If 0 then * alternative hashing is disabled. */
        transient int hashSeed = 0;
        //.... 
    }

### 构造方法 ###

我们先来看看HashMap的几个构造方法

![在这里插入图片描述][20200705163710507.png]

*  无参构造方法

/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */
        public HashMap() { 
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }

*  带一个int类型参数的构造方法(指定初始容量)

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */
        public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

*  带两个参数的构造方法(指定初始容量和负载因子)

*  带一个Map类型参数的构造方法

/** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */
        public HashMap(Map<? extends K, ? extends V> m) { 
            this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                          DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
            inflateTable(threshold);
    
            putAllForCreate(m);
        }

我们可以看到这几个构造方法其实都是用到了带两个参数的构造方法来进行初始化的。

那我们先来研究下这个带两个参数的构造方法里面做了些什么？

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
        public HashMap(int initialCapacity, float loadFactor) { 
            //判断初始容量是否小于0，初始容量不能小于0
            if (initialCapacity < 0)
                //如果小于0，则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            //判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY->2的30次幂 
            if (initialCapacity > MAXIMUM_CAPACITY)
                 //如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
                initialCapacity = MAXIMUM_CAPACITY;
            //判断负载因子loadFactor是否小于等于0或者是否是一个非数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                //如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            //将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
            this.loadFactor = loadFactor;
            //阈值设置为初始容量，但是在成员变量的注释中写着阈值应该(capacity * load factor),那么这里的设置是不是存在问题？我们先保留我们的疑问继续往下看
            threshold = initialCapacity;
            //调用init方法
            init();
        }

接下来我们来看看HashMap的`init()`方法

/** * Initialization hook for subclasses. This method is called * in all constructors and pseudo-constructors (clone, readObject) * after HashMap has been initialized but before any entries have * been inserted. (In the absence of this method, readObject would * require explicit knowledge of subclasses.) */
        void init() { 
        }

### `put()`方法 ###

接下来我们带着我们的疑问，也就是threshold的赋值问题来看看HashMap的`put()`方法

我们来看看HashMap的put方法中做了什么？

#### `inflateTable(threshold)`方法 ####

我们看看`inflateTable(threshold)`方法做了什么？

/** * Inflates the table. */
        private void inflateTable(int toSize) { 
            // Find a power of 2 >= toSize
            //这个方法很简单啦，看名字就知道是把table的容量设置为大于传入的初始容量的最小2的幂次方的整数
            int capacity = roundUpToPowerOf2(toSize);
            //注意这里我们又重新给threshold进行赋值了，可以看到这次的赋值就是(capacity * loadFactor)
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            //然后在这里我们给table进行初始化了，创建了一个长度为capacity的数组
            table = new Entry[capacity];
            //判断是否需要重新Hash，该方法是用来依据容量决定是否需要初始化hashSeed，hashSeed默认是0，如果初始化hashSeed，它的值将会是一个随机值。
            initHashSeedAsNeeded(capacity);
        }

所以我们这里可以知道，threshold在`put()`方法的时候进行了重新赋值，赋值为`(capacity * loadFactor)`,然后在new HashMap的时候并没有初始化table，而是在put方法中才进行初始化长度为capacity的table

private static int roundUpToPowerOf2(int number) { 
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }

这个方法就很眼熟啦，上一篇博文已经分析过jdk1.8的实现，都是一样的，其实就是把传进来的初始容量变成一个大于初始容量的最小2的幂次方的整数

/** * Returns an {@code int} value with at most a single one-bit, in the * position of the highest-order ("leftmost") one-bit in the specified * {@code int} value. Returns zero if the specified value has no * one-bits in its two's complement binary representation, that is, if it * is equal to zero. * * @return an {@code int} value with a single one-bit, in the position * of the highest-order one-bit in the specified value, or zero if * the specified value is itself equal to zero. * @since 1.5 */
        public static int highestOneBit(int i) { 
            // HD, Figure 3-1
            i |= (i >>  1);
            i |= (i >>  2);
            i |= (i >>  4);
            i |= (i >>  8);
            i |= (i >> 16);
            return i - (i >>> 1);
        }

最后我们来看看`initHashSeedAsNeeded(capacity)`方法

/** * Initialize the hashing mask value. We defer initialization until we * really need it. */
        final boolean initHashSeedAsNeeded(int capacity) { 
           // hashSeed 降低hash碰撞的hash种子，初始值为0
            boolean currentAltHashing = hashSeed != 0;
             //ALTERNATIVE_HASHING_THRESHOLD： 当map的capacity容量大于这个值的时候并满足其他条件时候进行重新hash
            boolean useAltHashing = sun.misc.VM.isBooted() &&
                    (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
            //异或操作，二者满足一个条件即可rehash 
            boolean switching = currentAltHashing ^ useAltHashing;
            if (switching) { 
             // 更新hashseed的值, 把hashSeed设置成随机值
                hashSeed = useAltHashing
                    ? sun.misc.Hashing.randomHashSeed(this)
                    : 0;
            }
            return switching;
        }

从上图代码可以看到，hashSeed的计算流程涉及到一个设定值`Holder.ALTERNATIVE_HASHING_THRESHOLD`，该设定值是通过JVM的参数`jdk.map.althashing.threshold`来设置的，如下代码。

/** * holds values which can't be initialized until after VM is booted. */
        private static class Holder { 
    
            /** * Table capacity above which to switch to use alternative hashing. */
            static final int ALTERNATIVE_HASHING_THRESHOLD;
    
            static { 
                // 读取JVM参数 -Djdk.map.althashing.threshold
                String altThreshold = java.security.AccessController.doPrivileged(
                    new sun.security.action.GetPropertyAction(
                        "jdk.map.althashing.threshold"));
    
                int threshold;
                try { 
                     // 如果该参数没有值，采用默认值
                    threshold = (null != altThreshold)
                            ? Integer.parseInt(altThreshold)
                            : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
    
                    // disable alternative hashing if -1
                    // 如果参数值为-1，禁用备用哈希
                    // ALTERNATIVE_HASHING_THRESHOLD_DEFAULT也是等于Integer.MAX_VALUE
                    // 所以jdk默认是禁用备用哈希的
                    if (threshold == -1) { 
                        threshold = Integer.MAX_VALUE;
                    }
    
                    if (threshold < 0) { 
                        throw new IllegalArgumentException("value must be positive integer.");
                    }
                } catch(IllegalArgumentException failed) { 
                    throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
                }
    
                ALTERNATIVE_HASHING_THRESHOLD = threshold;
            }
        }

所以hashSeed会在capacity容量发生变化的时候调用initHashSeedAsNeeded方法重新计算hashSeed的值

> 注：  
> 在JDK 8 中，hashSeed已经被移除掉了，移除掉的原因是调用sun.misc.Hashing.randomHashSeed计算hashSeed时会调用方法java.util.Random.nextInt()，该方法使用AtomicLong，在多线程情况下会有性能问题。

那么这个hashSessd的成员变量的作用是什么呢？它的作用就像是一个开关，我们看看后面的代码就知道了。

然后我们继续来看`put()`方法，我们前面已经看完了`inflateTable(threshold)`方法

/** * 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 <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */
        public V put(K key, V value) { 
            //判断当前的table(桶或者是数组)是否是空的
            if (table == EMPTY_TABLE) { 
                //如果是空的，那么就根据threshold来扩容(膨胀table)，记住这里传进入的是threshold,在构造方法中被赋值为了初始容量，所以相当传进入的是初始容量
                inflateTable(threshold);
            }
            //如果key为空
            if (key == null)
                //key为空 调用putForNullKey
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

#### `putForNullKey(value)`方法 ####

下面我们来看看`putForNullKey(value)`方法是怎么处理key为null的情况

/** * Offloaded version of put for null keys */
        private V putForNullKey(V value) { 
            //找到table的第一个位置，然后遍历链表
            for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
                //如果已经存在key为null
                if (e.key == null) { 
                    //用新值替换旧值
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            //修改记录次数
            modCount++;
            //如果不存在key为null的情况，则添加一个Entry
            addEntry(0, null, value, 0);
            return null;
        }

关于`addEntry`方法我们后面一点再讲，这里我们就理解为添加一个链表节点

然后我们继续看`put()`方法,前面看到了key为null的情况了，下面看看当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 <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */
        public V put(K key, V value) { 
            //判断当前的table(桶或者是数组)是否是空的
            if (table == EMPTY_TABLE) { 
                //如果是空的，那么就根据threshold来扩容(膨胀table)，记住这里传进入的是threshold,在构造方法中被赋值为了初始容量，所以相当传进入的是初始容量
                inflateTable(threshold);
            }
            //如果key为空
            if (key == null)
                //key为空 调用putForNullKey
                return putForNullKey(value);
            //如果key不为null的情况，首先根据key计算hash值
            int hash = hash(key);
            //然后根据hash值算出在tabke中的具体位置，其实相当于一个取模的操作，计算出数组下标
            int i = indexFor(hash, table.length);
            //这里就是找到指定下标的数组位置，遍历这个位置的链表
            for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
                Object k;
                // 这里就是通过判断对象的hashCode是否相同还有equals方法是否相等
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                     //如果对象的hashCode()还有equals()方法都相等，那就用新值替换旧值
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            //如果找不到已存在的key,那就修改记录次数
            modCount++;
            //添加一个新的key和value节点
            addEntry(hash, key, value, i);
            return null;
        }

下面我们来讲一下`hash(key)`方法还有`indexFor(hash, table.length)`方法

#### `hash(key)`方法 ####

其实这个方法就是通过key拿到它的hashCode的值，然后再做一系列的扰乱计算，以获得更好的散列值。

/** * Retrieve object hash code and applies a supplemental hash function to the * result hash, which defends against poor quality hash functions. This is * critical because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */
         //获取key的哈希码，并应用一个补充的哈希函数，构成最终的哈希码
        final int hash(Object k) { 
            //这里就用到了hashSeed这个开关了
            //方法调用链：inflateTable()-->initHashSeedAsNeeded()-->hash()
            int h = hashSeed;
            //当key的类型是String 并且hashSeed = 1的时候
            if (0 != h && k instanceof String) { 
                //使用stringHash32方法对key进行hash计算
                return sun.misc.Hashing.stringHash32((String) k);
            }
            //拿到key对象的hashCode
            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);
        }

那为什么中间特别需要对key为String类型的做一个特殊的hash计算呢，原因就是因为Tomcat的CVE-2011-4858漏洞。

参考：[http://mail-archives.apache.org/mod\_mbox/tomcat-announce/201112.mbox/%3C4EFB9800.5010106%40apache.org%3E][http_mail-archives.apache.org_mod_mbox_tomcat-announce_201112.mbox_3C4EFB9800.5010106_40apache.org_3E]

这个漏洞利用的原理就是hash碰撞，我们知道当hash碰撞的时候就会产生链表，我们知道链表查找的复杂度是O(n)

Tomact对于请求的参数比如`http://localhost/test?a=xxx&b=xxxx`对于后面的参数a和b使用HashMap来存储的，然后就可以构造好多个容易产生hash碰撞的参数去攻击Tomact服务器。

对于String的hashCode的方法如下：

/** * Returns a hash code for this string. The hash code for a * <code>String</code> object is computed as * <blockquote><pre> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] * </pre></blockquote> * using <code>int</code> arithmetic, where <code>s[i]</code> is the * <i>i</i>th character of the string, <code>n</code> is the length of * the string, and <code>^</code> indicates exponentiation. * (The hash value of the empty string is zero.) * * @return a hash code value for this object. */
        public int hashCode() { 
            int h = hash;
            if (h == 0 && value.length > 0) { 
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) { 
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }

下面的代码，我们就可以看出我们可以很容易的就写出几个会发生hash碰撞的String字符串

class Test{ 
        public static void main(String[] args) { 
            HashMap<String, String> hashMap = new HashMap<>();
            List<String> list = Arrays.asList("Aa", "BB", "C#");
            for (String s : list) { 
                System.out.println(s.hashCode());
                hashMap.put(s, s);
            }
            System.out.println(hashMap.size());
        }
    }

运行的结果如下：

2112
    2112
    2112
    3
    
    Process finished with exit code 0

可以看出来很容易就会发生hash碰撞。所以Oracle为了修复这一问题，对于String类型的就不用`hashCode()`来计算hash，而是使用`sun.misc.Hashing.stringHash32((String) k)`来计算hash值,这样就可以避免太多的hash碰撞。所以前面说的这个成员变量hashSeed，其实就是为了修复这个问题，而做的一个开关。

#### `indexFor(int h, int length)`方法 ####

这个方法就不多说了，其实相当于取模运算，上一篇博文也有说到，这个方法也跟为什么容量要设计成２的ｎ次幂有关。

/** * Returns index for hash code h. */
        static int indexFor(int h, int length) { 
            // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
            return h & (length-1);
        }

#### `addEntry(int hash, K key, V value, int bucketIndex)`方法 ####

接下来我们来看看addEntry方法

/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */
        void addEntry(int hash, K key, V value, int bucketIndex) { 
             // 如果容器大小大于等于阈值，且目标桶的entry不等于null
            if ((size >= threshold) && (null != table[bucketIndex])) { 
                //用当前容量的2倍进行扩容
                resize(2 * table.length);
                //扩容后重新计算哈希码
                hash = (null != key) ? hash(key) : 0;
                //并根据新哈希码和新数组长度重新计算存储位置
                bucketIndex = indexFor(hash, table.length);
            }
            //新增一个Entry
            createEntry(hash, key, value, bucketIndex);
        }

##### `createEntry(int hash, K key, V value, int bucketIndex)`方法 #####

我们先跳过扩容的部分，先看看`createEntry`的方法。 `createEntry`一般用在 新增Entry不会导致HashMap的实际容量超过阈值的情况下。因为在前面已经判断过并且有扩容的操作了。

我们来看代码：

/** * Like addEntry except that this version is used when creating entries * as part of Map construction or "pseudo-construction" (cloning, * deserialization). This version needn't worry about resizing the table. * * Subclass overrides this to alter the behavior of HashMap(Map), * clone, and readObject. */
        void createEntry(int hash, K key, V value, int bucketIndex) { 
            //这个bucketIndex是之前用key的哈希值做过位运算之后再去找数组运算得到的下标
            //取到数组上这个下标的元素，拿到链表的头结点
            Entry<K,V> e = table[bucketIndex];
            //然后创建了一个Entry，把上面的元素传进去了，也就是把这个创建出来的元素往链表里挂
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            //HashMap的容量大小+1
            size++;
        }

然后我们来看看Entry的构造方法，我们可以看到Entry的结构很明显就是一个链表的结点

static class Entry<K,V> implements Map.Entry<K,V> { 
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
    
            /** * Creates new entry. */
            Entry(int h, K k, V v, Entry<K,V> n) { 
                value = v;
                //头结点的next指向我们新创建的Entry元素，所以很明显这里是链表的头插法
                next = n;
                key = k;
                hash = h;
            }
            
            //....
            
        }

所以我们知道了jdk1.7对于hash碰撞时候，产生链表的时候是使用头插法进行插入的。

为什么会采用头插法，据说是考虑到热点数据的原因，即最近插入的元素也很可能最近会被使用到。所以为了缩短链表查找元素的时间，所以每次都会将新插入的元素放到表头。

而且使用头插法不像尾插法一样需要遍历链表找到链表的尾结点，效率是比较高的。

##### `resize(int newCapacity)`方法 #####

下面我们来看看扩容的方法，也是`resize(int newCapacity)`方法

/** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */
        void resize(int newCapacity) { 
            //首先缓存旧的哈希表数据
            Entry[] oldTable = table;
            //记录旧的哈希表的长度
            int oldCapacity = oldTable.length;
            //如果旧的哈希表的长度等于MAXIMUM_CAPACITY
            //也就是扩容前的数组大小如果已经达到最大(2^30)了
            if (oldCapacity == MAXIMUM_CAPACITY) { 
                //修改阈值为int的最大值，这样以后就不会扩容了
                //因为hashmap的size是不会大于这个threshold了
                threshold = Integer.MAX_VALUE;
                return;
            }
            //初始化一个新的Entry数组，这个newCapacity是原table容量的2倍
            Entry[] newTable = new Entry[newCapacity];
            //将数据转移到新的Entry数组里
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            //HashMap的table属性引用新的Entry数组
            table = newTable;
            //重新计算阈值
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }

##### `transfer(Entry[] newTable, boolean rehash)`方法 #####

下面我们来看看这个`transfer`方法，传入的是一个新的table还有一个是否需要重新hash的标志位。其实作用就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

/** * Transfers all entries from current table to newTable. */
        void transfer(Entry[] newTable, boolean rehash) { 
            //记录新数组的长度
            int newCapacity = newTable.length;
            //循环旧的数组
            for (Entry<K,V> e : table) { 
                //如果数组的元素不为null,则开始遍历链表
                while(null != e) { 
                    Entry<K,V> next = e.next;
                    //如果需要rehash
                    if (rehash) { 
                        //重新计算hash值
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    //根据hash值计算出数组下标
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    //把元素放到新的数组对应的下标位置中
                    newTable[i] = e;
                    e = next;
                }
            }
        }

值得注意的是：

> 在多线程环境下，有可能多条线程都调用transfer，而transfer方法中访问了一个全局变量table，并修改下标中指向的Entry。由于转移过程会导致链表逆序，就有可能出现闭环的引用。

## 参考 ##

[Java中的HashMap][Java_HashMap]

[理解HashMap][HashMap]

[HashMap在JDK1.7版本头插法实现解析][HashMap_JDK1.7]

[Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例][Java _10_ HashMap]

[Java集合——HashMap（四）扩容机制——resize（）][Java_HashMap_resize]

[疫苗：JAVA HASHMAP的死循环][JAVA HASHMAP]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nja2V2aW5jeWg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200705163644769.bmp?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nja2V2aW5jeWg=,size_16,color_FFFFFF,t_70
[20200705163710507.png]: https://img-blog.csdnimg.cn/20200705163710507.png
[http_mail-archives.apache.org_mod_mbox_tomcat-announce_201112.mbox_3C4EFB9800.5010106_40apache.org_3E]: http://mail-archives.apache.org/mod_mbox/tomcat-announce/201112.mbox/%3C4EFB9800.5010106@apache.org%3E
[Java_HashMap]: https://www.jianshu.com/p/a11b9c1002f1?from=singlemessage
[HashMap]: https://segmentfault.com/a/1190000018520768
[HashMap_JDK1.7]: https://blog.csdn.net/insomsia/article/details/88367436
[Java _10_ HashMap]: https://wangkuiwu.github.io/2012/02/10/collection-10-hashmap/
[Java_HashMap_resize]: https://blog.csdn.net/u012961566/article/details/72963157
[JAVA HASHMAP]: https://coolshell.cn/articles/9606.html