一、List 接口实现类

1. ArrayList

底层结构：动态数组（Object[]数组）。

核心原理：

o 动态扩容：初始容量为10（JDK 1.8），当元素超过容量时，新容量为原容量的1.5倍（oldCapacity + (oldCapacity >> 1)），通过Arrays.copyOf复制数组。

o 扩容时机：添加元素时检查容量，若不足则触发扩容。

o 随机访问：时间复杂度O(1)，通过数组下标直接访问。

o 插入/删除：O(n)，需移动后续元素（尾部插入/删除除外）。

o fail-fast机制：通过modCount记录修改次数，遍历时若发现修改则抛出
ConcurrentModificationException。

2. LinkedList

底层结构：双向链表（每个节点包含前驱和后继指针）。

核心原理：

o 节点结构：Node<E> { E item; Node<E> next; Node<E> prev; }。

o 插入/删除：O(1)，只需修改指针指向，无需移动元素（需先定位节点，定位时间复杂度O(n)）。

o 随机访问：O(n)，需从头或尾遍历链表。

o 特殊优化：实现了Deque接口，可作为栈或队列使用，头尾操作效率高。

二、Map 接口实现类

1. HashMap（JDK 1.8）

底层结构：数组 + 链表 + 红黑树。

核心原理：

o 哈希函数：通过key.hashCode()计算哈希值，再通过(n-1) & hash映射到数组下标（n为数组长度，必须是2的幂次）。

o 冲突解决：

o 链表法：同一哈希桶内的元素用链表存储。

o 红黑树优化：当链表长度≥8且数组容量≥64时，链表转为红黑树（查询时间从O(n)降为O(log n)）。

o 扩容机制：

o 负载因子默认为0.75，当元素个数≥数组长度×负载因子时触发扩容。

o 新容量为原容量的2倍，需重新计算所有元素的哈希位置（JDK 1.8优化了扩容算法，采用“高低位分组”减少迁移次数）。

o 线程不安全：多线程下可能出现链表成环、数据丢失等问题。

2. ConcurrentHashMap（JDK 1.8）

底层结构：数组 + 链表 + 红黑树（与HashMap类似，但线程安全）。

核心原理：

o 锁优化：

o JDK 1.7：分段锁（Segment数组，每个Segment是一个ReentrantLock）。

o JDK 1.8：取消Segment，采用CAS + synchronized，锁粒度更小（锁在哈希桶的头节点）。

o 红黑树转换：与HashMap相同，但并发环境下通过CAS保证树结构的一致性。

o 扩容机制：支持并发扩容，通过transfer方法将元素迁移到新数组，避免单线程阻塞。

o 读操作无锁：通过volatile保证数组和节点的可见性，读操作无需加锁。

3. TreeMap

底层结构：红黑树（自平衡二叉搜索树）。

核心原理：

o 红黑树性质：节点非红即黑，根节点为黑，红节点子节点必为黑，任意路径黑节点数相同。

o 排序规则：通过compareTo或自定义Comparator排序。

o 操作复杂度：插入、删除、查找均为O(log n)，因红黑树保持平衡。

o 有序性：天然支持按key排序，可通过firstKey()、lastKey()等方法获取边界元素。

三、Set 接口实现类

1. HashSet

底层结构：基于HashMap实现，key存储元素，value为固定对象PRESENT。

核心原理：

o 利用HashMap的哈希算法实现去重（key不可重复）。

o 插入、查找时间复杂度为O(1)（平均情况），依赖HashMap的性能。

o 线程不安全，可通过
Collections.synchronizedSet包装。

2. TreeSet

底层结构：基于TreeMap实现，key存储元素，value为固定对象PRESENT。

核心原理：

o 利用TreeMap的红黑树结构实现有序去重，元素需可比较（实现Comparable或提供Comparator）。

o 插入、查找时间复杂度为O(log n)，支持按顺序遍历。

四、队列与栈

1. LinkedList 作为队列/栈

o 队列（FIFO）：通过offer()入队，poll()出队，基于链表头尾操作实现。

o 栈（LIFO）：通过push()入栈，pop()出栈，本质是链表的尾插尾取。

2. ArrayBlockingQueue

底层结构：固定大小的数组 + 两把锁（takeLock和putLock） + 两个条件变量（notEmpty和notFull）。

核心原理：

o 基于ReentrantLock实现线程安全，通过条件变量实现阻塞等待（入队满时等待，出队空时等待）。

o 插入和删除操作均需获取对应锁，保证线程安全。

3. PriorityQueue

底层结构：小顶堆（数组实现的完全二叉树）。

核心原理：

o 堆顶元素为最小元素（默认），插入时通过shiftUp上浮调整，删除时通过shiftDown下沉调整。

o 插入、删除时间复杂度为O(log n)，查找堆顶为O(1)。

o 不支持线程安全，需配合
Collections.synchronizedQueue使用。

五、其他重要数据结构

1. 红黑树（Red-Black Tree）

o 平衡策略：通过颜色标记和旋转（左旋、右旋）保证树高不超过2log(n+1)，避免退化为链表。

o 应用场景：TreeMap、TreeSet、JDK 1.8后的HashMap。

2. 跳表（SkipList）

o Redis中的实现：通过多层索引提高查询效率，插入、查找时间复杂度为O(log n)。

o Java中的应用：ConcurrentSkipListMap和ConcurrentSkipListSet，通过原子操作实现线程安全。

六、面试高频问题总结

1. HashMap vs ConcurrentHashMap：

o HashMap线程不安全，适合单线程；ConcurrentHashMap通过锁优化支持高并发。

o JDK 1.8后ConcurrentHashMap用synchronized替代Segment，性能更好。

2. ArrayList vs LinkedList：

o ArrayList适合随机访问，LinkedList适合频繁插入删除。

o ArrayList扩容需复制数组，LinkedList无扩容开销。

3. 红黑树为什么比平衡二叉树效率高？

o 平衡条件更宽松（弱平衡），插入/删除时旋转次数更少，性能更优。

4. HashMap的哈希冲突如何解决？为什么链表长度超过8转红黑树？

o 哈希冲突通过链表解决，转红黑树是为了避免极端情况下链表过长导致查询效率下降（概率统计显示，链表长度超过8的概率极低，优化性价比高）。

掌握这些原理后，还需结合具体场景分析数据结构的选择，例如：

o 高并发读多写少场景选ConcurrentHashMap；

o 需要有序性选TreeMap/TreeSet；

o 频繁头尾操作选LinkedList或Deque实现。

面试中若能结合源码细节（如扩容算法、锁机制）讲解，会更具说服力。