HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题_hsahmap并发操作不同对象

本文基于Java7的源码做剖析

先看一下成员变量

  /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16,默认初始容量为16，必须为2的幂；
 
    /**
     * 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;//最大容量值，容量值必须为2的幂且小于该值；
 
    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认加载因子
 
    /**
     * An empty table instance to share when the table is not inflated.
     */
    static final Entry<?,?>[] EMPTY_TABLE = {};//空的Entry数组，未调整表容量前共享。
 
    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//必须重设容量的Entry数组表，长度必须为2的幂；
 
    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;//HashMap的大小，即Entry元素总量;
 
    /**
     * 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.
    int threshold;//临界值，如果表是空的，则该值作为空表膨胀的初始容量；
 
    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    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).
     */
    transient int modCount;//hashMap结构修改次数统计
 
    /**
     * 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.
     */
     // 默认备用哈希算法启用阈值，默认大小为Integer.MAX_VALUE,该变量被静态内部类Holder引用。
    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.
     */
     //哈希种子，用于降低key的hash碰撞概率，如果为0则禁用备用哈希算法；
    transient int hashSeed = 0;

先来看看put的几种分支

HashM ap源码分析

HashMap通过键的hashCode来快速的存取元素。当不同的对象hashCode发生碰撞时，HashMap通过单链表来解决，将新元素加入链表表头，通过next指向原有的元素。

先说说大概的过程：当我们调用put存值时，HashMap首先会获取key的哈希值，通过哈希值快速找到某个存放位置，这个位置可以被称之为bucketIndex。

对于一个key，如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为true。

所以理论上，hashCode可能存在冲突的情况，也叫发生了碰撞，当碰撞发生时，计算出的bucketIndex也是相同的，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是哈希码碰撞时才会执行的方法，所以说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值，如果不存在 ，则存放新的键值对<K, V>到bucketIndex位置。

1. //当key为null，调用putForNullKey方法，保存null于table第一个位置中，这是HashMap允许为null的原因
2. if (key == null)
3. return putForNullKey(value);
4. //计算key的hash值
5. int hash = hash(key.hashCode()); ------( 1)
6. //计算key hash 值在 table 数组中的位置
7. int i = indexFor(hash, table.length) ; ------(2)
8. //从i出开始迭代 e,找到 key 保存的位置
9. for (Entry<K, V> e = table[i]; e != null; e = e.next) {
10. Object k;
11. //判断该条链上是否有hash值相同的(key相同)
12. //若存在相同，则直接覆盖value，返回旧value
13. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
14. V oldValue = e.value; //旧值 = 新值
15. e.value = value;
16. e.recordAccess( this);
17. return oldValue; //返回旧值
18. }
19. }
20. //修改次数增加1
21. modCount++;
22. //将key、value添加至i位置处
23. addEntry(hash, key, value, i);
24. return null;
25. }

通过源码我们可以清晰看到HashMap保存数据的过程为：

1)首先判断key是否为null，若为null，则直接调用putForNullKey方法

从代码可以看出，如果key为null的值，默认就存储到table[0]开头的链表了。然后遍历table[0]的链表的每个节点Entry，如果发现其中存在节点Entry的key为null，就替换新的value，然后返回旧的value，如果没发现key等于null的节点Entry，就增加新的节点

2)计算key的hashcode（hash(key.hashCode())），再用计算的结果二次hash（indexFor(hash, table.length)），找到Entry数组的索引i，这里涉及到hash算法，最后会详细讲解

3)遍历以table[i]为头节点的链表，如果发现hash，key都相同的节点时，就替换为新的value，然后返回旧的value，只有hash相同时，循环内并没有做任何处理

4)modCount++代表修改次数，与迭代相关，在迭代篇会详细讲解

5)对于hash相同但key不相同的节点以及hash不相同的节点，就增加新的节点（addEntry()）

1. void addEntry(int hash, K key, V value, int bucketIndex) {
2. //获取bucketIndex处的Entry
3. Entry<K, V> e = table[bucketIndex];
4. //将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
5. table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
6. //若HashMap中元素的个数超过极限了，则容量扩大两倍
7. if (size++ >= threshold)
8. resize( 2 * table.length);
9. }

这里新增加节点采用了头插法，新节点都增加到头部，新节点的next指向老节点

