HashMap和ConcurrenthashMap详解(非常全面)

HashMap

1.HashMap简介

HashMap是Java中的一个常用的哈希表实现，用于存储键值对，是Java集合框架的常用类。

如下图所示：

HashMap继承了AbstractMap类，并且同时实现了Map接口。

主要特点和用途：

1. 键值对存储： HashMap允许将键和值关联起来，并将这些键值对存储在哈希表中。
2. 快速查找： 通过哈希函数，HashMap可以在常数时间内查找给定键所对应的值。
3. 灵活的键： 键可以是任何非null的对象，包括自定义类的实例。
4. 非同步： HashMap是非线程安全的，适用于单线程环境，在多线程环境中，应考虑使用ConcurrentHashMap。

 

2.HashMap数据结构

HashMap的内部实现：基于数组和链表和红黑树来实现的，红黑树是JDK1.8增加的。

如下图所示：

它使用哈希函数将键映射到数组索引，并将具有相同哈希码值的键值对存储在同一个链表（或红黑树）中，以解决哈希冲突。

 

3.数组（Array）

HashMap使用一个数组来存储数据，这个数组被称为“桶数组”（bucket array）。

每个桶数组的元素称为“桶”，就是上图的蓝色部分，每个桶可以存储一个或多个键值对。

如下所示：

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;  // 下一个节点的引用

    // 构造函数等代码
    // ...

    // JDK 1.8中新增的红黑树相关字段
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red;
}

Node节点是HashMap中用于存储键值对的基本单元，它包含：键、值、哈希值、下一个节点的引用等信息。

 

4.链表（Linked List）

在哈希表中，不同的键可能会映射到相同的数组索引位置，从而引发哈希冲突，为了解决哈希冲突的一种常见方法是链式法。

如下图所示：

当哈希冲突发生时，具有相同哈希值的键值对会被存储在同一个桶中，形成一个链表。

 

5.红黑树（Red-Black Tree）

当链表长度超过阈值（默认为8）时，链表会被转换为红黑树，以提高查找效率。

如下图所示：

在红黑树中，查找、插入和删除操作的时间复杂度为O(log n)，相比链表的O(n)要好。

 

ConcurrentHashMap

1.ConcurrentHashMap简介

ConcurrentHashMap是Java中用于多线程环境下的线程安全哈希表实现。

ConcurrentHashMap是对HashMap的改进，通过使用分段锁和CAS等技术来实现线程安全性。

 

2.JDK1.7 ConcurrentHashMap实现原理

谈到ConcurrentHashMap原理，这里需要谈下：JDK1.7和JDK1.8两个版本的ConcurrentHashMap的实现。

在JDK1.7中ConcurrentHashMap采用了：数组+Segment+分段锁的方式实现。

如下图所示：

分段锁的实现：

1. ConcurrentHashMap内部被划分为一定数量的段（Segments），每个段都是一个独立的哈希表，拥有自己的锁。
2. 每个段包含一部分键值对，不同的段之间可以并发读写，因为每个段都有自己的锁，不同段之间的操作不会相互影响。
3. ConcurrentHashMap在JDK 1.7中的结构由多个段（Segment）组成，每个段内部的实现与普通的HashMap类似，包含了数组和链表（或红黑树）的组合。

总结而言，JDK 1.7中的ConcurrentHashMap实现基于分段锁，将整个哈希表分为多个段，每个段拥有自己的锁。

这种实现方式允许一定程度的并发性，但在高并发写入的情况下可能还是需要注意性能问题。

 

2.JDK1.8 ConcurrentHashMap实现原理

在JDK 1.8中，ConcurrentHashMap的实现经过了重大的改进，参考了JDK8 HashMap的实现，进行全面升级。

如下图所示：

内部实现：

• JDK 1.8中的ConcurrentHashMap没有了“段”的概念，而是直接使用数组来存储Node，每个Node表示一个键值对。
• 每个数组元素可能是一个链表的头节点，也可能是一个红黑树的根节点（在键值对数超过一定阈值时）。

线程安全：

在JDK 1.8中，ConcurrentHashMap的设计依赖于CAS（Compare and Swap）操作和synchronized关键字，以实现线程安全性。

ConcurrentHashMap的插入、查找和删除等操作是通过CAS和synchronized来保证线程安全的。

性能：

• 在JDK 1.8中，ConcurrentHashMap的性能进一步提高，相比于JDK 1.7中的分段锁实现，更适用于高并发的场景。
• ConcurrentHashMap在多线程读取和写入时，能够提供更好的性能。

总结而言，JDK 1.8中的ConcurrentHashMap使用了新的数据结构和线程安全机制，通过CAS和synchronized来实现高效的并发性能。