import java.util.ArrayList; import java.util.HashMap;

第一部分：ArrayList（动态数组）

1. 核心概念与内存机制

定义：ArrayList 是List接口的实现类，底层基于动态数组实现。与普通数组不同，它没有固定大小的限制，可以自动扩容。

核心特性：

• 随机访问极快：基于数组下标，获取和修改元素的时间复杂度为 $O(1)$。
• 插入/删除较慢：在中间位置插入或删除元素时，需要移动后续所有元素，时间复杂度为 $O(n)$。
• 泛型限制：只能存储引用数据类型，基本数据类型（如int）必须使用包装类（如Integer）。

2. 常用方法详解与代码示例

①add(E e)/add(int index, E element)

用法：将元素追加到列表末尾，或在指定位置插入元素。插入时，该位置及后续元素会向后移动一位。

ArrayList<String> list = new ArrayList<>(); list.add("Apple"); list.add("Banana"); list.add(1, "Cherry"); // 在索引1处插入，Banana后移 // 结果: [Apple, Cherry, Banana]

②get(int index)

用法：获取指定索引处的元素（索引从0开始）。

String fruit = list.get(1); // 获取索引1的元素 System.out.println(fruit); // Cherry

③set(int index, E element)

用法：替换指定索引处的元素，并返回被替换的旧元素。

String old = list.set(1, "Orange"); System.out.println(old); // Cherry System.out.println(list); // [Apple, Orange, Banana]

④remove(int index)/remove(Object o)

用法：按索引删除（返回被删元素）或按对象删除（返回布尔值）。

list.remove(0); // 删除索引0的元素（Apple） list.remove("Banana"); // 删除值为Banana的元素

⑤size()/isEmpty()/clear()

用法：获取元素个数、判断是否为空、清空所有元素。

System.out.println(list.size()); // 元素个数 System.out.println(list.isEmpty()); // 是否为空 list.clear(); // 清空列表

⑥contains(Object o)

用法：判断列表中是否包含指定元素，返回布尔值。

boolean has = list.contains("Apple"); // true

⑦indexOf(Object o)/lastIndexOf(Object o)

用法：返回元素第一次/最后一次出现的索引，未找到返回 -1。

int idx = list.indexOf("Cherry");

⑧subList(int fromIndex, int toIndex)

用法：截取部分元素（包头不包尾）。注意：返回的是原列表的视图，修改子列表会影响原列表。

List<String> sub = list.subList(1, 3);

3. ArrayList的遍历方式

ArrayList<String> fruits = new ArrayList<>(); fruits.add("Apple"); fruits.add("Banana"); fruits.add("Orange"); // 方式1：普通for循环（适合需要索引的场景） for (int i = 0; i < fruits.size(); i++) { System.out.println(fruits.get(i)); } // 方式2：增强for-each（推荐，简洁安全） for (String fruit : fruits) { System.out.println(fruit); }

4. 动态扩容机制

当添加元素导致size > 容量时，ArrayList 会自动扩容。新容量通常为原容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。如果预知数据量，可在构造时指定初始容量以避免频繁扩容。

第二部分：HashMap（哈希表）

1. 核心概念与内存机制

定义：HashMap 实现了Map接口，基于哈希表（数组 + 链表 + 红黑树）实现，用于存储键值对（Key-Value）。

核心特性：

• Key 唯一且无序：不允许重复键，不保证存储顺序。
• 允许 Null：允许一个 null 键和多个 null 值。
• 高效查找：增删改查的平均时间复杂度为 $O(1)$。
• 非线程安全：多线程环境下应使用ConcurrentHashMap。

2. 底层工作原理

1. 哈希计算：对 Key 调用hashCode()计算哈希值，确定在数组中的存储位置（桶）。
2. 冲突处理：若多个 Key 落入同一个桶，JDK 1.8 采用链表存储；当链表长度超过8且数组长度 ≥ 64 时，链表转为红黑树以提升查找效率。
3. 扩容机制：当元素数量超过容量 × 加载因子(默认0.75)时，触发扩容，新容量为原来的2倍，所有元素需重新计算位置。

3. 常用方法详解与代码示例

①put(K key, V value)

用法：添加或更新键值对。若 Key 已存在，覆盖旧值并返回旧值；不存在则返回 null。

HashMap<String, Integer> map = new HashMap<>(); map.put("Tom", 90); Integer old = map.put("Tom", 95); // 覆盖，old = 90

②get(Object key)/getOrDefault(K key, V defaultValue)

用法：根据 Key 获取 Value。若 Key 不存在，get返回 null，getOrDefault返回指定的默认值。

int score = map.getOrDefault("Jerry", 0); // Jerry不存在，返回0

③remove(Object key)

用法：删除指定 Key 的键值对，返回被删除的 Value。

map.remove("Tom");

④containsKey(Object key)/containsValue(Object value)

用法：判断是否包含指定的 Key 或 Value。

boolean hasKey = map.containsKey("Tom");

⑤size()/isEmpty()/clear()

用法：获取键值对数量、判空、清空。

int count = map.size();

⑥keySet()/values()/entrySet()

用法：获取所有 Key 的集合、所有 Value 的集合、所有键值对的集合。

Set<String> keys = map.keySet(); Collection<Integer> vals = map.values(); Set<Map.Entry<String, Integer>> entries = map.entrySet();

4. HashMap的遍历方式

HashMap<String, Integer> map = new HashMap<>(); map.put("Apple", 5); map.put("Banana", 3); // 推荐方式：遍历 entrySet（性能最优） for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + " = " + entry.getValue()); }

核心对比总结