天天看点

HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题

先看一下 HashMap数据结构其中Entry为HashMap的内部类,它包含了键key、值value、下一个节点next,以及hash值,这是非常重要的,正是由于Entry才构成了table数组的项为链表

HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题

我们知道在 Java 中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现。数组的存储方式在内存的地址是连续的,大小固定,一旦分配不能被其他引用占用。它的特点是查询快,时间复杂度是O(1),插入和删除的操作比较慢,时间复杂度是O(n),链表的存储方式是非连续的,大小不固定,特点与数组相反,插入和删除快,查询速度慢。HashMap可以说是一种折中的方案吧。

本文基于Java7的源码做剖析

先看一下成员变量

/**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY =  << ; // 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 =  << ;//最大容量值,容量值必须为2的幂且小于该值;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = f;//默认加载因子

    /**
     * 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 = ;
           

先来看看put的几种分支

HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题

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()); ------( )
  6. //计算key hash 值在 table 数组中的位置
  7. int i = indexFor(hash, table.length) ; ------()
  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( * 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. }
  8. HashMapEntry[] newTable = new HashMapEntry[newCapacity];
  9. transfer(newTable);
  10. table = newTable;
  11. threshold = ( int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
  12. }

从代码可以看出,如果大小超过最大容量就返回。否则就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 == -) {
                    threshold = Integer.MAX_VALUE;
                }

                if (threshold < ) {
                    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

参数而已。

构造方法:

Constructor and Description

HashMap()

Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75). 构造一个空的HashMap,默认初始容量为16,默认加载因子为0.75。

HashMap(int initialCapacity)

Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).构造一个空的HashMap,指定初始容量,默认加载因子为0.75。

HashMap(int initialCapacity, float loadFactor)

Constructs an empty HashMap with the specified initial capacity and load factor.构造一个空的HashMap,指定初始容量和加载因子。

HashMap(Map<? extends K,? extends V> m)

Constructs a new HashMap with the same mappings as the specified Map.构造一个映射关系与指定 Map 相同的 HashMap。

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

//其他三种构造方法最后都指向了该构造方法
    public HashMap(int initialCapacity, float loadFactor) {
        //检查初始容量是否小于0,是则抛出异常
        if (initialCapacity < )
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //检查初始容量是否大于默认最大容量值,是则重置为MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //检查加载因子是否合法
        if (loadFactor <=  || 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) + ,
                      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 + );
        //创建指定容量的新表
        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)) != 
                    ? (Integer.bitCount(number) > ) ? rounded <<  : rounded
                    : ;

        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 >>  );
        i |= (i >>  );
        i |= (i >>  );
        i |= (i >>  );
        i |= (i >> );
        return i - (i >>> );
    }
           

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

HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题

有没有看明白?它其实就是通过不断的右移,再与原数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 >>> ) & );
        i = (i & ) + ((i >>> ) & );
        i = (i + (i >>> )) & ;
        i = i + (i >>> );
        i = i + (i >>> );
        return i & ;
    }
           

这又是什么鬼?简直丧心病狂!这里面用到了“分治”思想(如果不想看的也可以直接跳过本段),要统计32位数中1出现的次数,需要逐步分组并组内求和得到对应位的数,每次分组的位数加倍,以2位一组作为起始统计: 

HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题

先来分析一下第一行代码:i = i - ((i >>> 1) & 0x55555555); 

假设有个数 0xBC637EFF:1011 1100 0110 0011 0111 1110 1111 1111 

进行第一次分组运算,每2位一组: 

HashMap详解、源码、扩容、深入理解HashMap、HashMap多线程并发问题

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

  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 != ;
        //检查是否需要启用备用哈希算法
        //一般情况下,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)
                : ;
        }
        return switching;
    }
           

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

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

hash

final int hash(Object k) {
        int h = hashSeed;
        //检测hash种子的状态,决定是否启用新的hash算法。
        if ( != 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 >>> ) ^ (h >>> );
        return h ^ (h >>> ) ^ (h >>> );
    }
           

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-);
    }
           

这里就是需要保证容量必须为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( * table.length);
            hash = (null != key) ? hash(key) : ;
            //重新计算索引
            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 + );
    }
           

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 ?  : 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的性能。画了个图助于理解,丑了点,凑合看吧。。。

HashMap详解、源码、扩容、深入理解HashMap、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 == ) {
            return null;
        }
        //检测key是否为空,是则返回0;否则返回key的hash码
        int hash = (key == null) ?  : 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的其他源码并不是什么难事,加油吧少年!