开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【Java 集合】HashMap & ConcurrentHashMap 实现机制 -> 正文阅读

[数据结构与算法]【Java 集合】HashMap & ConcurrentHashMap 实现机制

本文使用 JDK 1.15 版本。

一、概述

什么是Map？

映射（Map），为解决查找元素的精确副本问题而设计的数据结构，用以存放键 / 值对。提供了键 (Key)，就能找到值 (Value)，即键 (Key)具有唯一性，而值 (Value)则不具备这个特性。

Java 提供了两个Map接口的通用实现：HashMap 和 TreeMap。

什么是HashMap？

散列映射（HashMap），它对键进行散列，只能作用于键，与键关联的值不能进行散列 / 比较。HashMap速度稍快，如若无需按排序访问键，HashMap是最好的选择，否则可选择TreeMap。

hash碰撞、解决方案：

hash碰撞：计算出的hash值相同，数组不可容纳多个元素
解决方案：将数组设计为链表 / 红黑树，数组每个位置称为 “桶”

HashMap底层结构图（数组 + 链表 + 红黑树）：

数组 + 链表：
数组 + 红黑树：

在 jdk1.8 以后，当链表内元素数超过8 时则会转化为红黑树以提高查询效率，当红黑树元素数小于6 时，则会退化回链表。

1、数组 table

数组 Table 是HashMap 的核心结构之一，为了提高取模运算hash & (table.length - 1)，选取长度为2的倍数（2ⁿ）；它允许被扩容，扩容时同样遵循这一点。
table

2、Map内置子接口 Entry → HashMap 内部类 Node

Entry是键值对的源头，HashMap 和 ConcurrentHashMap 的内部类 Node 均实现了此接口，这个类代表键值对数据结构，作为一个节点，用以存储数据。

Node 类定义key、value、hash、next等重要属性，重写HashCode()、equals()、toString()重要方法，实现父接口 Entry 的其他方法，方便内部使用。

3、HashMap 内部类TreeNode

TreeNode 是 HashMap 构成红黑树所要用到的节点，它本身继承了LinkedHashMap 的内部静态类，而 LinkedHashMap.Entry 则继承自 HashMap 的 Node，其本身继承了这两个类的所有属性，属于 HashMap.Node 类的子类，因此转换方便，值可以得到保留。由于它是 Node 的子类所以可以被放入 table 数组中。

TreeNode 类定义parent、left、right、prev、color等重要属性，继承 hash、key、value、next 等父类重要属性。

为什么TreeNode要引入 prev 前驱节点、继续使用 next 后继节点？

将单向链表转换为双向链表，能够加快红黑树的转换速度。
方便进行某些操作（如containsValue方法底层使用 next 属性查找）。

二、解析

1、重要属性

配置属性：

属性	译名	数值	解释	原因
`DEFAULT_INITIAL_ACPACITY`	初始数组大小	1 << 4 = 2⁴ = 16	数组 table 大小初始为16	选取2ⁿ取模进行`hash & (table.length - 1)`运算速度快，且取值16相对中肯
`MAX_CAPACITY`	数组最大长度	1 << 30 = 2³⁰	数组 table 大小最大为64	并非2³¹，预备部分空间留作他用
`DEFAULT_LOAD_FACTOR`	负载因子(装填因子)	0.75f	一个0.0 ~ 1.0 之间的数值（默认为0.75），这个数值决定散列数组的填充百分比；到达比例后，将散列数组扩容后结构重组。	①【适中原则】负载因子过大，桶中发生碰撞的概率就越大；过小则扩容次数增加。 ②【理性条件】 0.75是较为理想 (hash可能分布均匀)的选择，该条件下，桶中元素分布服从参数为0.5泊松分布。
`MIN_TREEIFY_CAPACITY`	树化最小数组容量	64	数组长度大于64时，允许链表在一定条件下转换为红黑树	①【设置属性原因】为防止初始时插入过多同一位置的元素而导致不必要的转换 ②【赋值64原因】时间、空间平衡，TreeNode空间为Node的2倍。
`TREEIFY_THRESHOLD`	树化阈值	8	数组内链表大小增至8时 (并且数组长度大于64)，链表转换为红黑树	① 理想状况下，LoadFactor 为 0.75时，桶中节点分布频率遵循参数为0.5的泊松分布，当链表长度为8时，概率为0.00000006，概率极低，所以树化阈值为8。 ② 阈值为8时，链表平均查找速度为8/2=4，红黑树平均查找速度为log₂8 = 3，速度更快，且节点越多差距越明显。
`UNTREEIFY_THRESHOLD`	退链阈值	6	数组内红黑树大小减至6时，红黑树退化为链表	红黑树查找速度log₂6=2.6，链表查找速度：6/2=3，速度接近，但TreeNode更占空间，故转换为链表

2、核心方法

① 一级公有方法（应用级）

1）put（底层方法：putVal）
向Map中添加元素，相同的key会被覆盖。

2）get（底层方法：getNode）
通过键获取Map中的值，如果对应的值不存在，则返回null。

3）containsKey（底层方法：getNode）
判断是否含有该键。

