一、核心概念与底层原理

1. HashMap

概念
基于哈希表的Map接口实现，允许null键/值，非线程安全，元素无序存储。

底层实现（JDK8+）

• 数组+链表+红黑树结构
• 默认初始容量16，负载因子0.75
• 链表长度≥8且数组长度≥64时，链表转为红黑树
• 哈希冲突通过链地址法解决

java

// 典型桶结构
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;  // 链表指针
}

2. LinkedHashMap

概念
HashMap的子类，通过双向链表维护元素插入顺序或访问顺序。

底层实现

• 继承HashMap的数组结构
• 添加before和after指针维护链表
• 支持两种排序模式：
• 插入顺序（默认）
• 访问顺序（LRU缓存基础）

java

static class Entry extends HashMap.Node {
    Entry before, after;  // 新增双向指针
}

3. ConcurrentHashMap

概念
线程安全的哈希表，支持高并发读写，JDK8后放弃分段锁设计。

底层实现（JDK8+）

• CAS + synchronized锁细化
• 数组+链表+红黑树结构
• 使用volatile保证可见性
• 并发控制粒度到桶级别

java

// 使用Unsafe类进行原子操作
static final  Node tabAt(Node[] tab, int i) {
    return (Node)U.getObjectVolatile(tab, i);
}

4. ArrayList

概念
基于动态数组的可调整大小列表，支持快速随机访问。

底层实现

• Object[]数组存储元素
• 默认初始容量10
• 扩容机制：新容量 = 原容量 + 原容量 >> 1（约1.5倍）
• System.arraycopy()实现数组拷贝

5. LinkedList

概念
基于双向链表的列表实现，支持高效插入/删除操作。

底层实现

• Node节点构成双向链表
• 每个节点包含前驱/后继指针

java

private static class Node {
    E item;
    Node next;
    Node prev;
}

二、核心区别对比

1. Map系列对比

2. List系列对比

三、使用场景指南

1. Map系列选择

• HashMap
• 快速键值查找
• 不要求顺序的缓存
• 单线程环境统计词频
• LinkedHashMap
• 需要保持插入顺序（如配置项加载）
• 实现LRU缓存（设置accessOrder=true）
• ConcurrentHashMap
• 高并发缓存（如商品库存计数）
• 替代Hashtable的多线程场景

2. List系列选择

• ArrayList
• 频繁随机访问（如按索引获取元素）
• 数据量相对固定的集合
• 需要空间局部性优化的场景
• LinkedList
• 频繁在头尾增删元素（队列/栈实现）
• 需要实现双向遍历
• 内存敏感场景（避免数组扩容）

四、性能优化要点

1. Map优化实践

• 设置合理的初始容量（减少扩容）
• 避免hashCode()冲突过多
• 使用ConcurrentHashMap替代Collections.synchronizedMap()

2. List优化实践

• ArrayList预分配足够容量
• 使用LinkedList时优先操作头尾节点
• 批量操作使用addAll()

五、常见误区解析

1. "LinkedList插入一定比ArrayList快"
   仅在头尾插入时成立，中间插入需要遍历到指定位置
2. "ConcurrentHashMap完全无锁"
   JDK8后仍使用synchronized锁单个桶，但锁粒度更细
3. "HashMap线程不安全仅指数据丢失"
   还包括可能导致闭环链表（JDK7头插法问题）

六、选择原则：

• 读多写少选ArrayList
• 频繁增删选LinkedList
• 常规映射用HashMap
• 需要顺序用LinkedHashMap
• 高并发选ConcurrentHashMap

通过理解底层实现机制，开发者可以根据具体场景选择最优数据结构，在性能与功能之间达到最佳平衡。