Java HashMap 深度解析

一、数据结构

1.1 JDK 7 vs JDK 8

JDK 7

  • 采用的是数组加链表，没有红黑树

JDK 8

  • 采用的是数组加链表加红黑树，红黑树的引入是为了解决链表过长的问题，提高查询效率

1.2 红黑树转换条件

红黑树的升级条件

  • 当链表长度大于等于 8 且数组长度大于等于 64 时，会将链表转换为红黑树

红黑树的退化条件

  • 当链表长度小于等于 6 时，会将红黑树转换为链表

1.3 Entry 结构

HashMap 的主干是一个 Entry 数组，Entry 其实就是一个有着键值对的链表节点，其中有 next 节点的指针，用于 Hash 冲突时形成链表，hash 字段是为了后面不用重复计算 hash 值，扩容直接 & 存在的

二、初始化

2.1 默认参数

HashMap 可以设置初始容量和负载因子：

  • 默认的初始容量 initialCapacity 是 16
  • 默认的负载因子 loadFactor 大小为 0.75

2.2 惰性初始化

和 ArrayList 一样，都是惰性初始化，等到实际要用了才会真正构建 table 数组。在第一次 put 的时候，如果发现没有初始化会调用 tableSizeFor，该函数的作用是确保 table 的容量始终是 2 的幂

2.3 负载因子为什么是 0.75

HashMap的负载因子LoadFactor默认值是0.75。首先我们都知道，负载因子太大太小都是不好的，如果太大会导致hash冲突的频率大大增加，降低性能，如果太小又会导致大量的空桶，很浪费空间，这个0.75是通过二项分布计算出来的，通过二项分布，我们知道负载因子最好是In2，也就是0.69，但是HashMap的容量又必须是2的次幂，所以我们用了与0.69非常接近的0.75作为HashMap的负载因子，这是时间成本和空间成本上的一种折中选择

三、⭐get 流程

3.1 核心函数

在 get 函数中主要调用了两个函数，分别是 getNode 函数和 hash 函数。

3.2 hash 函数 - 高位扰动

hash 函数是为了二次 hash，也就是高位扰动，将高 16 位和低 16 位异或，减少低位冲突，让 hash 更均匀。

3.3 getNode 函数实现

getNode 函数获取节点的步骤如下：

  1. 首先通过上面计算出来的 hash 值，得到 table 数组中桶的位置，并且得到该桶的第一个节点
  2. 如果调用 equals 方法后发现匹配上了，就会直接返回
  3. 如果不匹配就会继续去找第一个节点的下一个节点
  4. 如果是红黑树的话，会调用 getTreeNode 来查找下一个节点
  5. 如果只是链表的话，会直接使用 do-while 循环进行查找

3.4 查找流程总结

第一，通过 key 的 hash 定位数组中的桶；
第二，判断桶中的第一个节点是否命中；
第三，如果发生 hash 冲突，就在桶内继续查找：

  • 链表用遍历
  • 红黑树用树查找

整体时间复杂度理想情况下是 O(1)，冲突严重时退化为 O(n) 或 O(log n)。

四、⭐put 流程

4.1 hash 计算

