Java 集合 - Map 容器

Liang

2020-02-17

Java 集合容器

297

一、HashMap

2.1 结构

2.1.1 JDK 1.7

采用数组 + 链表实现，如下：

Entry[] table
Entry

table 源码片段：

transient Entry[] table;

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

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }
    
    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    ...
}

整体来看：

一个 HashMap 就是一个 Entry 数组
一个 Entry 数组的每一个 Entry 都是一条链表

2.1.2 JDK 1.8

采用数组 + 链表 + 红黑树

Node[] table
Node
TreeNode

table 源码片段：

transient Node<K,V>[] table;

Node 源码片段：

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        ...
    }

TreeNode 源码片段：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    ...
}

ThreeNode 继承的 LinkedHashMap.Entry 源码片段：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

树化阈值：

static final int TREEIFY_THRESHOLD = 8;

链化阈值：

static final int UNTREEIFY_THRESHOLD = 6;

整体来看：

一个 HashMap 就是一个 Node 数组
一个 Node 数组的每一个 Node 就是一条链表
当 Node 链表长度 >= 8，链表树化成红黑树，Node 头节点转换为 TreeNode 根结点
一个 Node 数组的每一个 TreeNode 就是一棵红黑树
当 TreeNode 数量小于 <= 6，红黑树链化成链表，TreeNode 转换成 Node 结点

PS：由于有继承关系如下

TreeNode extends LinkedHashMap.Entry
LinkedHashMap.Entry extends HashMap.Node

所以转化成树结点，会上转型，存在 Node 数组，不会混乱

2.2 碰撞

对于 HashMap 来说，减少碰撞冲突是很有必要的，JDK 1.7 & 1.8 的 HashMap 都是哈希桶，桶里要么存的是链表，要么存的是红黑树

减少碰撞，有以下几个途径可以考虑：

扰动函数：使元素位置分布均匀
使用 final 对象作为 key（String、Integer）：不可变对象保证了 key 的不可更改性，同时重写了 hashcode() 和 equals() ，hash 值不易计算错误

基于 JDK 1.8 ，分析放入添加值的计算桶下标过程：

将值添加到 hashmap 源码片段：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null) //这里计算下标 i
            tab[i] = newNode(hash, key, value, null);
		...
}

key 的 hashcode 计算源码片段：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashcode() 源码片段：

public native int hashCode();

调用过程分析：

首先通过本地方法获取到 hashcode，是一个 int 型的数，那么有 32 位
将 hashcode 与 hashcode 无符号右移 16 位后的结果相异或
返回 hashcode
取到 hashcode 后，通过 i = (n - 1) & hashcode，计算得出桶下标 i ，n 就是 hashmap 的容量

其实， (n - 1) & hashcode 等价于 hashcode % n，不过位运算更快，所以不用取模

并且，能够用该位运算替代取模操作，有个大前提就是每次扩容，新容量要都要为原来的 2^n 倍

2.3 扩容

2.3.1 区别

JDK 1.7 的扩容条件有两个：

存在碰撞
Node 数量大于阈值（n * 装填因子）

默认：16 * 0.75，阈值为 12

若 16 个 Node 均匀分布在桶的 16 个位置，不会扩容，因为没有冲突碰撞
若 11 个 Node 在桶的一个位置，不会扩容，因为没有大于阙值

JDK 1.8 的扩容条件有一个：

Node 数量容量大于阈值，不一定需要碰撞

2.3.2 容量确定

每次扩容，新的容量为原来的 2^n 倍大，也就是 2 的幂次方，分两种情况：

初始化容量确定
扩容容量确定

初始化容量确定

但初始化的时候，可以指定一个初始容量，不一定为 2 的幂次方，于是 hashmap 会进行如下操作，确保一个最接近旧容量，且大于或等于它的 2 的幂次方的新容量

源码片段：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

减 1 的目的是如果本身就是 2 的幂次方，那么不改变本身

扩容容量确定

初始化完了，就是扩容，负载因子默认 0.75 ，表示存储量达到最大的 75% 就要扩容，此时创建原来两倍大小的数组，并把元素容量依次放入

2.3.4 ReHashing

初始化完了之后的扩容，需要对元素依次重算 hashcode，并依次放入新的桶，这个过程就是 rehash

ReHashing 过程中，JDK 1.7 使用头插法移动节点元素，可能会发生循环链表问题，在 JDK 1.8 使用尾插法解决了问题，循序也不是反的

引用：Kristin - JDK1.7 HashMap死循环问题的图，来说明 JDK 1.7 扩容的循环链表问题

可以看到，这个过程是使用头插法的，简单说明一下

头插法就是：

若有链表 2： A->B->C，现在插入到 4：则有
- 4：A
- 4：B->A
- 4：C->B->A

尾插法就是：

若有链表 2： A->B->C，现在插入到 4：则有
- 4：A
- 4：A->B
- 4：A->B->C

回到 HashMap 中，两个线程并发执行如下：

简单解析这个过程，C 节点可以忽略不计：

