本日发一篇”水文”，大概许多读者城市暗示不领略，不外我想把它作为并发序列文章中不行缺少的一块来先容。原来觉得花不了几多时间的，不外最终照旧投入了挺多时间来完成这篇文章的。

网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少，不外缺斤少两的文章较量多，所以才想本身也写一篇，把细节说清楚说透，尤其像 Java8 中的 ConcurrentHashMap，大部门文章都说不清楚。终归是但愿能低落各人进修的本钱，不但愿各人处处找各类不是很靠谱的文章，看完一篇又一篇，但是照旧模恍惚糊。

阅读发起：四节根基上可以举办独立阅读，发起初学者可凭据 Java7 HashMap -> Java7 ConcurrentHashMap -> Java8 HashMap -> Java8 ConcurrentHashMap 顺序举办阅读，可适当低落阅读门槛。

阅读前提：本文阐明的是源码，所以至少读者要熟悉它们的接口利用，同时，对付并发，读者至少要知道 CAS、ReentrantLock、UNSAFE 操纵这几个根基的常识，文中不会对这些常识举办先容。Java8 用到了红黑树，不外本文不会举办展开，感乐趣的读者请自行查找相关资料。

Java7 HashMap

HashMap 是最简朴的，一来我们很是熟悉，二来就是它不支持并发操纵，所以源码也很是简朴。

首先，我们用下面这张图来先容 HashMap 的布局。

这个仅仅是示意图，因为没有思量到数组要扩容的环境，详细的后头再说。

大偏向上，HashMap 内里是一个数组，然后数组中每个元素是一个单向链表。

上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包括四个属性：key, value, hash 值和用于单向链表的 next。

capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组巨细为当前的 2 倍。

loadFactor：负载因子，默认为 0.75。

threshold：扩容的阈值，便是 capacity * loadFactor

put 进程阐明

照旧较量简朴的，随着代码走一遍吧。

public V put(K key, V value) {
    // 当插入第一个元素的时候，需要先初始化数组巨细
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 假如 key 为 null，感乐趣的可以往里看，最终会将这个 entry 放到 table[0] 中
    if (key == null)
        return putForNullKey(value);
    // 1. 求 key 的 hash 值
    int hash = hash(key);
    // 2. 找到对应的数组下标
    int i = indexFor(hash, table.length);
    // 3. 遍历一下对应下标处的链表，看是否有反复的 key 已经存在，
    //    假如有，直接包围，put 要领返回旧值就竣事了
    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;
        }
    }

    modCount++;
    // 4. 不存在反复的 key，将此 entry 添加到链表中，细节后头说
    addEntry(hash, key, value, i);
    return null;
}

数组初始化

在第一个元素插入 HashMap 的时候做一次数组的初始化，就是先确定初始的数组巨细，并计较数组扩容的阈值。

private void inflateTable(int toSize) {
    // 担保数组巨细必然是 2 的 n 次方。
    // 好比这样初始化：new HashMap(20)，那么处理惩罚成初始数组巨细是 32
    int capacity = roundUpToPowerOf2(toSize);
    // 计较扩容阈值：capacity * loadFactor
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 算是初始化数组吧
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity); //ignore
}

这里有一个将数组巨细保持为 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都有相应的要求，只不外实现的代码稍微有些差异，后头再看到的时候就知道了。

计较详细数组位置

这个简朴，我们本身也能 YY 一个：利用 key 的 hash 值对数组长度举办取模就可以了。

static int indexFor(int hash, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return hash & (length-1);
}

这个要领很简朴，简朴说就是取 hash 值的低 n 位。如在数组长度为 32 的时候，其实取的就是 key 的 hash 值的低 5 位，作为它在数组中的下标位置。

添加节点到链表中