精解四大集合框架：Map核心知识总结

关注“Java后端技术全栈”

回复“面试”获取全套面试资料

Map 集合类用于存储元素对（称作“键”和“值”），其中每个键映射到一个值。从概念上而言，您可以将 List 看作是具有数值键的 Map。而实际上，除了 List 和 Map 都在定义 java.util 中外，两者并没有直接的联系。

Java 核心类中有很多预定义的 Map 类。在介绍具体实现之前，我们先介绍一下 Map 接口本身，以便了解所有实现的共同点。Map 接口定义了四种类型的方法，每个 Map 都包含这些方法。

主要方法

覆盖的方法

我们将这 Object 的这两个方法覆盖，以正确比较 Map 对象的等价性。

更新方法

可以更改 Map 内容。

返回视图的 Map 方法

使用这些方法返回的对象，您可以遍历 Map 的元素，还可以删除 Map 中的元素。

访问方法

这些方法检索有关 Map 内容的信息但不更改 Map 内容。

核心 Map

Java 自带了各种 Map 类。这些 Map 类可归为三种类型：

• 通用 Map，用于在应用程序中管理映射，通常在 java.util 程序包中实现
• HashMap
• Hashtable
• Properties
• LinkedHashMap
• IdentityHashMap
• TreeMap
• WeakHashMap
• ConcurrentHashMap
• 专用 Map，您通常不必亲自创建此类 Map，而是通过某些其他类对其进行访问
• java.util.jar.Attributes
• javax.print.attribute.standard.PrinterStateReasons
• java.security.Provider
• java.awt.RenderingHints
• javax.swing.UIDefaults
• 一个用于帮助实现您自己的 Map 类的抽象类
• AbstractMap

常用实现类

在工作中常用的Map实现类有HashMap、Hashtable(基本上也不用了)、ConcurrentHashMap。

下面来对这三个进行一个总结。

HashMap

HashMap 是以key-value 键值对形式存储数据，允许 key 为 null（多个则覆盖），也允许 value 为 null。底层结构是数组 + 链表 + 红黑树。

主要属性：