这里涉及到了HashMap的扩容问题，随着HashMap中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响HashMap的速度，为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。

1. void resize(int newCapacity) {
2. HashMapEntry[] oldTable = table;
3. int oldCapacity = oldTable.length;
4. if (oldCapacity == MAXIMUM_CAPACITY) {
5. threshold = Integer.MAX_VALUE;
6. return;
7. }
9. HashMapEntry[] newTable = new HashMapEntry[newCapacity];
10. transfer(newTable);
11. table = newTable;
12. threshold = ( int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
13. }

从代码可以看出，如果大小超过最大容量就返回。否则就new 一个新的Entry数组，长度为旧的Entry数组长度的两倍。然后将旧的Entry[]复制到新的Entry[].

1. void transfer(HashMapEntry[] newTable) {
2. int newCapacity = newTable.length;
3. for (HashMapEntry<K,V> e : table) {
4. while( null != e) {
5. HashMapEntry<K,V> next = e.next;
6. int i = indexFor(e.hash, newCapacity);
7. e.next = newTable[i];
8. newTable[i] = e;
9. e = next;
10. }
11. }
12. }

在复制的时候数组的索引int i = indexFor(e.hash, newCapacity);重新参与计算

• 静态内部类Holder的源码：
  

/**
     * holds values which can't be initialized until after VM is booted.
     * 控制一些数据在VM启动之前不能初始化
     */
    private static class Holder {
 
        /**
         * Table capacity above which to switch to use alternative hashing.当表容量溢出时使用备用哈希算法。
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD;
 
        static {
        //获取系统变量jdk.map.althashing.threshold，获取备用哈希算法阈值，默认为-1
            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，则禁用备用哈希算法
                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;
        }
    }

很多文章讲到这里都是直接跳过，本人也是看得云里雾里，怎么莫名其妙的蹦出这么个东西，好像在源码中也没多大用处，没错，它是没多大用，至少对于目前的我们这种菜鸡来说，因为它涉及到了一种JDK1.7新加入的哈希算法：sun.misc.Hashing.stringHash32((String) k)，针对String类型的key，提供一个新的hash算法处理hashcode分布以减少冲突，这个算法是不稳定的，还在实验阶段，默认情况下是关闭的，要想启用这个新特性，需要手动设置jdk.map.althashing.threshold为非负数（默认为-1），这一点可以从Holder源码中看出。

这有另一个关于String类更新的介绍：一个新的哈希算法。Oracle声称这个新的哈希算法会提供更好的哈希码分布，这将会改善一些基于哈希码集合的性能：HashMap,Hashtable,HashSet,LinkedHashMap,LinkedHashSet,WeakHashMap和ConcurrentHashMap。不像文章开头所说的那个改变，这些改变是实验性的，默认是关闭的。

正如你所想那样，这些新特性只用于String类型的Key。如果你想启用这个特性，你可以将系统参数 jdk.map.althashing.threshold设置为非负数（默认为-1），这个值将会成为集合大小的阈值，新的哈希算法将会在超越阈值时使用。提醒一下：哈希算法的只会在重算hash时改变（当没有多余空间的时候）。所以，如果一个集合上一次rehash时的大小为160，而 jdk.map.althashing.threshold = 200，则新的哈希算法将会在集合大小到达320（大概）时启用。

是不是已经有点感觉了？新的hash算法的使用只有在rehash中才会用到，而这个Holder静态内部类，只是加载并初始化ALTERNATIVE_HASHING_THRESHOLD参数而已。

构造方法：

在这四个构造方法中，其他三个构造方法都共同调用了第三个构造方法：

//其他三种构造方法最后都指向了该构造方法
    public HashMap(int initialCapacity, float loadFactor) {
        //检查初始容量是否小于0，是则抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //检查初始容量是否大于默认最大容量值，是则重置为MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //检查加载因子是否合法
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        //指定加载因子
        this.loadFactor = loadFactor;
        //初始化阈值
        threshold = initialCapacity;
        //初始化函数，里面是空的，供子类调用
        init();
    }
 
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
 
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
 
    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);
    }

下面开始分析HashMap的几个常用方法的源码：

put方法

---

public V put(K key, V value) {
    //检查是否为空表，是则膨胀容量
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //检查key是否为null,这个很熟悉吧
        if (key == null)
            return putForNullKey(value);
        //计算key的hash值
        int hash = hash(key);
        //获取bucketIndex,即在table中存放的位置
        int i = indexFor(hash, table.length);
        //取出该索引下的Entry，遍历单链
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //检查hash码是否相同，key是否相等
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                //该key已存在，取出对应的value并转移
                V oldValue = e.value;
                //存入新的value
                e.value = value;
                //该方法内容为空，供子类重写所用
                e.recordAccess(this);
                //返回对应的旧value
                return oldValue;
            }
        }
        //记录表结构修改次数；到了这里证明，该table中并不存在该key，向表中增加Entry
        modCount++;
        //增加Entry
        addEntry(hash, key, value, i);
        //返回空值
        return null;
    }

从源码中我们可以看到，put方法进行了如下操作： 
1. HashMap是在put操作的时候才开始膨胀的； 
2. 然后判断输入的key是否为空值，如果为空则调用putForNullKey(V)设入空key（原理差不多，但需要注意，空Key都是放在table[0]里面的）； 
3. hash(key)获取哈希码； 
4. indexFor(hash, table.length)获取存放位置的索引； 
5. 遍历table[i]，检查是否存在，存在则覆盖并返回旧值； 
6. 不存在，准备修改表结构，先记录次数； 
7. 调用addEntry(hash, key, value, i)增加元素。

这里面涉及到几个函数，我们依次分析就明白了。

inflateTable :

---

    /**
     * Inflates the table.
     * 膨胀表容量
     */
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        //将指定的表容量toSize传入，获取大于或等于toSize的2的幂值
        int capacity = roundUpToPowerOf2(toSize);
        //获取下一次膨胀的阈值；
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //创建指定容量的新表
        table = new Entry[capacity];
        //初始化哈希种子作为备用
        initHashSeedAsNeeded(capacity);
    }

为了保证表容量为2的幂，必须将当初初始化threshold时指定的initialCapacity过滤一遍，那为什么一定要保证容量为2的幂呢？那就是资源浪费和效率的二选一了，而显然JDK开发人员选择了后者，后文分析到相关函数时再作介绍。下面是roundUpToPowerOf2(toSize)的源码：

roundUpToPowerOf2 :

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

先来理一下思路：

1. 判断number是否大于MAXIMUM_CAPACITY，是则返回MAXIMUM_CAPACITY，否则进入第二步；
2. 获取nubmer中的1出现的最高位（待会细讲）赋给rounded，若rounded等于零，返回1，否则进入第三步；
3. 获取number的1位出现的次数，若大于1，则rounded左移一位 （保证为2的幂），否则rounded为1，返回rounded； 
   
   因此不管结果如何，最后该函数返回的都是2的幂值。下面介绍第二步和第三步涉及到的Integer相关函数。

Integer

(已经了解了？直接跳过。)

---

highestOneBit (int)

//该函数实现获取指定int数的二进制数中1出现的最高位
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);
    }

