HashMap源码分析-JDK1.7

浅析JDK1.7 HashMap源码。

HashMap中几个重要的属性

/**
    * 默认初始化化容量,即16  
    */
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

   /**
    * 最大容量，即2的30次方  
    */
   static final int MAXIMUM_CAPACITY = 1 << 30;

   /**
    * 默认负载因子
    */
   static final float DEFAULT_LOAD_FACTOR = 0.75f;

   /**
    * 空数组，表示没有初始化之前的状态
    */
   static final Entry<?,?>[] EMPTY_TABLE = {};

   /**
    * 空的存储实体
    */
   transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

   /**
    * HashMap中Entry的数量
    */
   transient int size;

   /**
    * 阈值，当size大于threshold时会执行resize操作
    * threshold = capacity * loadFactor
    */
   int threshold;

   /**
    * 负载因子，默认是0.75
    */
   final float loadFactor;

   /**
    * HashMap结构上修改（比如put，remove等操作）的的次数，保证并发访问时，若HashMap内部结构发生变化，快速响应失败
    */
   transient int modCount;

   /**
    * 默认的threshold值，下文会具体讲到
    */
   static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
   
   /**
    * 哈希种子，与此实例关联的随机值，应用于键的哈希码以使哈希冲突更难找到
    * 如果为0，则禁用备用散列，同样在下文具体分析
    */
    transient int hashSeed = 0;

Entry

当实例化一个HashMap时，会创建一个长度为Capacity的Entry数组。在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。

Entry源码如下:

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

构造方法

HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity或loadFactor，会使用默认值。

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    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;
    // 在HashMap中没有实际实现
    init();
}

在常规构造器中，并没有马上为数组table分配内存空间（有一个入参为指定Map的构造器例外），事实上是在执行第一次put操作的时候才真正构建table数组。

put()

public V put(K key, V value) {
    // 如果table数组为空数组，创建存储实体
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    // 如果key为null，存储位置为table[0]，或table[0]的冲突链上
    if (key == null)
        return putForNullKey(value);
    // 对key的hashcode进一步计算，确保散列均匀
    int hash = hash(key);
    // 获取在table数组中的下标
    int i = indexFor(hash, table.length);
    // 如果出现对应key已存在，则覆盖
    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;
        }
    }

    // 如果key没出现过，则modCount++
    modCount++;
    // 添加entry
    addEntry(hash, key, value, i);
    return null;
}

建哈希表是在inflateTable()中实现的，我们来看一看：

private void inflateTable(int toSize) {
    // 比容量（capacity）大的2的次幂，作为哈希表的容量
    int capacity = roundUpToPowerOf2(toSize);

    // 计算新的扩容阈值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 分配空间
    table = new Entry[capacity];
    // 根据容量判断是否需要初始化hashSeed
    initHashSeedAsNeeded(capacity);
}

继续看下addEntry()源码：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容，新容量为旧容量的2倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    // 将新Entry放入HashMap的桶的对应位置
    createEntry(hash, key, value, bucketIndex);
}

使用头插法将Entry插入桶中：

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Alternative hashing和hashSeed

这里我要补充一下hashSeed这个属性，inflateTable()中最后还调用了一个initHashSeedAsNeeded()方法，该方法是用来依据容量决定是否需要初始化hashSeed。

在源码中有一个常量ALTERNATIVE_HASHING_THRESHOLD_DEFAULT，它是一个默认的阈值，当一个键值对的键是String类型时，且map的容量达到了这个阈值，就启用备用哈希(alternative hashing)。备用哈希可以减少String类型的key计算哈希码（更容易）发生哈希碰撞的发生率。该值可以通过定义系统属性jdk.map.althashing.threshold来指定。如果该值是1，表示强制总是使用备用哈希；如果是-1则表示禁用。

HashMap有一个静态内部类Holder,它的作用是在虚拟机启动后根据jdk.map.althashing.threshold和ALTERNATIVE_HASHING_THRESHOLD_DEFAULT初始化ALTERNATIVE_HASHING_THRESHOLD，相关代码如下：

/**
 * Holder维护着一些只有在虚拟机启动后才能初始化的值
 */
private static class Holder {

    /**
     * 触发启用备用哈希的哈希表容量阈值
     */
    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;

            // 如果参数值为-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;
    }
}

