1、HashMap 概述
HashMap 是 Map 接口的一种非同步实现，基于哈希表构建。它支持所有可选的映射操作，允许使用 null 值和 null 键。HashMap 不保证映射顺序，特别是不保证顺序始终不变。
2、HashMap 数据结构
HashMap 本质上是一种“链表散列”数据结构，结合了数组和链表。
HashMap 实现基于 Hash 算法：
– 当将元素放入 HashMap 时，使用键的哈希码重新哈希计算出该元素在数组中的索引。
– 存储时，如果出现哈希值相同的键，有两种情况：
– 如果键相同，则覆盖原始值。
– 如果键不同（出现冲突），则将当前键值对放入链表。
– 获取时，直接找到哈希值对应的索引，再进一步判断键是否相同，从而找到对应值。
– 理解以上过程有助于了解 HashMap 如何解决哈希冲突问题。它使用数组存储方式，并将冲突键的对象放入链表中。一旦发现冲突，就在链表中进一步比较。
需要注意：在 JDK 1.8 中，对 HashMap 进行了优化。当链表中的节点数据超过八个，且数组元素超过 64 时，该链表会转换为红黑树，以提高查询效率，从原来的 O(n) 优化到 O(logn)。
3、集合类主要实现
ArrayList
ArrayList 是容量可变的非线程安全列表，使用数组实现。扩容时会创建更大的数组并复制原有元素。支持对元素的快速随机访问，但插入和删除速度很慢。ArrayList 实现了 RandomAccess 标记接口，表示使用索引遍历比迭代器更快。
“`java
private transient Object[] elementData; // transient 修饰，序列化时不写入流
private int size; // 当前实际大小
private int modCount; // 记录结构性变化次数，用于 fail-fast 机制
“`
LinkedList
LinkedList 本质上是双向链表，与 ArrayList 相比，插入和删除速度更快，但随机访问元素很慢。除了继承 AbstractList，还实现了 Deque 接口，具有队列和栈的特性。成员变量被 transient 修饰，原理与 ArrayList 类似。
“`java
private transient int size = 0; // 节点数量
private transient Node first; // 首节点引用
private transient Node last; // 尾节点引用
“`
Set
Set 不允许元素重复，不保证元素有序。常见实现有 HashSet、LinkedHashSet 和 TreeSet。
HashSet
HashSet 通过 HashMap 实现，HashMap 的 Key 即 HashSet 存储的元素，所有 Key 都使用相同的 Value（PRESENT 常量）。使用 Key 保证元素唯一性，但不保证有序性。由于 HashSet 是 HashMap 实现的，因此线程不安全。
“`java
Map map;
“`
LinkedHashSet
LinkedHashSet 继承自 HashSet，通过 LinkedHashMap 实现，使用双向链表维护元素插入顺序。
TreeSet
TreeSet 通过 TreeMap 实现。添加元素时按照比较规则插入合适位置，保证有序性。
“`java
private transient NavigableMap m;
“`
TreeMap
TreeMap 基于红黑树实现，增删改查平均和最差时间复杂度均为 O(logn)。Key 必须实现 Comparable 接口或提供比较器。
“`java
private transient Entry root;
private transient int size = 0;
“`
HashMap 实现细节
JDK 8 之前：数组 + 链表
JDK 8：数组 + 链表/红黑树
“`java
private Node[] table; // 存储数据的数组
private transient int size; // 元素数量
private float loadFactor; // 加载因子
“`
table 数组记录 HashMap 的数据，每个下标对应一条链表。哈希冲突的数据存储在同一条链表上。Node/Entry 节点包含键、值、下一个指针和哈希值。
键的哈希值用来计算数组下标，如果哈希值相同，就产生哈希冲突。为了提高查询效率，键的哈希值应尽可能分散。
HashMap 默认初始化容量为 16，扩容容量必须是 2 的幂次方，最大容量为 1<< 30，默认加载因子为 0.75。
JDK 7 问题
数据丢失：
– 并发赋值被覆盖
– 已遍历区间新增元素丢失
– 新表被覆盖
死循环：
– 扩展时，扩容使用头插法迁移元素，并发的 Entry next 指针修改导致死循环
JDK 8 改进
– 扩容时使用尾插法，不会产生死循环
– 仍可能丢失数据，可使用 ConcurrentHashMap 或 Collections.synchronizedMap 包装成同步集合