WTF?!又见位运算，高大上啊有没有！但是有没有一脸懵逼的感觉？好吧，快告诉我不是只有我才这么无聊去研究这个是怎么实现的。先来个简单的4bit运算，假设有个数 i=0110,我们来最笨的方法一位一位的移动:

 

有没有看明白？它其实就是通过不断的右移，再与原数i做或运算，重复以上步骤，得到一个自1的最高位到最低位都是1的数，如上面的0111，然后再拿它来和它的右移1位(无符号右移)得到的值做减运算，从而得到我们最终想要的结果：自1的最高位之后的所有低位都是0的数，如上面的0100。而我们的int的长度始终都是4个字节，也就是32bit，所以上面要进行31位的右移操作。还有疑惑的话不妨动手试一试就明白了。

bitCount (int)

//该函数实现统计指定int数的二进制数中1出现的的次数。
    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

这又是什么鬼？简直丧心病狂！这里面用到了“分治”思想（如果不想看的也可以直接跳过本段），要统计32位数中1出现的次数，需要逐步分组并组内求和得到对应位的数，每次分组的位数加倍，以2位一组作为起始统计： 
 
先来分析一下第一行代码：i = i - ((i >>> 1) & 0x55555555); 
假设有个数 0xBC637EFF:1011 1100 0110 0011 0111 1110 1111 1111 
进行第一次分组运算，每2位一组： 

 

