Java equals() 与 hashCode() 契约详解及容器类（List/Set/Map）核心整理 | 极客日志

Java equals() 与 hashCode() 契约详解及容器类（List/Set/Map）核心整理 | 极客日志

实现类	底层数据结构	核心特色
ArrayList	动态数组	1. 随机访问（索引）效率 O(1)，增删需移动元素（效率 O(n)）； 2. 线程不安全，适合查询多、增删少的场景。
LinkedList	双向链表（JDK1.7+ 取消循环）	1. 增删只需修改节点指针（首尾操作 O(1)），随机访问需遍历（O(n)）； 2. 实现了 Deque 接口，可作为队列/栈使用； 3. 线程不安全，适合增删多、查询少的场景。
Vector	动态数组	1. 与 ArrayList 类似，但所有方法加 synchronized 修饰； 2. 线程安全但效率低，已很少使用。
Stack	继承 Vector，动态数组	1. 后进先出（LIFO）； 2. 线程安全但效率低，推荐用 Deque（如 LinkedList）替代。

实现类	底层数据结构	核心特色
HashSet	基于 HashMap（存储在 key 中）	1. 哈希表（数组 + 链表 + 红黑树，JDK1.8+）实现； 2. 无序，添加/查询/删除效率平均 O(1)； 3. 线程不安全，需重写 equals() 和 hashCode() 保证唯一性。
LinkedHashSet	继承 HashSet，基于 LinkedHashMap	1. 哈希表 + 双向链表实现； 2. 有序（按插入顺序或访问顺序）； 3. 性能略低于 HashSet（需维护链表），线程不安全。
TreeSet	基于 TreeMap（红黑树）	1. 红黑树（自平衡二叉搜索树）实现； 2. 有序（自然排序或定制排序，需实现 Comparable 接口）； 3. 增删改查效率 O(logn)，线程不安全。

实现类	底层数据结构	核心特色
HashMap	哈希表（数组 + 链表 + 红黑树）	1. JDK1.8+：链表长度≥8 且数组长度≥64 时转红黑树； 2. 无序，允许1 个 null 键和多个 null 值； 3. 线程不安全，多线程需用 ConcurrentHashMap 替代。
LinkedHashMap	继承 HashMap，哈希表 + 双向链表	1. 维护插入顺序或访问顺序（accessOrder=true 时为 LRU 缓存）； 2. 性能略低于 HashMap，线程不安全。
TreeMap	红黑树	1. 按 key自然排序或定制排序； 2. 不允许 null 键（但允许 null 值）； 3. 增删改查效率 O(logn)，线程不安全。
Hashtable	哈希表（数组 + 链表，无红黑树）	1. 所有方法加 synchronized 修饰； 2. 线程安全但效率低，不允许 null 键/值； 3. 已过时，推荐用 ConcurrentHashMap。
ConcurrentHashMap	哈希表（数组 + 链表 + 红黑树）	1. JDK1.8+：用 CAS+synchronized（只锁链表/红黑树头节点）替代分段锁； 2. 线程安全，效率远高于 Hashtable； 3. 不允许 null 键/值，适合高并发场景。