一、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实现。
面试中若能结合源码细节（如扩容算法、锁机制）讲解，会更具说服力。