- **正确答案**：Java 提供了丰富的数据结构，主要包括 List、Set、Map、Queue、Deque、Stack 等。这些数据结构都包含在 Java 的集合框架（Java Collections Framework）中，常见的实现类有 ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap、PriorityQueue、ArrayDeque 等。 - **解答思路**：首先要明确 Java 中的数据结构主要分为两大类：Collection 和 Map。 - Collection 接口的子接口包括 List（有序可重复）、Set（无序不可重复）、Queue（队列）等； - Map 接口用于存储键值对（Key-Value Pair），常见实现如 HashMap、TreeMap、LinkedHashMap。每种接口有不同的实现类，适用于不同的使用场景。例如： - ArrayList 基于数组实现，适合随机访问； - LinkedList 基于双向链表实现，适合频繁插入删除； - HashSet 使用哈希表实现，元素不重复； - TreeSet 使用红黑树实现，元素有序； - HashMap 使用哈希表+红黑树实现（JDK8以后），用于高效查找； - TreeMap 基于红黑树，键按顺序排列； - PriorityQueue 是一个最小堆（默认情况下），常用于优先级队列； - ArrayDeque 是双端队列，基于数组实现，性能优于 LinkedList 作为栈或队列使用时的表现。 - **深度知识讲解**： ### 1. 数据结构分类 Java 集合框架的顶层是 Iterable 接口，所有集合类都实现了该接口。核心接口如下： - **List**：有序、可重复、可通过索引访问。 - 实现类：ArrayList、LinkedList、Vector（线程安全） - **Set**：无序、不可重复。 - 实现类：HashSet（哈希表）、TreeSet（红黑树）、LinkedHashSet（哈希表+双向链表） - **Queue / Deque**：队列和双端队列，支持先进先出或后进先出。 - 实现类：PriorityQueue（最小堆）、ArrayDeque（双端队列）、LinkedList（也可作为队列） - **Map**：键值对集合，键唯一。 - 实现类：HashMap（哈希表+红黑树）、TreeMap（红黑树）、LinkedHashMap（哈希表+双向链表）、ConcurrentHashMap（线程安全） ### 2. 底层实现原理 #### ArrayList： - 基于动态数组实现； - 初始容量为10（JDK8开始为延迟初始化）； - 插入元素超过当前容量时扩容为原来的1.5倍； - 支持O(1)随机访问，尾部添加O(1)，中间插入O(n)； - 不是线程安全的。 #### LinkedList： - 基于双向链表实现； - 每个节点保存前驱和后继指针； - 插入删除O(1)（已知节点位置）； - 随机访问O(n)； - 可以作为 List、Deque 使用。 #### HashMap： - 哈希表 + 红黑树（当链表长度 >= 8 时转换为红黑树）； - 键不能重复，允许 null 键和 null 值； - put(k, v)：计算 key 的 hash 值，定位到桶的位置，冲突处理使用链表或红黑树； - get(k)：根据 hash 找到桶，再遍历链表或红黑树查找 key； - 默认加载因子为 0.75，初始容量为16； - 不是线程安全的。 #### HashSet： - 内部使用 HashMap 实现，value 存的是一个静态 Object 对象； - add(e)：调用 map.put(e, PRESENT)； - 元素唯一性由 equals() 和 hashCode() 保证。 #### TreeMap： - 基于红黑树实现； - 键必须实现 Comparable 接口或传入 Comparator； - 支持按键排序； - 查询、插入、删除的时间复杂度为 O(log n)。 #### PriorityQueue： - 最小堆实现，默认构造器构建最小堆； - 插入和删除都是 O(log n)； - 常用于任务调度、合并 K 个有序链表等问题； - 不支持线程安全。 ### 3. 应用场景总结 | 场景 | 推荐数据结构 | |------|---------------| | 需要频繁随机访问 | ArrayList | | 需要频繁插入/删除 | LinkedList | | 需要唯一元素 | HashSet | | 需要排序的集合 | TreeSet | | 需要键值对存储 | HashMap | | 需要按键排序的键值对 | TreeMap | | 需要优先级队列 | PriorityQueue | | 需要双端操作 | ArrayDeque | ### 4. 示例代码（伪代码风格） ```java // ArrayList 示例 List list = new ArrayList<>(); list.add(1); list.add(2); int value = list.get(0); // O(1) // LinkedList 示例 List linkedList = new LinkedList<>(); linkedList.add("A"); linkedList.addFirst("B"); // O(1) // HashSet 示例 Set set = new HashSet<>(); set.add(1.0); set.add(2.0); boolean contains = set.contains(1.0); // O(1) // HashMap 示例 Map map = new HashMap<>(); map.put("apple", 5); map.put("banana", 3); int count = map.get("apple"); // O(1) // PriorityQueue 示例 Queue pq = new PriorityQueue<>(); pq.offer(3); pq.offer(1); pq.offer(2); int min = pq.poll(); // 返回1 // TreeMap 示例 Map treeMap = new TreeMap<>(); treeMap.put("z", 10); treeMap.put("a", 5); for (String key : treeMap.keySet()) { System.out.println(key); // 输出 a z } ``` ### 5. 扩展知识点 - **线程安全的集合类**： - Vector、Hashtable（不推荐使用） - Collections.synchronizedList(new ArrayList<>()) - CopyOnWriteArrayList、ConcurrentHashMap（并发包中的高性能线程安全结构） - **函数式编程与集合结合**（Java 8+）： - Stream API 结合集合进行 filter、map、reduce 等操作； - 示例：`list.stream().filter(x -> x > 0).forEach(System.out::println);` - **迭代器失效问题**： - 在遍历集合过程中修改集合内容会导致 ConcurrentModificationException； - 解决方案：使用 Iterator.remove() 或者 CopyOnWriteArrayList。综上所述，Java 提供了非常丰富且灵活的数据结构体系，理解其底层实现有助于写出更高效的程序。在校园招聘面试中，这类问题通常考察候选人对 Java 基础的理解程度以及是否具备选择合适数据结构的能力。

爱奇艺二面

全站热榜

创作者周榜