• initialCapacity：初始容量，默认 16，2 的 N 次方。
• loadFactor：负载因子，默认 0.75，用于扩容。
• threshold：阈值，等于 initialCapacity * loadFactor，比如：16 * 0.75 = 12。
• size：存放元素的个数，非 Node 数组长度。
• Node

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    //存储元素的数组
    transient Node<K,V>[] table;
    //存放元素的个数，非Node数组长度
    transient int size;
    //记录结构性修改次数，用于快速失败
    transient int modCount;
    //阈值
    int threshold;
    //负载因子，默认0.75，用于扩容
    final float loadFactor;

     /**
     * 静态内部类，存储数据的节点 
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        //节点的hash值
        final int hash;
        //节点的key值
        final K key;
        //节点的value值
        V value;
        //下一个节点的引用
        Node<K,V> next;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
}

数据结构：数组 + 单链表，Node 结构：hash|key|value|next

HashMap数据结构

特征：

1. 只允许一个 key 为 Null（多个则覆盖），但允许多个 value 为 Null
2. 查询、插入、删除效率都高（集成了数组和单链表的特性）
3. 默认的初始化大小为 16，之后每次扩充为原来的 2 倍
4. 线程不安全

使用场景：

1. 快速增删改查
2. 随机存取
3. 缓存

哈希冲突的解决方案：

1. 开放定址法
2. 再散列函数法
3. 链地址法（拉链法，常用）

put() 存储的流程（Java 8）：

1. 计算待新增数据 key 的 hash 值；
2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况，则需要进行初始化；
3. 根据 hash 值通过位运算定计算出 Node 数组的下标，判断该数组第一个 Node 节点是否有数据，如果没有数据，则插入新值；
4. 如果有数据，则根据具体情况进行操作，如下：

• 如果该 Node 结点的 key（即链表头结点）与待新增的 key 相等（== 或者 equals），则直接覆盖值，最后返回旧值；
• 如果该结构是树形，则按照树的方式插入新值；
• 如果是链表结构，则判断链表长度是否大于阈值 8，如果 >=8 并且数组长度 >=64 才转为红黑树，如果 >=8 并且数组长度 < 64 则进行扩容；
• 如果不需要转为红黑树，则遍历链表，如果找到 key 和 hash 值同时相等，则进行覆盖返回旧值，如果没有找到，则将新值插入到链表的最后面（尾插法）；

1. 判断数组长度是否大于阈值，如果是则进入扩容阶段。

resize() 扩容的流程（Java 8）：

扩容过程比较复杂， 迁移算法与 Java 7 不一样，Java 8 不需要每个元素都重新计算 hash，迁移过程中元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。

get() 查询的流程（Java 8）：

1. 根据 put() 方法的方式计算出数组的下标；
2. 遍历数组下标对应的链表，如果找到 key 和 hash 值同时相等就返回对应的值，否则返回 null。

get() 注意事项：Java 8 没有把 key 为 null 放到数组 table[0] 中。

remove() 删除的流程（Java 8）：

1. 根据 get() 方法的方式计算出数组的下标，即定位到存储删除元素的 Node 结点；
2. 如果待删结点是头节点，则用它的 next 结点顶替它作为头节点；
3. 如果待删结点是红黑树结点，则直接调用红黑树的删除方法进行删除；
4. 如果待删结点是链表中的一个节点，则用待删除结点的前一个节点的 next 属性指向它的 next 结点；
5. 如果删除成功则返回被删结点的 value，否则返回 null。

remove() 注意事项：删除单个 key，注意返回是的键值对中的 value。

为什么使用位运算（&）来代替取模运算（%）：

1. 效率高，位运算直接对内存数据进行操作，不需转成十进制，因此处理速度非常快；
2. 可以解决负数问题，比如：-17 % 10 = -7。

HashMap 在 Java 7 和 Java 8 中的区别：

1. 存放数据的结点名称不同，作用都一样，存的都是 hashcode、key、value、next 等数据：

• Java 7：使用 Entry 存放数据
• Java 8：改名为 Node

1. 定位数组下标位置方法不同：

• Java 7：计算 key 的 hash，将 hash 值进行了四次扰动，再进行取模得出；
• Java 8：计算 key 的 hash，将 hash 值进行高 16 位异或低 16 位，再进行与运算得出。

1. 扩容算法不同：

• Java 7：扩容要重新计算 hash
• Java 8：不用重新计算

1. put 方法插入链表位置不同：

• Java 7：头插法
• Java 8：尾插法

1. Java 8 引入了红黑树，当链表长度 >=8 时，并且同时数组的长度 >=64 时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能。

HashTable

和 HashMap 一样，Hashtable 也是一个哈希散列表，Hashtable 继承于 Dictionary，使用重入锁 Synchronized 实现线程安全，key 和 value 都不允许为 Null。HashTable 已被高性能的 ConcurrentHashMap 代替。

主要属性：

• initialCapacity：初始容量，默认 11。
• loadFactor：负载因子，默认 0.75。
• threshold：阈值。
• modCount：记录结构性修改次数，用于快速失败。

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {
    //真正存储数据的数组
    private transient Entry<?,?>[] table;
    //存放元素的个数，非Entry数组长度
    private transient int count;
    //阈值
    private int threshold;
    //负载因子，默认0.75
    private float loadFactor;
    //记录结构性修改次数，用于快速失败
    private transient int modCount = 0;

    /**
    * 静态内部类，存储数据的节点
    */
    private static class Entry<K,V> implements Map.Entry<K,V> {
        //节点的hash值
        final int hash;
        //节点的key值
        final K key;
        //节点的value值
        V value;
        //下一个节点的引用
        Entry<K,V> next;
    }
    //使用同步锁修饰的方法
    public synchronized int size() {
        return count;
    }
    public synchronized boolean isEmpty() {
        return count == 0;
    }
    public synchronized V put(K key, V value) {
        //...
    }
    public synchronized boolean equals(Object o) {
    //....
    }
}    

快速失败原理是在并发场景下进行遍历操作时，如果有另外一个线程对它执行了写操作，此时迭代器可以发现并抛出 ConcurrentModificationException，而不需等到遍历完后才报异常。