4）containsValue
判断是否含有该值。

5）remove（底层方法：removeNode）
根据键删除对应的值，或尝试删除键 / 值对。

6）replace（底层方法：getNode、afterNodeAccess）
根据键替换对应的值，或尝试替换键 / 值对。

HashMap<Integer,Integer> map = new HashMap<>();
map.put(1,1);
map.put(1,2);
map.put(10,20)
map.get(1);	//返回2
map.get(4);	//返回null
map.containsKey(5); //返回false
map.containsValue(2); //返回true
map.remove(10);		//根据键删除值，返回20
map.remove(1,1);	//尝试删除，删除成功

② 二级私有方法（实现级）

现在，我们为以下四个实现级的核心方法作解释说明：
1）putVal
放置元素的核心方法：
putVal
2）getNode
获取元素的核心方法：
getNode
3）removeNode
移除元素的核心方法：

4）resize
调整数组大小的核心方法（根据众多配置属性）：
resize
resize

三、使用

1、构造方法

HasMap 有三个重载的构造方法：

无参的构造方法：

HaspMap()

指定初始容量：

HashMap(int initialCapacity)

可指定初始容量、负载因子（默认为0.75），将取代默认值：

HashMap(int initialCapacity, float loadFactor)

2、初始化

类似于数组，我们同样可以在初始化 HashMap 时，通过双层花括号{{ }}（外层大括号代表匿名内部类 + 内层大括号代表初始代码块：参考文章）、调用put方法、putIfAbsent方法直接放入数据：

Map<Integer,String> map = new HashMap<Integer,String>(){{
	put(01,"小明");
	put(02,"小花");
	put(03,"小兰");
}};

3、映射视图

有3种视图：键集、值集合、键 / 值对集：

//键集
Set<K> keySet()
//值集合
Collection<V> values()
//键/值对集
Set<Map.Entry<K,V>> entrySet()

※?双射关系

使用两个 HashMap ，键值相互交换，保证所有键值对满足一一对应的关系，这种关系与策略称为双射关系。

四、多线程环境：脆弱的HashMap

HashMap 在 JDK1.8 版本以前链表添加元素采用 “头插法”，线程环境下存在产生链表成环的问题，JDK 1.8 版本以后采用 “尾插法”，避免了链表成环的问题。

但仍存在其他方面的问题，重要的方法都没有加锁，多线程环境问题举例：

读写不一致（put() 1毫秒后 get() 值不一致）
写入失败（多次写入 put() 部分失效）
频繁更改结构，节点 Node 与 TreeNode 间转换异常

程序举例（预计添加元素100000个）：

public class Demo {
    static Map<String,String> map = new HashMap<>();
   //static Map<String,String> map = new ConcurrentHashMap<>();
    public static class AddThread implements Runnable{
        int start = 0;
        public AddThread(int start){
            this.start = start;
        }

        @Override
        public void run() {
            for (int i = start; i < 100000; i+=2) {
                map.put(Integer.toString(i),Integer.toBinaryString(i));
            }
        }
    }

    public static void main(String[] args) throws Exception{
        Thread t1 = new Thread(new Demo.AddThread(0));
        Thread t2 = new Thread(new Demo.AddThread(1));
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(map.size());
    }
}

得到如下几种结果：
① 抛出异常（频繁更改结构，Node 与 TreeNode 间转换异常），程序得出错误结果：

② 部分元素未能成功添加，得到小于设定大小的结果：
小于设定结果
③ 正常结束，并且结果符合预期（几乎不可能遇到）

④ 程序永远无法结束：
程序无法结束
使用ConcurrentHashMap：
修改以下代码：

//static Map<String,String> map = new HashMap<>();
static Map<String,String> map = new ConcurrentHashMap<>();

结果符合预期：
预期结果

五、ConcurrentHashMap 如何保障线程安全？

ConcurrentHashMap ，为解决HashMap 线程不安全、HashTable运行慢而定制的一种哈希映射结构，设计理念基于HashMap，默认参数均与HashMap相同。

CAS操作

锁支持
线程操作时，对互不干扰的部分分段加锁，故命名为Segment (分段锁)。
Segment

LockSupport 协助线程
LockSupport类，是JUC包中的一个工具类，是用来创建锁和其他同步类的基本线程阻塞原语。

Basic thread blocking primitives for creating locks and other synchronization classes

LockSupport类的核心方法其实就两个：park()和unpark()，其中park()方法用来阻塞当前调用线程，unpark()方法用于唤醒指定线程。
这其实和Object类的wait()和signal()方法有些类似，但是LockSupport的这两种方法从语意上讲比Object类的方法更清晰，而且可以针对指定线程进行阻塞和唤醒。

LockSupport类使用了一种名为Permit（许可）的概念来做到阻塞和唤醒线程的功能，可以把许可看成是一种(0,1)信号量（Semaphore），但与 Semaphore 不同的是，许可的累加上限是1。
初始时，permit为0，当调用unpark()方法时，线程的permit加1，当调用park()方法时，如果permit为0，则调用线程进入阻塞状态。

LockSupprt
LockSupport