HashMap ConcurrentHashMap1.7和1.8

HashMap1.7

初始化



put



创建新的Entry


get


扩容机制

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容，容量 * 2
        resize(2 * table.length);
        // 扩容以后，重新计算 hash 值
        hash = (null != key) ? hash(key) : 0;
        // 重新计算扩容后的新的下标
        bucketIndex = indexFor(hash, table.length);
    }
    // 创建元素
    createEntry(hash, key, value, bucketIndex);

}

那么size为16的hashMap最多到底能塞多少个元素？

hashmap是数组+链表的结构

利用扩容条件，我们可以

/**

 * Inflates the table.

 */

private void inflateTable(int toSize) {

    // Find a power of 2 >= toSize 保证数组大小一定是 2 的 n 次方。
    // new HashMap(519)，大小是1024
    int capacity = roundUpToPowerOf2(toSize);

    // 计算扩容阈值：capacity * loadFactor
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 初始化数组
    table = new Entry[capacity];

    initHashSeedAsNeeded(capacity);

}

HashMap1.8（与1.7的不同之处）


扩容


所以1.8的最大扩容临界点就是12

put


为什么要转换？

在1.7的hashMap中，若表size从512扩容至1024，链表的最大长度也增大到1024，这样若出现新插入的五百多个元素全部进入第一个链表，导致链表长度过大，则会造成查询速度很慢的情况。所以1.8有了树形结构。

树：构建树结构，复杂（插入复杂），所以复杂jdk1.8是在达到一定阈值（8）的时候，再转换成树

Java8扩容时机

1、 超过阈值（默认12）

2、 当链表长度超过8，且，数组长度<64的时候(代码如下图)


所以1.8的hashmap扩容时机最大是12，最小是9。

并发安全

jdk1.7 CurrentHashMap

初始化



put

Segment.put


<=1.7segment(分段锁) = HashMap功能+Lock锁的功能 = 类似hashTable

缺点：统计size，就是遍历每个segment，性能较差

1.8ConcurrentHashMap——— 没有segment概念

put

无冲突的时候 CAS无锁


降低锁的粒度，减小冲突发生的可能性。