数据结构：链表的数组，数组 + 链表，Entry 结构：hash|key|value|next

特征：

1. key 和 value 都不允许为 Null；
2. HashTable 默认的初始大小为 11，之后每次扩充为原来的 2 倍；
3. 线程安全。

原理：

与 HashMap 不一样的流程是定位数组下标逻辑，HashTable 是在 key.hashcode() 后使用取模，HashMap 是位运算。HashTable 是 put() 之前进行判断是否扩容 resize()，而 HashMap 是 put() 之后扩容。

ConcurrentHashMap

ConcurrentHashMap 在 Java 8 版本中丢弃了 Segment（分锁段）、ReentrantLock、HashEntry 数组这些概念，而是采用CAS + Synchronized 实现锁操作，Node 改名为 HashEntry，引入了红黑树保证查询效率，底层数据结构由数组 + 链表 + 红黑树组成，Node 数组默认为 16。数据结构如下图：

ConcurrentHashMap数据结构

数据结构（Java 8)：Node[] 数组 + 单链表 + 红黑树

put() 存储的流程（Java 8）：

1. 判断待新增数据 key 和 value 是否为空，如果是则抛空指针异常；
2. 计算待新增数据 key 的 hash 值；
3. 判断 Node[] 数组是否为空或者数据长度为 0 的情况，则需要进行初始化；
4. 根据 hash 值通过位运算定计算出 Node 数组的下标，判断该数组第一个 Node 节点是否有数据，如果没有数据，则使用 CAS 操作将这个新值插入；
5. 如果有数据，则判断头结点的 hashCode 是否等于 MOVED（即 -1），即检查是否正在扩容，如果等于 - 1 则帮助扩容；
6. 如果有数据，则对头结点进行加锁（synchronized），如果头结点的 hashCode>=0，说明是链表，遍历链表，如果找到 key 和 hash 值同时相等，则进行覆盖，如果没有找到，则将新值插入到链表的最后面（尾插法）；如果 hashCode<0，说明是红黑树，调用红黑树的插值方法插入新节点；
7. 插值完成之后，判断链表元素是否 >=8，如果 >=8 并且数组长度 >=64 才转为红黑树，如果 >=8 并且数组长度 < 64 则进行扩容。

resize() 扩容的流程（Java 8）：

扩容的原理是创建新的数组，长度是原来的两倍，然后把旧数组数据迁移到新的数组中，在多线程情况下，需要注意线程安全问题，在解决安全问题的同时，还需要关注其效率。

get() 查询的流程（Java 8）：

1. 计算获取数据 key 的 hash 值；
2. 根据 hashCode 通过位运算定得到 Node 数组的下标，即得到头节点；
3. 如果头结点为空，则返回 null；
4. 如果头结点的 key 与参数 key 可以相等，则返回头结点的值；
5. 如果头结点的 hashCode 小于 0，说明是红黑树，则调用 find() 方法按照树的方式获取值；
6. 如果都不满足 3、4 和 5 条件，说明是链表，则按照链表的方式遍历获取值。整个过程都不需要加锁。

get() 注意事项：

整个过程都不需要加锁，因为读取数据的属性使用 volatile 修饰，实现线程可见性。

remove() 删除的流程（Java 8）：

1. 计算待新增数据 key 的 hash 值；
2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况，如果是则返回 null；如果不是则根据 hashCode 通过位运算定得到 Node 数组的下标，即得到头结点；
3. 判断头结点的 hashCode 是否等于 MOVED（即 -1），检查是否正在扩容，如果是则帮助扩容；
4. 如果都不满足 2 和 3 条件，则加锁进行删除操作；
5. 首先判断头结点有无发生变化（步骤 3 点转移操作会改变头结点），如果有改变则返回 null；
6. 如果头结点的 hashCode 大于 0 说明是链表，则按照链表方式遍历删值；
7. 如果头结点是 TreeBin 类型，说明是红黑树，则按照树的方式删值。

remove() 注意事项：

remove 函数底层是调用 replaceNode 函数实现结点的删除。

使用场景：并发、线程不安全场景

TreeMap