T1：
- 得知 OldList：目前信息，A->B->C
- 下一步要利用头插法搞到 NewList，使得：B->A
- 正要开始，这时被暂停了
T2：
- 把链表搞成了 B->A
T1：
- 终于唤醒了！但它知道的还是没有更新的 OldList 信息，但不知道现在 B->A 了
- 它会按照 OldList：A->B->C 完全没动过的原始信息那样去重做一遍 T2 搞定的事
- 第一步，B->A 没问题，因为睡着前已经保存了 e 和 next 信息，这一步可以完成
- 第二步，要获取第三个元素时，头插法的过程会获取到 B 的下一个元素，本来应该要是 C ，但其实由于 T2 ，这里已经是 A 了，于是再 A 插入 B 之前，A-> B，而 T2 搞的 B->A ，链表循环

如果用尾插法，不会出现这种问题

2.4 线程安全性

HashMap 是线程不安全的，虽然 JDK 1.8 修复了 rehashing 链表可能成环的并发问题，它依然是线程不安全的，因为多个线程对 HashMap 写，可能存在丢失修改，多个线程对 hashmap get，也可能出现数据更新延迟的错误

二、HashTable

HashTable 是线程安全的 HashMap，方法实现基本没有区别，就是每个方法基本都加了 synchronized 重量锁，方法加锁，获取到的就是 this 对象，一旦获取锁，其他线程无法执行其他方法，被阻塞，效率比较低下

三、ConcurrentHashMap

3.1 目的

为了优化 HashTable，引入了 ConcurrentHashMap

3.2 结构

3.2.1 JDK 1.7

采用分锁锁 + 哈希桶（数组） + 链表实现，如下

Segment<K, V>[] segments
HashEntry<K, V>[] table;
HashEntry

分段锁数组 segments 源码片段：

final Segment<K,V>[] segments;

分段锁 segment 与哈希桶（table）源码片段：

static final class Segment<K,V> extends ReentrantLock implements Serializable {

    private static final long serialVersionUID = 2249069246763182397L;

    static final int MAX_SCAN_RETRIES =
        Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

    transient volatile HashEntry<K,V>[] table;

    transient int count;

    transient int modCount;

    transient int threshold;

    final float loadFactor;
}

链表节点 HashEntry 源码片段：

static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;
}

分别解析一下这几种结构：

Segment，分段锁，同时它继承 ReentrantLock，是一种可重入锁，基于数组和链表实现
HashEntry，哈希桶，基于链表实现

所以，高层来看：

一个 ConcurrentHashMap 就是一个 Segment 数组（Segments）
一个 Segment 数组里的每一个 Segment 都维护了一个哈希桶（table）
一个哈希桶里面每个位置都维护了一条链表（HashEntry）

3.2.2 JDK 1.8

采用数组 + 链表 + 红黑树，结构如下：

Node<K,V>[] table
Node<K,V>
TreeNode<K,V>
TreeBin<K,V>

数组源码片段：

transient volatile Node<K,V>[] table;

链表节点源码片段：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        ...
}

红黑树结点源码片段：

static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        ...
}

红黑树操作结点源码片段：

static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    // values for lockState
    static final int WRITER = 1; // set while holding write lock
    static final int WAITER = 2; // set when waiting for write lock
    static final int READER = 4; // increment value for setting read lock
    ...
}

分析一下这几个结构：

Node，链表结点，每一个 Node 都实现了 Map.Entry
TreeNode，红黑树结点，用于链表节点（Node）转换成树的红黑树结点（TreeNode）
TreeBin，红黑树结点容器，对 TreeNode 的封装，JDK 操作红黑树真正操作的是这个结点，包含锁控制等

从高层来看，有以下层次：

一个 ConcurrentHashMap 有一个 Node 数组
Node 数组的每一个位置，是一条链表（Node），或者存一棵红黑树（TreeBin）
红黑树（TreeBin）是对一系列的红黑树数据结点（TreeNode）的封装

3.3 并发控制

一般并发问题发生在 put，以下就讨论一下 put 的并发控制

3.3.1 JDK 1.7

每次要操作某个哈希桶，必须就得获取到桶对应的 segment，也就是分段锁，一旦 segment 被获得，其他线程再次获取会被阻塞，但其他线程获取其他的 segment 不会被阻塞

默认的 segment 是 16 个，也就是有 16 个分段锁

3.3.2 JDK 1.8

采用 CAS + synchronized 实现

CAS 指的是首次插入，当插入的时候发现链表没有头节点，则采用 CAS 重试去插入链表头节点
而一旦发现有了链表头节点，CAS 失败，再次重试若发生碰撞，就通过 synchronized 获取链表头节点或者树的头结点，从而进行插入操作

所以，总体来看：

DK 1.7 是一个分段锁锁定一个哈希桶，哈希桶那么多个元素共享一个分段锁
JDK 1.8 是去除了分段锁，一旦有冲突，每个元素使用一个锁，锁的粒度更小，改善锁竞争，提高了并发度