转载

Java并发指南13：Java7和8 中的 HashMap 和 ConcurrentHashMap 全解析

本文首发于我的个人博客： https://h2pl.github.io/

欢迎阅览我的CSDN专栏：Java并发指南

https://blog.csdn.net/column/details/21961.html

相关代码会放在我的的Github： https://github.com/h2pl/

Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析

转自 https://www.javadoop.com/post/hashmap#toc7

部分内容转自

http://www.jasongj.com/java/concurrenthashmap

今天发一篇”水文”，可能很多读者都会表示不理解，不过我想把它作为并发序列文章中不可缺少的一块来介绍。本来以为花不了多少时间的，不过最终还是投入了挺多时间来完成这篇文章的。

网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少，不过缺斤少两的文章比较多，所以才想自己也写一篇，把细节说清楚说透，尤其像 Java8 中的 ConcurrentHashMap，大部分文章都说不清楚。终归是希望能降低大家学习的成本，不希望大家到处找各种不是很靠谱的文章，看完一篇又一篇，可是还是模模糊糊。

阅读建议：四节基本上可以进行独立阅读，建议初学者可按照 Java7 HashMap -> Java7 ConcurrentHashMap -> Java8 HashMap -> Java8 ConcurrentHashMap 顺序进行阅读，可适当降低阅读门槛。

阅读前提：本文分析的是源码，所以至少读者要熟悉它们的接口使用，同时，对于并发，读者至少要知道 CAS、ReentrantLock、UNSAFE 操作这几个基本的知识，文中不会对这些知识进行介绍。Java8 用到了红黑树，不过本文不会进行展开，感兴趣的读者请自行查找相关资料。

Java7 HashMap
- put 过程分析
  - 数组初始化
  - 计算具体数组位置
  - 添加节点到链表中
  - 数组扩容
- get 过程分析
Java7 ConcurrentHashMap
- 初始化
- put 过程分析
  - 初始化槽: ensureSegment
  - 获取写入锁: scanAndLockForPut
  - 扩容: rehash
- get 过程分析
- 并发问题分析
Java8 HashMap
- put 过程分析
  - 数组扩容
- get 过程分析
Java8 ConcurrentHashMap
- 初始化
- put 过程分析
  - 初始化数组：initTable
  - 链表转红黑树: treeifyBin
- 扩容：tryPresize
  - 数据迁移：transfer
- get 过程分析
总结

Java7 HashMap

HashMap 是最简单的，一来我们非常熟悉，二来就是它不支持并发操作，所以源码也非常简单。

首先，我们用下面这张图来介绍 HashMap 的结构。

Java并发指南13：Java7和8 中的 HashMap 和 ConcurrentHashMap 全解析

这个仅仅是示意图，因为没有考虑到数组要扩容的情况，具体的后面再说。

大方向上，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/. 不存在重复的 
                原文  
                http://h2pl.github.io/2018/05/29/concurrent13/

正文到此结束