put 函数实际上调用的是 putVal 函数，但是在调用 putVal 函数之前，需要通过 hash 函数得到 key 的散列值。如果 key 不为 null，就会进行如下的位运算 (h = key.hashCode() ^ (h >>> 16)。hash 函数的作用是对 key 的 hashCode() 进行二次哈希处理，减少低 bit 位冲突，该操作的意思是将 hashCode 的高 16 位与低 16 位异或，然后再通过 (n - 1) & hash 得到该键值对应的数组下标。

4.2 插入逻辑

得到要插入的下标之后，根据是不是空桶进行不同的处理：

情况一：空桶

  • 如果要插入的目标桶为空，就会直接 newNode

情况二：非空桶

  • 如果桶中已经存在元素，且如果是红黑树，则会调用 putTreeVal 方法
  • 如果只是普通链表，会用尾插法在链表尾部插入元素
  • 同时检查是否达成树化的条件，如果满足树化的条件(链表⻓度大于等于 8，而且数组容量大于等于 64)，会将链表转换为红黑树，调用 treeifyBin 函数树化
  • 如果找到相同键的节点，会覆盖旧值

情况三：扩容检查

  • 最后检查是不是大于阈值(默认是 0.75)，如果大于阈值，最后要调用 resize 函数扩容
  • 需要注意的是，如果 table 没有初始化或者长度为 0，在一开始的时候就会调用 resize 函数进行扩容操作

4.3 put 流程总结

HashMap 的 put 流程大致分为几步：

  1. 首先对 key 做 hash 扰动，然后定位到数组中的桶
  2. 如果桶为空，直接插入
  3. 如果桶不为空，就在桶内处理冲突：
    • key 相同则覆盖
    • 否则在链表或红黑树中插入
  4. 当链表长度超过 8 且数组长度 ≥ 64 时，会转成红黑树
  5. 插入完成后，如果元素个数超过阈值，就会触发扩容

4.4 索引计算与比较

桶索引计算 → 快速找到候选桶

  • 链表/树遍历 → 先比 hash 再比 equals → 快速过滤 + 保证正确性
  • hash != equals → hash 只是一个 int，可能冲突，equals 才判断逻辑相等
  • 性能优化 → hash int 比较比调用 equals 快

换句话说：

  • index 是”候选范围”
  • hash 是”初步过滤”
  • equals 才是”最终判定”

4.5 为什么 hashcode 和 equals 都要比较

hashmap在put键值对的时候比较键是否相等为什么hashcode(key)和equals(key)都要比一下？

同一个桶下面的链表节点或者树节点是hash值对数组长度取余结果相同，但不一定hash值相等，比如 3 % 5 == 8 % 5，结果都是3，但一个hash值是3一个是8，所以他们位于同一桶下但hash值不同，所以还需要再比较一下。

五、null 值处理

5.1 HashMap vs HashTable

HashMap

  • HashMap 的 key 是可以为 null 的
  • 因为 HashMap 在 key 为 null 的时候，会将 key 的 hash 值设置为 0，解决了走 hashCode 方法导致空指针异常的问题

HashTable

  • HashTable 的 key 是不能为 null 的
  • 因为 HashTable 会直接走 hashCode 方法，当 key 为 null 的时候就会出现空指针异常

六、⭐扩容机制

6.1 扩容触发条件

HashMap扩容主要使用的是resize方法，一般发生在table未初始化和数组元素超出阈值的时候。

6.2 扩容倍数与原理

扩容每次扩大两倍，之所以每次都扩大两倍是因为这样省去了重新计算hash值的时间，因为我们只需要看新增的那个bit位的值是0还是1就行了，是0的话就不动，如果是1的话索引就变为原索引+ oldCap

这里注意一下 hash % length == hash & (length-1)，HashMap就是通过这种方式将之前冲突的节点再次打散的（在得到节点index的时候会使用到这个小技巧）

6.3 扩容流程总结

HashMap 的扩容通过 resize 方法完成，一般发生在 table 未初始化或 size 超过 threshold 时。

扩容时容量会扩大为原来的 2 倍，这是为了避免重新计算 hash。

在 JDK8 中，不再重新算索引，而是通过 (hash & oldCap) 判断节点是否需要移动：

  • 为 0 的节点仍然放在原索引
  • 为 1 的节点移动到 原索引+ oldCap

这样可以把原来一个桶里的链表拆成低位链表和高位链表，提高扩容效率。

6.4 两个位运算的区别

hash & (length - 1)

  • 用于定位数组下标，算桶位置的

hash & oldCap

  • 只在扩容时使用，用来判断节点是否需要迁移，避免重新计算 hash

6.5 低位链表和高位链表

低位链表

  • 包含那些哈希值与当前扩容位掩码（bit）按位与结果为0的节点
  • 这些节点会被分配到新数组的原索引位置（index）

高位链表

  • 包含那些哈希值与当前扩容位掩码（bit）按位与结果为1的节点
  • 这些节点会被分配到新数组的新索引位置(index+bit）

6.6 JDK 7 vs JDK 8 扩容差异

大致的扩容流程可以分为：

重新计算索引的位置

  • 在 JDK7 中需要重新计算索引的位置
  • 在 JDK8 中，充分应用了哈希值，用 & 的位是不是 1 来判断要不要移动

选用插入的方法

  • 在 JDK7 中采用的是头插法，在并发场景下容易出现链表成环的 Bug
  • 在 JDK8 中修复了这一点，采用了尾插法

当然了 HashMap 具体的扩容代码以及相关流程还是要记得的，当 size(当前 Map 大小) 超过临界阈值 threshold(阈值) 的时候，会进行扩容，调用 resize() 方法，创建一个大小为之前两倍的 table，并通过惰性传输完成赋值操作

6.7 扩容总结

HashMap 扩容发生在 size 超过临界阈值 threshold 时，会调用 resize，将容量扩为原来的 2 倍。

在 JDK7 中，扩容时需要重新计算索引，并且采用头插法，在并发场景下可能导致链表成环；

JDK8 对此做了优化：

  • 通过 (hash & oldCap) 判断元素是否需要移动，避免重新计算 hash
  • 迁移时使用尾插法，解决了并发成环问题

七、⭐线程安全问题

7.1 JDK 7 - 头插法导致的死循环

问题描述

JDK7 的时候使用头插法，在多线程的环境下，可能扩容的时候会出现环形链表，形成死循环。

原理分析

两个线程扩容传递的是两个新的 table，原来是 ABC，t1 扩容完成变成了 CBA，此时 t2 接着迁移对象遍历原来 ABC，遍历到 C 的时候发现 C 的 next 节点是 B，这样一直循环，这才叫死循环(主要是要理解两个线程对节点的引用是相同的)

注意：环不是因为 B->A, A->null 本身有环，而是两个线程同时修改节点 next 指针，形成交叉引用

为什么使用头插法

JDK 7（HashMap）使用头插法，主要原因不是为了插入效率，而是方便在扩容时直接迁移旧节点，避免多余遍历。

JDK7 使用头插法并不是为了插入效率，而是为了在扩容时方便迁移节点到新 table，不需要遍历链表找到尾部，从而保持扩容性能O(n^2)。

JDK8 改为尾插法，主要是为了避免多线程扩容导致的环形链表死循环，并保持插入顺序。

7.2 JDK 8 - 尾插法的数据丢失问题

数据丢失场景

JDK8 的时候使用尾插法，避免了 JDK7 的环形链表问题，但是还是有多线程 put，导致数据丢失的问题。

比如有两个线程 A 和 B，首先 A 希望插入一个 key-value 对到 HashMap 中，首先计算记录所要落到的 hash 桶的索引坐标，然后获取到该桶里面的链表头结点时线程 A 的时间片用完了。而此时线程 B 被调度得以执行，和线程 A 一样执行，只不过线程 B 成功将记录插到了桶里面，假设线程 A 插入的记录计算出来的 hash 桶索引和线程 B 要插入的记录计算出来的 hash 桶索引是一样的，那么当线程 B 成功插入之后，线程 A 再次被调度运行时，它依然持有过期的链表头但是它对此一无所知。以至于它认为它应该这样做如此一来就覆盖了线程 B 插入的记录，这样线程 B 插入的记录就凭空消失了

红黑树的死循环问题

尾插法也有死循环的问题。在 JDK 8 中，当链表长度超过 8 时，链表会被转换为红黑树。在红黑树的插入和平衡操作中，如果多个线程同时对同一个红黑树进行操作，可能会导致红黑树的结构被破坏，从而形成环形结构。例如，balanceInsertion 方法和 root 方法中都可能出现死循环(相互引用不为 null)。

具体可以这样排查：dump 下来堆内存信息，通过 jhat 命令生成 html 的内存信息页面。由于红黑树细节过于复杂，这里不讨论到底是怎么出现死循环的，记住这个 Bug 就行了。

JDK 8 的 HashMap 在多线程的情况下也会出现死循环的问题，但是是在链表转换树或者对树进行操作的时候会出现线程安全的问题

7.3 线程安全问题总结

JDK 7

  • 在 JDK 7 中，HashMap 在多线程环境下由于 resize 过程中使用头插法，可能导致链表反转，从而形成环形链表并引发死循环。

JDK 8

  • JDK 8 中改为尾插法，避免了 resize 时链表反转的问题，因此不再出现 JDK 7 中那种典型的环形链表死循环。但这并不意味着 HashMap 变成线程安全的。
  • 在 JDK 8 中，HashMap 仍然是非线程安全的。在多线程并发 put 时，可能发生数据丢失问题：一个线程读取到桶中的旧头结点并准备插入元素，而在它挂起期间，另一个线程已经完成了插入操作。当前线程恢复执行后，仍然基于过期的链表头进行写回，从而覆盖掉其他线程插入的节点，导致数据丢失。
  • 此外，当链表长度超过阈值（默认 8）并转换为红黑树后，如果多个线程同时对同一个桶中的红黑树进行插入、旋转或平衡操作，由于缺乏同步机制，可能导致红黑树结构被破坏，出现指针异常甚至死循环。这种问题通常表现为 CPU 100%，可通过堆转储分析 TreeNode 的引用关系进行排查。

结论

  • 因此，无论是 JDK 7 还是 JDK 8，HashMap 都不应在多线程环境下使用，应使用 ConcurrentHashMap 等线程安全的替代方案。
  • JDK 8 解决了 HashMap 在 resize 时的结构性死循环问题，但并没有解决并发安全问题，多线程 put 仍可能导致数据丢失，甚至在树化阶段引发更隐蔽的死循环。

八、手撕 HashMap

8.1 测试用例

1
2
3
4
5
6
7
8
9
10
11
12
@Test
void test3() {
    MyHashMap<String, Integer> myHashMap = new MyHashMap<>();
    myHashMap.put("a", 1);
    myHashMap.put("b", 2);
    myHashMap.put("c", 3);
    System.out.println(myHashMap.get("a"));
    System.out.println(myHashMap.get("b"));
    System.out.println(myHashMap.get("c"));
    myHashMap.remove("b");
    System.out.println(myHashMap.get("b"));
}

8.2 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class MyHashMap<K, V> {
    private Node[] table;
    private int size;
    private static final int DEFAULT_CAPACITY = 16;
    
    class Node<K, V> {
        K key;
        V value;
        final int hash;
        Node<K, V> next;
        
        Node(K key, V value, int hash) {
            this.key = key;
            this.value = value;
            this.hash = hash;
        }
    }
    
    private int hash(K key) {
        if (key == null) return 0;
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
    
    public V get(K key) {
        int hash = hash(key);
        int index = hash & (table.length - 1);
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }
    
    public V put(K key, V value) {
        int hash = hash(key);
        int index = hash & (table.length - 1);
        Node<K, V> node = table[index];
        
        if (node == null) {
            table[index] = new Node<>(key, value, hash);
            size++;
            return null;
        }
        
        Node<K, V> curr = node;
        while (true) {
            if (curr.key.equals(key)) {
                V old = curr.value;
                curr.value = value;
                return old;
            }
            if (curr.next == null) {
                break;
            }
            curr = curr.next;
        }
        curr.next = new Node<>(key, value, hash);
        size++;
        return null;
    }
    
    public V remove(K key) {
        int hash = hash(key);
        int index = hash & (table.length - 1);
        Node<K, V> curr = table[index];
        V value = curr.value;
        Node<K, V> prev = null;
        
        while (curr != null) {
            if (curr.key.equals(key)) {
                if (prev == null) {
                    table[index] = curr.next;
                } else {
                    // 删的是中间节点
                    prev.next = curr.next;
                }
                size--;
                return value;
            }
            prev = curr;
            curr = curr.next;
        }
        
        return null;
    }
    
    public MyHashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }
    
    public boolean containsKey(K key) {
        int hash = hash(key);
        int index = hash & (table.length - 1);
        Node curr = table[index];
        while (curr != null) {
            if (curr.hash == hash && curr.key.equals(key)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }
}

九、扩展 - HashTable

9.1 数据结构

底层使用的是 数组 + 链表，效率更低

9.2 初始化

HashTable 的默认容量是 11，默认的负载因子也是 0.75 和 HashMap 一样

9.3 线程安全

HashTable 是线程安全的，但是方法都加上了 synchronized，性能不是很高

9.4 null 值处理

HashTable 不能存储 key 或 value 为 null 的数据，因为 HashTable 在 put 的时候，会先检查 value 是不是为 null，如果为 null 就会抛出空指针异常，key 不能为 null 是因为 HashTable 对于这种情况没有特殊处理，直接通过 key.hashCode() 来获取 hash 值，所以一旦 key 为 null，就会报空指针异常

9.5 扩容

与 HashMap 不同的是，HashTable 每次扩容的大小为原来的 2n + 1 。值得注意的是，HashTable 没有惰性初始化，在构造方法创建对象的时候，会直接初始化数组

十、扩展 - ConcurrentHashMap

10.1 ⭐数据结构

核心对比

  • JDK7 = 多个小 HashMap（Segment）+ 锁段
  • JDK8 = 单个大 HashMap + CAS/节点锁，高并发更灵活

JDK 7 结构

JDK7 的时候使用的是数组加链表的方式。

特点：分段锁 → 并发写受 segment 数量限制

1
2
3
ConcurrentHashMap
└── Segment[] segments   （每个 segment 是一个小型 HashMap + 锁）
    └── HashEntry[] table  （每个 segment 内部的桶数组 + 链表）

JDK 8 结构

JDK8 的时候使用的是数组加链表/红黑树的方式。

特点：CAS + 局部加锁 → 更高并发，去掉 segment

1
2
ConcurrentHashMap
└── Node[] table  （单个数组 + 链表 / 红黑树）

10.2 ⭐线程安全

JDK 7 - 分段锁

ConcurrentHashMap 是多个 HashMap 组成，每一个 HashMap 是一个 segment，就如传说中一样，ConcurrentHashMap 使用分段锁的方式，这个”段”就是 segment。

ConcurrentHashMap 之所以能够保证并发安全，是因为支持对不同 segment 的并发修改操作，比如两个线程同时修改 ConcurrentHashMap，一个线程修改第一个 segment 的数据，另一个线程修改第二个 segment 的数据，两个线程可以并发修改，不会出现并发问题；但是多个线程同一个 segment 进行并发修改，则需要先获取该 segment 的锁后再修改，修改完后释放锁，然后其他要修改的线程再进行修改。

那么，ConcurrentHashMap 可以支持多少并发量（写）呢？这个也就是问，ConcurrentHashMap 最多能支持多少线程并发修改，其实也就是 segment 的数量，只要修改 segment 的这些线程不是修改同一个 segment，那么这些线程就可以并行执行，这也就是 ConcurrentHashMap 的并发量（segment 的数量）。

JDK 8 - CAS + 局部锁

ConcurrentHashMap 主要是通过原子操作和局部加锁保证了线程安全和 CopyOnWriteArraylist 一样，节点数组使用 volatile 修饰，保证了节点数组在多线程环境下的可见性

10.3 ⭐扩容

JDK 7 扩容

注意，ConcurrentHashMap 创建完成后，也就是 segment 的数量、并发级别已经确定，则 segment 的数量和并发级别都不能再改变了，即使发生扩容，也是 segment 中的 table 进行扩容，segment 的数量保持不变

特点

  • 扩容只是 Segment 内部 table 的扩容
  • 并发度 = Segment 数量，永远固定

JDK 8 扩容

特点

  • 扩容是整个 Node[] table 的扩容
  • 不存在 Segment，并发度更高
  • 扩容可由多线程协助完成，效率高

10.4 ⭐put 操作

共同点

相较于 HashMap，ConcurrentHashMap 和 HashTable 一样，都不允许 key 和 value 为 null，如果为 null，会抛出空指针异常

总结

  • JDK7 的 ConcurrentHashMap 用 Segment + HashEntry，锁粒度大并发受限
  • JDK8 去掉 Segment，使用 CAS + 节点级 synchronized + 链表/红黑树，锁粒度更小，并发度更高，插入操作先尝试 CAS 自旋落槽，冲突多时再加锁处理

JDK 7 put 流程

通过源码我们可以看到，和 HashMap 一样，ConcurrentHashMap 调用 put 方法底层调用的也是 putVal 方法。

JDK7 时候的 ConcurrentHashMap 使用的是分段锁 segment，每个 segment 就有一个 HashEntry 数组。在 JDK7 中，ConcurrentHashMap 是由 Segement 数组和 HashEntry 数组构成的，也就是桶 + 链表的结构，Segement 是一种可重入锁 ReentrantLock，HashEntry 用于存储实际的键值对数据，就是 HashMap 中的 Node，每个 Segement 守护一个 HashEntry 数组中的元素，要对 HashEntry 数组中的数据进行修改的时候，必须先获取到它对应的 Segement 锁

JDK 8 put 流程

虽然比 HashTable 和 SynchronizedMap 锁整个数组对象要好，但是在 JDK8 中，对该策略进行了进一步的优化，将锁的对象从小数组变为了节点，锁的粒度进一步降低，并发度变的更高了，除此之外 JDK8 的 ConcurrentHashMap 还带来了 CAS + synchronized 的设计。

ConcurrentHashMap 做插入操作的时候是在死循环中进行的，插入的时候有四种情况：

第一种情况

  • 如果数组为空，没有被初始化，这时会调用 initTable 函数进行初始化操作

第二种情况

  • 如果数组已经被初始化，而且要插入的节点为 null，会调用 casTabAt 函数尝试通过 CAS 进行插入

第三种情况

  • 如果节点的 hash 值为 -1 也就是 tab 的状态为 MOVED，表示数组正在扩容，会先调用 helpTransfer 函数协助扩容

第四种情况

  • 直接对节点进行加锁，通过 synchronized 锁住整个代码快，这部分代码和 HashMap 类似，分为链表处理和红黑树处理

原理总结

简单的说，如果一开始计算出的 Hash 槽没有数据，为 null，说明没有大量的线程访问，竞争较小，所以会使用 CAS 自旋来完成落槽操作，如果计算出的 Hash 槽中是有数据的，说明发生了 Hash 碰撞，这时竞争比较激烈，使用 synchronized 来处理的效率比用 CAS 来处理的效率要高

关键概念

  • 原子操作 = CAS，适合低竞争空桶，保证插入不会被打断
  • 局部加锁 = synchronized 某个节点/桶，而不是锁整个 HashMap，适合冲突多的情况，保证链表或红黑树操作正确
  • 结合 volatile → 保证修改对所有线程可见

十一、扩展 - Set

11.1 ⭐数据结构

Set 集合中不会出现重复的元素，集合中的元素都是唯一的，Set 集合底层是基于 Hash 表存储的，比如我们在使用 HashSet 的时候，会发现它的构造函数是 new 了一个 HashMap，往 Set 集合中存储数据，其实就是往 Map 成员变量中添加对应的 key 和 value，不过 value 是一个默认参数 PRESENT，是一个虚拟的 Object 对象，而且 HashSet 中的 API 底层基本都是调用 HashMap 的方法

11.2 手撕 HashSet

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Test
void test4() {
    MyHashSet<String> set = new MyHashSet<>();
    set.add("A");
    set.add("B");
    set.add("C");
    set.add("A"); // 重复元素不会加入
    
    System.out.println("set contains A? " + set.contains("A"));
    System.out.println("set contains D? " + set.contains("D"));
    
    System.out.println("set: " + set);
    
    set.remove("B");
    System.out.println("after remove B: " + set);
}

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyHashSet<E> {
    private final MyHashMap<E, Object> map;
    private static final Object PRESENT = new Object();
    
    public MyHashSet() {
        map = new MyHashMap<>();
    }
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    public boolean remove(E e) {
        return map.remove(e) == PRESENT;
    }
    
    public boolean contains(E e) {
        return map.containsKey(e);
    }
}

11.3 扩展 - LinkedHashSet 和 TreeSet

有序的 Set 是什么？记录插入顺序的集合是什么？

虽然我们的 HashSet 是无序的，但是不代表我们的 Set 是不能保证有序的

LinkedHashSet

我们先来分析一下 LinkedHashSet，该类会继承 HashSet

构造方法调用的是父类的构造方法，这个构造方法使用了 LinkedHashMap 来初始化 HashSet 中的 map

所以实际上底层是使用 LinkedHashMap 来存储元素的

这里顺便解释一下 LinkedHashMap 的源码

LinkedHashMap 继承自 HashMap，在 HashMap 的基础上维护了一条双向链表，该链表的每一个节点都有前驱引用和后驱引用，以插入过程来说，本质上还是使用的是 HashMap 的 put 方法，但是重写了 newNode 方法，同时新增了 linkNodeLast 方法，将 Entry 接在双向链表的尾部

TreeSet

当然，除了 LinkedHashSet，还有 TreeSet 也可以保证 Set 的有序性

HashSet 底层是通过 HashMap 实现的，TreeSet 底层是通过 TreeMap 实现的，TreeMap 底层是使用红黑树实现的，和 HashSet 与 LinkedHashSet 不同，TreeSet 容器存储数据是靠 NavigableMap 接口实现的，同样的，这里也有 PRESENT 作为默认的 value，之所以要用 PRESENT 不用 null 是要判断是否插入成功，是因为如果使用的是 null，那么就算是插入失败也会返回 true，表示插入成功，构造器自然使用的是 TreeMap，实际的 API 调用的大多也是 TreeMap 的方法

注意

在 Java 中，有序无序指的是插入的时候是否维护了插入的顺序，当遍历的时候是否会按照插入顺序展示，但是排序不同，比如 TreeMap，虽然是可排序的，但是实际上是无序的

总结

  • LinkedHashSet 通过 LinkedHashMap 维护元素的插入顺序，因此遍历时是插入有序的。
  • TreeSet 底层基于 TreeMap 的红黑树结构，遍历时按照元素的排序规则输出，因此是排序有序的，但不保证插入顺序。
  • Java 中的 Set 是否”有序”，取决于遍历顺序是否可预测。LinkedHashSet 保证插入顺序，TreeSet 保证排序顺序，而 HashSet 两者都不保证。