HashMap底层详解-003-resize、并发下的安全问题

2017-11-16 本文已影响19人 53b3f4658edc

微信公众号：JavaWeb架构师

HashMap扩容的时机是: 当前HashMap中存放的元素个数 > HashMap的当前总长度 * loadFactor（loadFactor默认值是0.75）时进行扩容，扩容之后的长度是当前长度的2倍（比如现在存放了 16 * 0.75 = 12个，再存放第十三个元素的时候，HashMap就会自动的扩容，扩展成 2 * 16 = 32个）。

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

    int s = m.size();
    float ft = ((float)s / loadFactor) + 1.0F;

当扩容之后，需要重新计算元素的位置，这是一个非常耗时的操作，所以我们最好能预设长度，比如我们有1000个元素，那么 new HashMap(1000)? 不！前面我们说过了，应该设置成2的幂，所以 new HashMap(1024)? 其实我们设置成1000也会被调整成1024的，但是这样就可以了吗？不！当元素超过 1024*0.75 = 768个的时候会进行自动扩容，所以我们应该是new HashMap(2048)。

微信公众号：JavaWeb架构师

1.新建Entry，长度是原长度的两倍

2.rehash，遍历原有的数组，把那些元素重新映射到新的数组上（参考咱们前面的公式，length变了，结果自然就变了）。

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