1. Java集合框架概述Java集合框架是Java语言中最重要的基础库之一它提供了一套完善的接口和类来存储和操作数据集合。在面试中集合框架相关的问题几乎必问因为它不仅考察基础知识的掌握程度还能反映开发者对数据结构和算法的理解深度。集合框架主要分为三大类List有序集合允许重复元素Set无序集合不允许重复元素Map键值对映射集合2. 常见集合类解析2.1 List接口实现类ArrayListArrayList是基于动态数组实现的List它有以下特点随机访问速度快O(1)时间复杂度插入和删除元素效率较低需要移动元素默认初始容量为10扩容时增加50%// ArrayList初始化示例 ListString arrayList new ArrayList(); arrayList.add(Java); arrayList.add(Python);LinkedListLinkedList是基于双向链表实现的List特点包括插入和删除元素效率高O(1)时间复杂度随机访问效率低需要遍历链表实现了Deque接口可以作为队列使用// LinkedList作为队列使用示例 QueueString queue new LinkedList(); queue.offer(First); queue.offer(Second);2.2 Set接口实现类HashSetHashSet是基于HashMap实现的Set特点包括元素无序不允许重复元素添加、删除、查找操作的时间复杂度都是O(1)// HashSet使用示例 SetInteger set new HashSet(); set.add(1); set.add(2);TreeSetTreeSet是基于红黑树实现的Set特点包括元素按自然顺序或Comparator排序添加、删除、查找操作的时间复杂度都是O(log n)// TreeSet使用示例 SetString treeSet new TreeSet(); treeSet.add(Banana); treeSet.add(Apple);2.3 Map接口实现类HashMapHashMap是基于哈希表实现的Map特点包括键值对存储允许null键和null值非线程安全JDK8后当链表长度超过8时会转为红黑树// HashMap使用示例 MapString, Integer map new HashMap(); map.put(Java, 1); map.put(Python, 2);ConcurrentHashMapConcurrentHashMap是线程安全的HashMap实现特点包括采用分段锁技术提高并发性能不允许null键和null值在JDK8中改为使用CASsynchronized实现3. 数据结构基础3.1 二叉树基本概念二叉树是每个节点最多有两个子节点的树结构具有以下特性第i层最多有2^(i-1)个节点深度为k的二叉树最多有2^k-1个节点对于任何非空二叉树n0 n2 1n0是叶子节点数n2是度为2的节点数3.2 二叉树遍历方式前序遍历根节点 - 左子树 - 右子树void preOrder(TreeNode root) { if (root ! null) { System.out.print(root.val ); preOrder(root.left); preOrder(root.right); } }中序遍历左子树 - 根节点 - 右子树void inOrder(TreeNode root) { if (root ! null) { inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } }后序遍历左子树 - 右子树 - 根节点void postOrder(TreeNode root) { if (root ! null) { postOrder(root.left); postOrder(root.right); System.out.print(root.val ); } }层序遍历按层次从上到下每层从左到右void levelOrder(TreeNode root) { if (root null) return; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); System.out.print(node.val ); if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } }3.3 特殊二叉树类型满二叉树所有非叶子节点都有两个子节点且所有叶子节点都在同一层。完全二叉树除最后一层外其他层节点数都达到最大值最后一层节点都集中在左侧。二叉搜索树(BST)对于任意节点左子树所有节点值小于该节点值右子树所有节点值大于该节点值平衡二叉树(AVL)任何节点的左右子树高度差不超过1。红黑树一种自平衡二叉搜索树具有以下特性节点是红色或黑色根节点是黑色每个叶子节点(NIL)是黑色红色节点的子节点必须是黑色从任一节点到其每个叶子的路径包含相同数目的黑色节点4. 常见面试题解析4.1 HashMap相关HashMap的工作原理HashMap基于哈希表实现通过hashCode()方法计算键的哈希值然后通过哈希算法确定存储位置。当发生哈希冲突时JDK8之前使用链表解决JDK8之后当链表长度超过阈值(8)时会转为红黑树。HashMap的扩容机制HashMap默认负载因子为0.75当元素数量超过容量*负载因子时会进行扩容扩容后容量变为原来的2倍。扩容时需要重新计算所有元素的位置这是一个耗时的操作。4.2 ConcurrentHashMap相关ConcurrentHashMap如何保证线程安全在JDK7中ConcurrentHashMap使用分段锁技术将数据分成多个Segment每个Segment独立加锁。在JDK8中改为使用CASsynchronized实现锁的粒度更小并发性能更好。4.3 二叉树相关判断二叉树是否对称public boolean isSymmetric(TreeNode root) { return root null || isMirror(root.left, root.right); } private boolean isMirror(TreeNode left, TreeNode right) { if (left null right null) return true; if (left null || right null) return false; return left.val right.val isMirror(left.left, right.right) isMirror(left.right, right.left); }二叉树的最大深度public int maxDepth(TreeNode root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }5. 性能比较与选择建议5.1 List实现类比较特性ArrayListLinkedList随机访问O(1)O(n)头部插入O(n)O(1)尾部插入O(1)O(1)内存占用较小较大选择建议需要频繁随机访问ArrayList需要频繁在头部插入删除LinkedList不确定时优先选择ArrayList5.2 Set实现类比较特性HashSetTreeSet排序无序有序时间复杂度O(1)O(log n)允许null是否(如果使用自然排序)选择建议需要快速查找且不关心顺序HashSet需要有序集合TreeSet5.3 Map实现类比较特性HashMapTreeMapConcurrentHashMap排序无序有序无序线程安全否否是允许null是否否选择建议单线程环境HashMap需要有序映射TreeMap多线程环境ConcurrentHashMap6. 实际应用场景6.1 使用HashMap统计词频public MapString, Integer wordCount(String text) { MapString, Integer map new HashMap(); String[] words text.split(\\s); for (String word : words) { map.put(word, map.getOrDefault(word, 0) 1); } return map; }6.2 使用TreeSet实现排行榜class Player implements ComparablePlayer { String name; int score; // 按分数从高到低排序 public int compareTo(Player other) { return other.score - this.score; } } public class Leaderboard { private TreeSetPlayer players new TreeSet(); public void addPlayer(Player player) { players.add(player); } public ListPlayer getTop10() { return players.stream().limit(10).collect(Collectors.toList()); } }6.3 使用优先队列解决Top K问题public ListInteger topKFrequent(int[] nums, int k) { MapInteger, Integer frequencyMap new HashMap(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) 1); } PriorityQueueMap.EntryInteger, Integer pq new PriorityQueue((a, b) - a.getValue() - b.getValue()); for (Map.EntryInteger, Integer entry : frequencyMap.entrySet()) { pq.offer(entry); if (pq.size() k) { pq.poll(); } } ListInteger result new ArrayList(); while (!pq.isEmpty()) { result.add(pq.poll().getKey()); } return result; }7. 常见问题与解决方案7.1 HashMap线程不安全问题问题描述在多线程环境下使用HashMap可能导致死循环或数据丢失。解决方案使用Collections.synchronizedMap包装HashMap使用ConcurrentHashMap推荐// 解决方案1 MapString, String syncMap Collections.synchronizedMap(new HashMap()); // 解决方案2 MapString, String concurrentMap new ConcurrentHashMap();7.2 ArrayList并发修改异常问题描述在使用迭代器遍历ArrayList时修改集合会抛出ConcurrentModificationException。解决方案使用迭代器的remove方法使用CopyOnWriteArrayList适合读多写少场景在遍历前创建副本ListString list new ArrayList(); // 错误方式 for (String item : list) { if (condition) { list.remove(item); // 抛出异常 } } // 正确方式1 IteratorString it list.iterator(); while (it.hasNext()) { String item it.next(); if (condition) { it.remove(); // 安全删除 } } // 正确方式2 ListString copy new ArrayList(list); for (String item : copy) { if (condition) { list.remove(item); } }7.3 对象作为HashMap键的注意事项问题描述自定义对象作为HashMap键时如果重写了equals方法但没重写hashCode方法可能导致无法正确获取值。解决方案同时重写equals和hashCode方法确保equals和hashCode使用相同的字段保证对象的不可变性class Person { private String name; private int age; // 构造函数、getter/setter省略 Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Person person (Person) o; return age person.age Objects.equals(name, person.name); } Override public int hashCode() { return Objects.hash(name, age); } }8. 性能优化建议8.1 初始化集合时指定容量对于已知大小的集合初始化时指定容量可以避免不必要的扩容操作。// 优化前 ListString list new ArrayList(); // 默认容量10 MapString, Integer map new HashMap(); // 默认容量16 // 优化后 ListString list new ArrayList(100); // 初始容量100 MapString, Integer map new HashMap(128); // 初始容量1288.2 使用entrySet遍历Map遍历Map时使用entrySet比先获取keySet再获取value更高效。MapString, Integer map new HashMap(); // 低效方式 for (String key : map.keySet()) { Integer value map.get(key); // 处理key和value } // 高效方式 for (Map.EntryString, Integer entry : map.entrySet()) { String key entry.getKey(); Integer value entry.getValue(); // 处理key和value }8.3 考虑使用原始类型集合对于基本数据类型使用原始类型集合如Eclipse Collections、FastUtil可以避免装箱/拆箱开销。// 使用FastUtil的IntArrayList IntList list new IntArrayList(); list.add(1); list.add(2); int first list.getInt(0); // 不需要拆箱9. Java 8对集合的增强9.1 Stream APIStream API提供了更强大的集合操作方式ListString names Arrays.asList(Alice, Bob, Charlie); // 过滤和转换 ListString result names.stream() .filter(name - name.length() 3) .map(String::toUpperCase) .collect(Collectors.toList()); // 分组 MapInteger, ListString groupByLength names.stream() .collect(Collectors.groupingBy(String::length)); // 统计 IntSummaryStatistics stats names.stream() .mapToInt(String::length) .summaryStatistics();9.2 forEach方法集合新增了forEach方法简化遍历ListString list Arrays.asList(a, b, c); // 传统方式 for (String s : list) { System.out.println(s); } // Java 8方式 list.forEach(System.out::println);9.3 compute方法Map新增了compute系列方法简化操作MapString, Integer map new HashMap(); map.put(apple, 1); // 如果存在则更新 map.computeIfPresent(apple, (k, v) - v 1); // 如果不存在则添加 map.computeIfAbsent(banana, k - 0);10. 面试准备建议10.1 重点掌握内容HashMap工作原理、哈希冲突解决、扩容机制ConcurrentHashMap线程安全实现原理JDK7和JDK8的区别ArrayList vs LinkedList底层实现、适用场景TreeMap/TreeSet红黑树原理、时间复杂度Fail-Fast机制快速失败原理及应对方法10.2 常见问题示例HashMap和HashTable的区别ConcurrentHashMap是如何实现线程安全的ArrayList的扩容机制是怎样的如何实现一个LRU缓存红黑树有哪些特性为什么要用红黑树而不用AVL树10.3 算法题准备实现一个双向链表实现一个简单的HashMap二叉树的各种遍历递归和非递归判断二叉树是否为平衡二叉树两个栈实现队列11. 总结与个人建议在实际开发中选择正确的集合类可以显著提高程序性能。根据我的经验以下几点特别值得注意预估集合大小对于已知大小的集合初始化时指定容量可以避免多次扩容带来的性能损耗。我曾经优化过一个性能问题仅仅通过为ArrayList指定初始容量就将性能提升了30%。注意集合的线程安全性在多线程环境下一定要使用线程安全的集合类或进行适当的同步。我曾经遇到过因为使用非线程安全集合导致的难以复现的bug花费了大量时间排查。合理使用Java 8新特性Stream API可以让代码更简洁但要注意它不总是性能最优的选择特别是在处理小数据集时。理解底层实现只有深入理解集合类的底层实现原理才能在面试和实际开发中做出最佳选择。建议阅读JDK源码特别是HashMap和ArrayList的实现。关注内存使用对于大型集合不同的实现内存开销可能差异很大。在内存敏感的场景下可以考虑使用原始类型集合或更紧凑的数据结构。