继续看inflateTable()中initHashSeedAsNeeded()这个方法，该方法是用来依据容量决定是否需要初始化hashSeed，hashSeed默认是0，如果初始化hashSeed。所以下面来看看这个方法：

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

final boolean initHashSeedAsNeeded(int capacity) {
    // 如果hashSeed != 0，表示当前正在使用备用哈希
    boolean currentAltHashing = hashSeed != 0;
    // 如果vm启动了且map的容量大于阈值，使用备用哈希
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    // 异或操作，如果两值同时为false，或同时为true，都算是false。
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        // 把hashSeed设置成随机值
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

从hashSeed变量的注释可以看出，哈希种子一个随机值，在计算key的哈希码时会用到这个种子，目的是为了进一步减少哈希碰撞。如果hashSeed=0表示禁用备用哈希。

而Holder中维护的ALTERNATIVE_HASHING_THRESHOLD是触发启用备用哈希的阈值，该值表示，如果容器的容量（注意是容量，不是实际大小）达到了该值，容器应该启用备用哈希。

Holder会尝试读取JVM启动时传入的参数-Djdk.map.althashing.threshold并赋值给ALTERNATIVE_HASHING_THRESHOLD。它的值有如下含义：

• ALTERNATIVE_HASHING_THRESHOLD = 1，总是使用备用哈希
• ALTERNATIVE_HASHING_THRESHOLD = -1，禁用备用哈希

在initHashSeedAsNeeded(int capacity)方法中，会判断如果容器的容量>=ALTERNATIVE_HASHING_THRESHOLD，就会生成一个随机的哈希种子hashSeed，该种子会在put方法调用过程中的hash()中使用到：

final int hash(Object k) {
    // 如果哈希种子是随机值，使用备用哈希
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

扩容

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 旧容量值已经到了最大容量值  
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 将阀值修改至最大整数 
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 新的Entry数组
    Entry[] newTable = new Entry[newCapacity];
    // 将旧数组的数据拷贝到新数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    // 修改阀值 
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

这个时候不得不提resize()中的核心方法transfer()：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;	// 新容量
    for (Entry<K,V> e : table) {	// 遍历所有桶
        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 = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

get()

public V get(Object key) {
    // 获取key为空的元素
    if (key == null)	
        return getForNullKey();
    // 依据key获取元素
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

获取key为空的值：

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    // key为null的元素存储在table的下标为0的位置
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

getEntry()相对简单，直接贴源码：

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

remove()

remove()也比较简单直接贴源码：

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

为什么JDK1.7 HashMap是线程不安全的？

在多线程环境下，HashMap主要会出现下面三种问题：

• 死循环
• 数据丢失
• 数据覆盖

死循环和数据丢失

死循环问题出现在resize()中的核心方法transfer()中：

e.next = newTable[i];
newTable[i] = e;
e = next;

头插法会将链表的顺序翻转，这也是形成死循环的关键点。

假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作：

HashMap01

正常扩容后的结果是下面这样的：

HashMap02

但如果线程A在e.next = newTable[i];处CPU时间片耗尽，线程A被挂起，此时线程A中：e=3、next=7、e.next=null即：

HashMap03

当线程A的时间片耗尽后，CPU开始执行线程B，并在线程B中成功的完成了数据拷贝，此时线程B中7.next=3、3.next=null，即：

HashMap02

随后线程A获得CPU时间片继续执行，将3放入新数组对应的位置，执行完此轮循环后线程A的情况如下：

HashMap04

接着继续执行下一轮循环，此时e=7，从主内存中读取e.next时发现主内存中7.next=3，于是乎next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环，结果如下：

HashMap05

执行下一次循环可以发现，next=3.next=null，所以此轮循环将会是最后一轮循环。接下来当执行完e.next=newTable[i]即3.next=7后，3和7之间就相互连接了，当执行完newTable[i]=e后，3被头插法重新插入到链表中，执行结果如下图所示：

HashMap06

此时next=null，将不会进行下一轮循环。到此线程A、B的扩容操作完成，很明显当线程A执行完后，HashMap中出现了环形结构，当在以后对该HashMap进行操作时会出现死循环。

并且从上图可以发现，元素5在扩容期间被莫名的丢失了，这就发生了数据丢失的问题。

数据覆盖

还是在put()中：
比如有两个线程A和B，首先A希望插入一个元素到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头，这就导致了线程B插入的数据被线程A覆盖了。

参考：
Alternative hashing和hashSeed部分 https://segmentfault.com/a/1190000018520768