🎯 Java容器全面详解

🔍 容器框架概览

Java容器主要分为两大体系：Collection 和 Map，它们都是Java集合框架的基础。

集合框架三大核心接口

• List：有序可重复集合
• Set：无序不可重复集合
• Map：键值对映射

体系结构图

Collection接口
    ├── List接口 (有序、可重复)
    │    ├── ArrayList
    │    ├── LinkedList  
    │    └── Vector
    │
    ├── Set接口 (无序、不可重复)
    │    ├── HashSet
    │    ├── LinkedHashSet
    │    └── TreeSet
    │
    └── Queue接口 (队列)
         ├── PriorityQueue
         └── LinkedList

Map接口
    ├── HashMap
    ├── LinkedHashMap
    ├── TreeMap
    └── Hashtable

⚙️ 核心容器详解

1. List体系

ArrayList

底层原理：基于动态Object数组实现。当数组容量不足时，会自动进行扩容操作。

// 默认初始容量为10
// 扩容机制：newCapacity = oldCapacity + (oldCapacity >> 1)
// 即每次扩容为原来的1.5倍

操作复杂度：

• 查询（get/set）：O(1) - 通过索引直接访问
• 插入/删除（add/remove）：
  • 末尾操作：O(1)（不考虑扩容）
  • 指定位置：O(n) - 需要移动元素
• 包含（contains）：O(n) - 需要遍历数组

核心API：

// 构造方法
ArrayList<Integer> list = new ArrayList<>(); // 初始容量10
ArrayList<Integer> list2 = new ArrayList<>(100); // 指定初始容量

// 常用方法
list.add(1); // 添加元素
list.add(0, 10); // 在指定位置插入
list.get(0); // 获取指定位置元素
list.set(0, 20); // 设置指定位置元素
list.remove(0); // 删除指定位置元素
list.remove(Integer.valueOf(20)); // 删除指定元素
list.size(); // 元素个数
list.isEmpty(); // 判断是否为空
list.contains(10); // 是否包含指定元素
list.indexOf(10); // 查找元素索引

LinkedList

底层原理：基于双向链表数据结构实现。每个节点包含前驱、后继指针和存储的数据。

操作复杂度：

• 查询（get/set）：O(n) - 需要遍历链表
• 插入/删除：
  • 头尾操作：O(1)
  • 指定位置：O(n) - 需要先找到位置
• 包含（contains）：O(n) - 需要遍历链表

核心API：

LinkedList<Integer> list = new LinkedList<>();

// LinkedList特有方法
list.addFirst(1); // 头部添加
list.addLast(2); // 尾部添加
list.getFirst(); // 获取头部元素
list.getLast(); // 获取尾部元素
list.removeFirst(); // 移除头部元素
list.removeLast(); // 移除尾部元素

// 也支持List接口的所有方法
list.add(1); 
list.get(0);
list.remove(0);

Vector

底层原理：与ArrayList类似，基于Object数组实现，但是线程安全（方法使用synchronized修饰），效率较低。

2. Set体系

HashSet

底层原理：基于HashMap实现，使用哈希表支持，元素存储在HashMap的key中。

操作复杂度：

• 添加、删除、包含：平均O(1)，最坏O(n)（哈希冲突严重时）

核心API：

HashSet<String> set = new HashSet<>();

set.add("apple");
set.add("banana");
set.remove("apple");
set.contains("banana");
set.size();
set.isEmpty();

LinkedHashSet

底层原理：继承HashSet，底层使用链表和哈希表，链表保证元素插入顺序，哈希表保证元素唯一性。

TreeSet

底层原理：基于红黑树（自平衡二叉查找树）实现，元素会按照自然顺序或比较器进行排序存储。

操作复杂度：

• 添加、删除、包含：O(log n)

3. Map体系

HashMap

底层原理：基于数组+链表+红黑树的哈希表实现。

• JDK1.7：数组+链表
• JDK1.8+：数组+链表+红黑树（链表长度>8时转换为红黑树）

操作复杂度：

• 插入、删除、查询：平均O(1)，最坏O(log n)（转为红黑树时）

核心API：

HashMap<String, Integer> map = new HashMap<>();

map.put("apple", 1); // 添加键值对
map.get("apple"); // 获取值
map.remove("apple"); // 删除键值对
map.containsKey("apple"); // 是否包含键
map.containsValue(1); // 是否包含值
map.keySet(); // 获取所有键的Set
map.values(); // 获取所有值的Collection
map.entrySet(); // 获取所有键值对的Set
map.size();
map.isEmpty();

LinkedHashMap

底层原理：继承HashMap，使用链表维护元素的插入顺序或访问顺序。

TreeMap

底层原理：基于红黑树实现，键会按照自然顺序或比较器进行排序存储。

操作复杂度：各项操作均为O(log n)

Hashtable

底层原理：早期的哈希表实现，线程安全但效率低，不允许null键和null值。

📊 复杂度对比总结

下表总结了各容器主要操作的时间复杂度：

容器	查询	插入/删除(头尾)	插入/删除(指定位置)	包含
ArrayList	O(1)	O(1)	O(n)	O(n)
LinkedList	O(n)	O(1)	O(n)	O(n)
HashSet	-	-	-	O(1)
TreeSet	-	-	-	O(log n)
HashMap	O(1)	-	-	O(1)
TreeMap	O(log n)	-	-	O(log n)

🔄 容器遍历方式

1. 传统for循环（只适用于List）

List<String> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    String item = list.get(i);
}

2. foreach循环

for (String item : list) {
    System.out.println(item);
}

3. 迭代器（Iterator）

// Collection遍历
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    iterator.remove(); // 安全删除
}

// Map遍历
Map<String, Integer> map = new HashMap<>();
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

4. Lambda表达式（Java 8+）

list.forEach(item -> System.out.println(item));
map.forEach((key, value) -> System.out.println(key + ": " + value));

⚠️ 面试常见问题解析

1. 线程安全性问题

• 非线程安全：ArrayList、HashMap、HashSet等
• 线程安全：Vector、Hashtable
• 推荐方案：使用Collections.synchronizedXXX()包装器或ConcurrentHashMap等并发容器

2. HashMap工作原理

1. put过程：计算key的hashcode→确定桶位置→遍历链表/红黑树插入
2. 扩容机制：默认负载因子0.75，当size > capacity * 0.75时扩容为2倍
3. 链表转红黑树：链表长度>8且数组长度≥64时转换
4. 哈希冲突解决：链表法（JDK1.7），链表+红黑树（JDK1.8+）

3. ConcurrentHashMap vs Hashtable

• Hashtable：全表锁，性能差
• ConcurrentHashMap：分段锁（JDK1.7），CAS+synchronized（JDK1.8+），高并发性能好

4. fail-fast机制

使用modCount记录结构修改次数，在迭代时检测到意外修改会抛出ConcurrentModificationException。

💡 笔试算法技巧

1. 容器选择策略

• 快速随机访问：ArrayList
• 频繁插入删除：LinkedList
• 去重操作：HashSet
• 键值映射：HashMap
• 排序需求：TreeSet/TreeMap

2. 常用算法模式

// 双指针+List
List<Integer> list = new ArrayList<>();
int left = 0, right = list.size() - 1;

// 滑动窗口+Map记录
Map<Character, Integer> window = new HashMap<>();

// 优先级队列（堆）
PriorityQueue<Integer> heap = new PriorityQueue<>();

// 并查集+Map实现
Map<Integer, Integer> parent = new HashMap<>();

3. 复杂度优化示例

// 两数之和：使用HashMap将O(n²)优化为O(n)
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}