TreeMap 实现了 SotredMap 接口，意味着可以排序，是一个有序的集合。底层数据结构是红黑树结构，TreeMap 中的每个元素都存放在红黑树的节点上，默认使用自然排序，也可以自定排序，线程不安全。

主要属性：

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
    //排序比较器
    private final Comparator<? super K> comparator;
    //红黑树根节点
    private transient Entry<K,V> root;
    //集合长度
    private transient int size = 0;
    //记录结构性修改次数，用于快速失败
    private transient int modCount = 0;

    //红黑树常量
    private static final boolean RED   = false;
    private static final boolean BLACK = true;

    /**
    * 实际存储数据的节点 
    */
    static final class Entry<K,V> implements Map.Entry<K,V> {
        //节点的key值
        K key;
        //节点的value值
        V value;
        //左子树引用
        Entry<K,V> left;
        //右子树引用
        Entry<K,V> right;
        //父节点引用
        Entry<K,V> parent;
        //节点颜色（默认黑色）
        boolean color = BLACK;
    }
}    

数据结构：红黑树（高效的检索二叉树），Entry 结构：key|value|left|right|parent|color

特征：

1. key 不允许为 Null，但允许多个 value 为 Null
2. 线程不安全

put() 存储的流程：

主要分为两个步骤，构建排序二叉树和构建平衡二叉树。

构建排序二叉树，过程如下：

1. 从根节点 root 开始查找；
2. 如果 root 节点比待插入节点值小，则在 root 节点左子树查找，如果大于，则在右子树查找；
3. 递归循环步骤 2，找到合适的节点为止；
4. 把待插入节点与步骤 3 中找到的节点进行比较，如果待插入节点小于找到节点，则把待插入节点作为左子节点；否则作为右子节点。

举个栗子：put(9)，步骤如下：

在这里插入图片描述

1. 从 root 节点 8 开始检索；
2. 如果 8 小于 9，则从 8 的右子树继续找，10 大于 9，10 没有左子树；
3. 循环递归步骤 2，找到 10 这个合适节点；
4. 10 大于 9，则把 9 作为左子节点。

构建平衡二叉树，经过左旋、右旋、着色这些步骤后，得到一棵平衡二叉树。

remove() 的流程：比 put() 复杂，也是分两个步骤，删除节点和着色旋转。

删除节点，删除时出现以下 3 种情况：

1. 待删除节点，如果没有左和右子节点时，则直接删除；
2. 待删除节点，如果有一个子节点时，则把它的子节点指向它的上级节点（即父节点）；
3. 待删除节点，如果有两个非空的子节点时，流程复杂，暂不在此解释。

着色旋转，进行颜色的对调和旋转，达到红黑树的特征。

LinkedHashMap

LinkedHashMap 是使用 HashMap 机制实现。LinkedHashMap 在 HashMap 的基础上增加 before 和 after 两个属性来保证了迭代顺序。迭代顺序可以是插入顺序（默认），也可以是访问顺序。线程不安全。

主要属性：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    /**
    * 静态内部类，存储数据的节点
    */
    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);
        }
    }

    //头结点
    transient LinkedHashMap.Entry<K,V> head;
    //尾结点
    transient LinkedHashMap.Entry<K,V> tail;
    //排序标识，true访问顺序迭代；false插入顺序迭代（默认）
    final boolean accessOrder;
}    

数据结构：数组 + 双向链表，Entry 结构：before|hash|key|value|next|after，before 和 after 用于维护整个双向链表。

特征：

1. 只允许一个 key 为 Null（多个则覆盖），允许多个 value 为 Null；
2. 线程不安全。

原理：

LinkedHashMap 继承了 HashMap，hash 算法也是跟 HashMap 一致。LinkedHashMap 在 Entry 中新增了 before 和 after 两个属性来维护双向链表的迭代顺序。Entry 的 next 属性是维护 Entry 连接顺序，而 after 是维护迭代顺序。LinkedHashMap 使用 LRU 算法实现访问顺序排序，比如 get() 操作后的元素会移动到链表末尾，从而实现按访问顺序迭代。

使用场景：保证插入和访问顺序