可以看出已经达到了我们想要的效果，那开发人员到底是怎么想到的呢？我也不知道[尴尬]，在这里我就说说我的理解吧。请结合上图理解下面分析

1. (i >>> 1)先将i无符号右移，则每2位中的高位移向低位，我们的目的是在这基础上再将每2位中的高位置0（此时的高位为原每2位中的低位）；
2. (i >>> 1)& 0x55555555：将每2位中的高位置0；

3. 此时将出现以下结果：

   　1011 1100 0110 0011 0111 1110 1111 1111 [i] 
   　0101 0100 0001 0001 0001 0101 0101 0101 [(i>>1)&0x55555555] 
   　 
   　对比之下不难发现，上一行减下一行刚好是原数中每2位中1出现的次数。我们拿出最高的2位出来比较就很明显了：

10 
01 ：此数的高位永远为0，而低位则是上一行的高位，上下两数之差必等于上一行中1出现的次数。

这其实等价于i = (i& 0x55555555) + ((i >>> 1) & 0x55555555)，这样更好理解，把原i和0x55555555相与过滤掉每2位中的高位，这样就只剩下低位了，而(i >>> 1) & 0x55555555又把高位移到了低位，两个数相加同样等于1出现的次数。理解了这个，后面就不难理解了吧，原理都是一样的。

下面了分析inflateTable(int)函数里面涉及到的第二个函数：

