别再背API了你只需要知道每种集合底层是个什么数据结构写在前面集合框架是面试的绝对重灾区。几乎每一场Java面试都会问到HashMap而HashMap一问就能问出你的水平——是停留在会用层面还是真的看过源码。这篇文章的核心就一句话Java集合框架就是一堆数据结构的封装。你把数据结构学明白了集合框架根本不用背。ArrayList就是动态数组LinkedList就是双向链表HashMap就是哈希表TreeMap就是红黑树。就这么简单。一、先搞清集合框架的顶层设计Java的集合框架分两大派系Collection体系存单个元素List有序、可重复 → 相当于排队Set无序、不可重复 → 相当于集合Queue队列 → 相当于排队办事Map体系存键值对HashMap哈希表实现无序TreeMap红黑树实现有序LinkedHashMap哈希表双向链表维护插入/访问顺序面试官常问“Collection和Collections有什么区别”Collection接口所有单列集合的根接口。Collections工具类提供了操作集合的静态方法排序、二分查找、线程安全包装等。二、ArrayList vs LinkedList数组 vs 链表这俩的区别是面试基础中的基础但很多人只知道ArrayList查快增删慢LinkedList增删快查慢——太笼统了面试官会追问具体场景。ArrayList 动态数组底层是个Object数组默认初始容量10满了就扩容1.5倍oldCapacity (oldCapacity 1)。随机访问快get(index)直接根据下标取O(1)。尾部插入快直接往数组末尾塞O(1)需要扩容时除外。中间插入/删除慢因为要把插入位置后面的元素全部往后/往前挪O(n)。LinkedList 双向链表每个节点存着前一个节点、后一个节点、以及数据。随机访问慢要从head或tail顺着链表找O(n)。头部/尾部插入删除快只改前后节点的指针就行O(1)。中间插入删除也快只要拿到了那个位置的节点改指针就行O(1)。但注意找这个位置本身需要O(n)。面试官追问“ArrayList中间插入真的比LinkedList慢吗”不一定。虽然理论上是O(n) vs O(1)但ArrayList的System.arraycopy是底层C语言实现的、经过极致优化的内存复制在元素数量不大时可能比LinkedList反复遍历指针操作更快。所以选型要看实际场景不能死背书。什么场景用哪个频繁随机访问 → ArrayList频繁头部/尾部操作 → 都可以ArrayList尾部插入很快频繁中间操作 数据量极大 → LinkedList但如果你既要中间插入又要随机访问可以考虑ArrayDeque或ConcurrentSkipListSet三、HashMap重中之重HashMap是面试的一号重灾区。你必须从底层数据结构说到扩容机制再说到线程安全问题。3.1 底层数据结构JDK 1.7及之前数组 链表头插法JDK 1.8及之后数组 链表 红黑树一个Node数组叫table每个位置叫桶bucket。存的时候算key的hash值对数组长度取模确定放到哪个桶里。多个key落到同一个桶时用链表串起来。链表什么时候转红黑树链表长度 ≥ 8且数组长度 ≥ 64 → 链表转红黑树红黑树节点数 ≤ 6 → 红黑树退化成链表为什么是8和6源码注释里写了链表的查找复杂度是O(n)红黑树是O(log n)。根据泊松分布链表长度达到8的概率只有千万分之六所以8是个阈值6是回退阈值中间差2防止频繁转换。3.2 put流程背下来但要说人话我用人话讲一遍你理解了就不用背计算key.hashCode()再高低位异或扰动函数让hash更散列。用(n - 1) hash算出应该放到数组的哪个位置相当于取模但位运算更快。如果这个位置是空的直接创建Node放进去。如果这个位置有东西了先判断这个位置的key是不是跟你要放的key相等hash相等且equals相等→ 是就覆盖value。如果不是判断是不是TreeNode红黑树节点→ 是就走红黑树的插入逻辑。如果不是TreeNode那就是链表 → 遍历链表看有没有相等的key有就覆盖没有就尾插JDK 1.8改成了尾插解决了1.7头插扩容死循环的问题。插入完成后如果链表长度 ≥ 8转红黑树。最后判断size是否超过了threshold容量 × 负载因子→ 超过了就扩容。3.3 扩容机制什么时候扩容当size capacity × loadFactor时扩容。默认capacity16loadFactor0.75所以当size 12时触发扩容。扩容成多大2倍。16 → 32 → 64 → 128……为什么是2倍因为计算桶位置用的是(n - 1) hashn是2的幂次方时n-1全是1hash (n-1)等价于hash % n但位运算更快。而且扩容后元素要么留在原位置要么移到原位置旧容量的位置不需要重新计算hash效率高。负载因子为什么是0.75还是权衡。0.75是时间和空间的平衡点。0.5哈希冲突少查询快但浪费一半空间。1.0空间利用率高但冲突多查询慢。0.75是基于大量实验统计出来的最优值。你改这个值唯一能改变的就是用空间换时间还是用时间换空间。3.4 线程安全问题HashMap线程不安全。具体表现JDK 1.7并发扩容时链表用头插法可能形成环形链表导致get死循环CPU飙到100%。JDK 1.8改用了尾插法环形链表问题解决了但仍有数据覆盖问题——两个线程同时put后一个可能覆盖前一个的值。那并发场景用什么ConcurrentHashMap分段锁1.7→ CAS synchronized1.8线程安全且效率高。Collections.synchronizedMap(new HashMap())全表锁性能差不推荐。Hashtable全表锁已淘汰。面试官追问“ConcurrentHashMap的size()准确吗”不准确。ConcurrentHashMap的size()返回的是个近似值因为它是通过遍历所有段累加的遍历过程中可能有新的数据进来所以不精确。如果你需要精确计数用LongAdder或维护单独的计数器。追问“ConcurrentHashMap在JDK 1.8中怎么保证线程安全的”put时如果桶为空用CAS把节点放进去无锁操作。如果桶不为空synchronized锁住桶的头节点然后操作链表或红黑树。get时不加锁直接用volatile保证可见性所以get是并发安全的且无锁。扩容时多个线程可以协同迁移数据每个线程负责一部分桶效率高。四、LinkedHashMapHashMap 双向链表LinkedHashMap继承自HashMap但多维护了一个双向链表记录了元素的插入顺序或访问顺序。两种模式插入顺序默认遍历时按插入顺序输出。访问顺序每访问一个元素get/put就把它移到链表末尾。这正是LRU最近最少使用缓存的底层实现。面试官问“怎么用LinkedHashMap实现一个LRU缓存”classLRUCacheK,VextendsLinkedHashMapK,V{privatefinalintmaxCapacity;publicLRUCache(intmaxCapacity){super(maxCapacity,0.75f,true);// true表示开启访问顺序this.maxCapacitymaxCapacity;}OverrideprotectedbooleanremoveEldestEntry(Map.EntryK,Veldest){returnsize()maxCapacity;// 超过容量就删除最老的头节点}}就这么简单。removeEldestEntry在每次put后调用返回true就删除最老的那个元素。五、TreeMap红黑树实现的有序MapTreeMap底层是红黑树自平衡二叉查找树所以它的key是有序的自然顺序或自定义Comparator。put、get、remove都是O(log n)。支持firstKey()、lastKey()、ceilingKey()、floorKey()等范围查找操作。红黑树是什么说白了就是二叉树 染色规则保证树不会退化成链表始终保持平衡。红黑树的五个性质面试可能会问节点是红色或黑色。根节点是黑色。所有叶子节点NIL是黑色。红色节点的两个子节点都是黑色即不能有连续的红节点。从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点。面试官追问“为什么TreeMap不用AVL树”因为红黑树的插入删除更快。AVL树要求更严格的平衡左右子树高度差不超过1插入删除后需要更多的旋转调整。红黑树只要求黑平衡旋转次数少插入删除性能好。查询多选AVL插入删除多选红黑树。六、HashSetHashMap套了个马甲HashSet底层就是HashMap只是value固定放了一个PRESENT占位对象。publicclassHashSetE{privatetransientHashMapE,Objectmap;privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;}}所以HashSet的无序、不可重复特性本质上就是HashMap的key的特性——key不能重复。TreeSet同理底层是TreeMap。七、Fail-Fast vs Fail-Safe遍历时能不能改集合Fail-Fast快速失败遍历一个集合时如果其他线程修改了集合结构增删或者在同一线程中用集合自身的修改方法会抛出ConcurrentModificationException。实现原理集合内部维护了一个modCount字段修改次数每次修改时1。迭代器在遍历时检查modCount是否变了变了就抛异常。哪些是Fail-FastArrayList、HashMap、HashSet……几乎所有的非并发集合。Fail-Safe安全失败遍历时修改集合不会抛异常。原理是迭代器操作的是集合的副本快照而不是原集合。哪些是Fail-SafeConcurrentHashMap的迭代器、CopyOnWriteArrayList的迭代器。八、补充几个面试冷门但爱考的8.1 hashCode和equals的约定再次强调两个对象equals相等 →hashCode必须相等。两个对象hashCode相等 →equals不一定相等哈希冲突。所以在HashMap的put过程中先算hashCode定位桶。再遍历桶里的链表用equals逐一比较找相等的key。如果key的hashCode相同但equals不同它们会放在同一个桶里用链表串着。8.2 HashMap允许null key吗允许。null key的hashCode被固定为0所以放在数组的第一个桶index0里而且只能有一个null key。8.3 ConcurrentHashMap允许null key吗不允许。为什么因为很多并发场景下null值的语义不明确——你存的null到底代表这个key对应的值是null还是这个key不存在而且ConcurrentHashMap的get方法在并发下无法区分key存在但value为null和key不存在这两种情况为了规避歧义干脆不允许。8.4 Arrays.asList()返回的List能增删吗不能。它返回的是Arrays的内部类ArrayList不是java.util.ArrayList它不支持add()和remove()。如果调用会抛UnsupportedOperationException。想变回可增删的ArrayList就new ArrayList(Arrays.asList(arr))。九、面试官真正想听什么集合框架的面试面试官考的不是背API而是数据结构选型和并发场景下的处理能力。场景1“你的系统有100万条数据需要频繁随机访问和尾部追加用什么”→ 果断ArrayList。LinkedList的随机访问是O(n)100万数据你不可能每次都从头遍历。场景2“需要频繁头部插入和删除用什么”→ 可以考虑ArrayDeque双端队列底层是数组但环形结构头部操作O(1)且没有LinkedList的节点开销。LinkedList也能用但内存占用更大。场景3“一个高并发系统需要用Map做缓存怎么选”→ 如果并发量大用ConcurrentHashMap。如果缓存需要淘汰策略可以考虑Caffeine本地缓存或Redis分布式缓存。场景4“你项目里有没有遇到过集合相关的线上问题”这才是真正的加分题。有就说“我们遇到过ConcurrentModificationException后来发现是遍历时用了remove()改成Iterator就好了。”“我们遇到过HashMap在1.7下CPU飙高排查发现是并发扩容导致的死循环后来换成ConcurrentHashMap解决了。”“我们遇到过在for循环里用ArrayList.remove()结果下标错乱的问题后来改用倒序遍历或Iterator。”没有实战经历就实话实说但要表明你的理论是完备的——“我知道这些坑我在代码里会注意避免。”小结集合底层特点常见面试点ArrayList动态数组查快改慢扩容1.5倍、初始容量10LinkedList双向链表头尾操作快节点内存开销大HashMap数组链表红黑树无序键值对put流程、扩容、线程不安全LinkedHashMapHashMap双向链表有序插入/访问LRU缓存实现TreeMap红黑树有序红黑树性质、日志级复杂度HashSetHashMap套壳无序不重复本质是HashMap的keyConcurrentHashMapCASsynchronized并发安全get无锁、size不精确Hashtable全表锁并发安全但性能差已淘汰记住一句话集合框架不靠背靠理解数据结构。你知道了数组、链表、哈希表、红黑树各自的特点就能自然地选出合适的集合也能自然地答出面试官的所有追问。下一篇我们讲并发编程——多线程到底是在解决什么问题线程池的参数怎么设volatile和synchronized到底有什么区别把这些讲透你就再也不用背了。