initHashSeedAsNeeded

    /**
     * Initialize the hashing mask value. We defer initialization until we
     * really need it.
     * 初始化哈希掩码值。我们延迟初始化它直到我们需要它的时候。
     */
    final boolean initHashSeedAsNeeded(int capacity) {
        //检查当前备用哈希算法状态，hashSeed初始值为0
        boolean currentAltHashing = hashSeed != 0;
        //检查是否需要启用备用哈希算法
        //一般情况下，capacity小于Holder.ALTERNATIVE_HASHING_THRESHOLD，因此该值为false
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        //进行异或判断，一般情况下为switching为false
        boolean switching = currentAltHashing ^ useAltHashing;
         //若switching=true,则进行以下操作
        if (switching) {
           //若useAltHashing=true，返回随机hashSeed,否则返回0；
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

这个方法用于决定是否启用新的hash算法，他被两个方法所调用：

• inflateTable(int toSize)
• resize(int newCapacity)

hash

    final int hash(Object k) {
        int h = hashSeed;
        //检测hash种子的状态，决定是否启用新的hash算法。
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        //使用旧的哈希算法
        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).
        //保证hashCode 不同的算法，看不懂就随缘啦，太凶残了
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

indexFor

    /**
     * Returns index for hash code h.
     * 返回该hashcode在table中对应的索引
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";保证表容量必须为2的幂。
        //hashcode在table中对应的索引
        return h & (length-1);
    }

这里就是需要保证容量必须为2的幂的原因，因为length为2的幂的话，length-1刚好就是索引范围：[0,length),形成左闭右开区间，而又恰巧每一个有效位都为1，例如：

Capacity=16 
则length=16， 二进制为0000 0000 0000 0000 0000 0000 0001 0000 
lenght-1 =15，二进制为0000 0000 0000 0000 0000 0000 0000 1111

那么通过h & (length-1)得到的就是key在表中的索引位置。h & (length-1)与h%length等价不等效，位运算的速度和效率是非常高的，这就是容量必须为2的幂的原因。

接下来就是遍历Entry单链了，这个应该很好理解，Entry是以单链的形式存在的，用于解决hash碰撞时的存放问题。最后就是addEntry()，向表中插入元素，内容拉的有点长，可以点下锚点跳至put源码整理一下思路，现在再去看应该一目了然了吧。接下来基本上没什么难度了，读懂源码的表面意思就ok。

addEntry

 void addEntry(int hash, K key, V value, int bucketIndex) {
 //检查存放元素的数量是否大于或等于阈值，该bucketIndex下的表位置是否不为空
        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);
    }

resize

（或者先看createEntry方法?）

//重新调整表容量
  void resize(int newCapacity) {
      //备份表数据
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //检查旧表的容量是否已是最大值，是则终止扩容直接返回
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //创建空的新表
        Entry[] newTable = new Entry[newCapacity];
        //转移表数据，第二个参数决定是否重算hash码
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //新表覆盖旧表
        table = newTable;
        //计算下一次调整的阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

transfer

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历table中的Entry
        for (Entry<K,V> e : table) {
            //遍历Entry单链
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //重新计算索引
                int i = indexFor(e.hash, newCapacity);
                //置空e.next。将table[i]的空引用赋值给e.next，此时Entry链表中只有一个e。
                //也就是这里，会触发多线程并发问题
                e.next = newTable[i];
                //将e放入新table[i]中；
                newTable[i] = e;
                //将next链表赋值给e，继续循环遍历。
                e = next;
            }
        }
    }

这里的后半部分可能比较难以理解，其实就是先把Entry从一个拖家带口的家庭里抽出来，单独放到新的table中的过程，目的就是想让表中的元素尽量单独存在于表中，而不是以多个单链的形式存在，从而提高HashMap的性能。画了个图助于理解，丑了点，凑合看吧。。。

多线程并发问题

那么这就牵扯到了多线程并发问题了，我在源码注释中也提到， e.next = 
newTable[i]，就是问题所在，这里将该索引下的Entry元素单链处理成单个元素，那么链表之后的元素就是null 
了，而恰巧你在此刻又进行了get操作，又很恰巧你的Entry元素在被处理掉的链表中，那么他get到的还是原table中的数据，自然也就拿不到数据了，就会报空指针异常。最后一句e 
= next也是，假如你get的元素恰巧是之前这个e，而此刻e又被next顶掉了，同样也会报空指针异常。

createEntry

(跳回resize源码)

    void createEntry(int hash, K key, V value, int bucketIndex) {
    //初始化索引为bucketIndex的表位置
        Entry<K,V> e = table[bucketIndex];
        //初始化Entry，可能会引发多线程并发问题
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        //元素加1
        size++;
    }

多线程并发问题

Entry是一个链表结构，如果在new Entry<>(hash, key, value, e)操作中，有两个线程同时在此刻拿到相同的e，那么这两个线程就会竞争作为e的链头的所有权，势必会有一个会被覆盖掉，而在你进行get操作想取被覆盖掉的entry，那自然也是取不到的，返回空值。

了解一下Entry的内部结构：

Entry

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        //体现了entry的链表特性
        Entry<K,V> next;
        int hash;
 
        /**
         * Creates new entry.
         * 将新new的entry插入到旧entry的链头
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
 
    //省略展示部分方法
 
    }

• 好了，到这里我们put方法所涉及到的所有操作都分析完了。下面来分析get方法。

get

    public V get(Object key) {
    //检测是否为空key
        if (key == null)
            return getForNullKey();
        //获取相应的Entry
        Entry<K,V> entry = getEntry(key);
        //检查entry是否为空，是则返回null；否则返回对应的value
        return null == entry ? null : entry.getValue();
    }

getEntry

final Entry<K,V> getEntry(Object key) {
        //检查表中元素数量
        if (size == 0) {
            return null;
        }
        //检测key是否为空，是则返回0；否则返回key的hash码
        int hash = (key == null) ? 0 : hash(key);
        //根据hash码和表长度获取索引，从table中取出entry
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //检测hash是否相同，key的内存地址是否相等，key是否为null，key的equals方法返回值是否为true（之所以要比较这个是因为可以通过重写equals实现两个不同内存地址的对象返回true值）。
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                //返回entry
                return e;
        }
        return null;
    }

总结

本文重在梳理HashMap内部实现原理，至于HashMap的多线程问题，可以通过以下方式解决：

• 在包含HashMap的方法中实现同步机制，效率太低
• 外部包装：Map<K,V> map = Collections.synchronizedMap(new HashMap<K,V>());
• HashTable，效率太低
• 使用JDK1.5中引进的Concurrent包下的ConcurrentHashMap，相对安全高效，建议使用。

写在最后

到这里HashMap的一些常用方法源码就分析完了，其中也提到了有关可能引发多线程并发问题的所在，摸清了这个数据结构，以后用起来也就胸有成竹了，当然，有兴趣的同学也可以尝试去写自己的Map结构，在这里就不再赘述了。相信如果已经理解了上面的内容，那么阅读HashMap的其他源码并不是什么难事，加油吧少年！