面试基础--Java 集合框架详解

Java 集合框架详解：从 ArrayList 到 HashMap 的底层原理

引言

在 Java 开发中，集合框架（Collection Framework）是处理数据存储和操作的核心工具。无论是日常开发还是大厂面试，对集合框架的理解都是考察的重点之一。本文将详细讲解 ArrayList、LinkedList 以及 HashMap 的底层实现原理，并通过对比分析它们的优缺点和适用场景。

---

一、List 接口的实现：ArrayList 和 LinkedList

1. ArrayList 的底层实现

ArrayList 是基于 动态数组 实现的，其内部使用一个 对象数组（Object[]） 来存储数据。当数组空间不足时，ArrayList 会自动扩容。

核心特性

• 查询效率高：由于数组是连续内存空间，可以通过索引直接访问元素，时间复杂度为 O(1)。
• 增删效率低：在中间位置插入或删除元素时，需要移动大量数据，时间复杂度为 O(n)。
• 动态扩容机制：默认情况下，ArrayList 的容量每次增加 50%（即 newCapacity = oldCapacity + (oldCapacity >> 1)）。

源码分析

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final int DEFAULT_CAPACITY = 10;transient Object[] elementData; // 存储元素的数组private int size; // 当前列表大小public E get(int index) {rangeCheck(index);return (E) elementData[index];}public void add(E e) {if (size == elementData.length)expandCapacity();elementData[size++] = e;}private void expandCapacity() {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);elementData = Arrays.copyOf(elementData, newCapacity);}
}

---

2. LinkedList 的底层实现

LinkedList 是基于 双向链表 实现的。每个节点（Node）包含一个指向前后节点的指针以及存储的数据。

核心特性

• 查询效率低：由于链表是非连续内存空间，需要从头或尾遍历到目标节点，时间复杂度为 O(n)。
• 增删效率高：在链表中间插入或删除元素时，只需要修改前后节点的指针，时间复杂度为 O(1)。

源码分析

public class LinkedList<E> extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {private static class Node<E> {E item; // 存储的元素Node<E> next; // 后继节点指针Node<E> prev; // 前驱节点指针Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}private transient Node<E> first; // 首节点private transient Node<E> last; // 末尾节点public void addFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;}public E get(int index) {checkElementIndex(index);Node<E> node = node(index);return node.item;}private Node<E> node(int index) {if (index < (size >> 1)) { // 从前向后查找Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else { // 从后向前查找Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}
}

---

3. ArrayList 和 LinkedList 的对比

特性	ArrayList	LinkedList
存储结构	动态数组	双向链表
查询效率	高（O(1)）	低（O(n)）
增删效率	低（O(n)）	高（O(1)）
内存占用	较高（额外存储空间用于扩容）	较低（仅存储节点和指针）
适用场景	需要频繁查询的场景	需要频繁增删的场景

---

二、Map 接口的实现：HashMap 的底层原理

1. HashMap 的基本结构

HashMap 是基于 哈希表（Hash Table） 实现的，其底层是一个 数组+链表+红黑树 的组合结构。

核心特性

• 存储结构：数组中的每个元素称为一个“桶”（Bucket），每个桶包含一组键值对。
• 哈希函数：通过 hashCode() 方法计算键的哈希值，并将其映射到数组索引位置。
• 解决哈希冲突：当多个键映射到同一个索引时，使用链表或红黑树存储这些键值对。

---

2. 哈希冲突的处理

（1）拉链法（Chaining）

当发生哈希冲突时，HashMap 使用 拉链法 将多个键值对存储在同一个桶中。具体实现方式如下：

• 如果一个桶中只有一个节点，则使用单链表结构。
• 当链表长度超过 8 时，链表会被转换为红黑树（JDK 1.8 及以上版本）。

（2）开放地址法（Open Addressing）

HashMap 不采用开放地址法，而是通过拉链法解决哈希冲突。

---

3. HashMap 的源码分析

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始容量 16private static final float LOAD_FACTOR = 0.75f; // 负载因子transient Node<K,V>[] table; // 存储节点的数组private int size; // 当前键值对数量int threshold; // 扩容阈值（容量 × 负载因子）public V get(Object key) {Node<K,V> node = getNode(hash(key), key);return (node == null) ? null : node.value;}private Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab = table;int index = (tab.length - 1) & hash; // 计算索引for (Node<K,V> e = tab[index]; e != null; e = e.next) {if (e.hash == hash && (key == e.key || key.equals(e.key))) {return e;}}return null;}public boolean put(K key, V value) {return putVal(hash(key), key, value, false, true);}private int hash(int originalHash) {// 高位参与运算，减少碰撞概率int h = originalHash ^ (originalHash >>> 16);return h;}
}

---

4. HashMap 的扩容机制

当键值对的数量超过 扩容阈值（threshold） 时，HashMap 会执行扩容操作：

• 新容量为当前容量的 2 倍。
• 所有键值对会被重新散列到新的数组中。

---

5. HashMap 的性能分析

特性	描述
时间复杂度	平均情况下，查询、插入和删除的时间复杂度为 O(1)
空间复杂度	O(n)，其中 n 是键值对的数量
适用场景	需要高效查询的场景

---

总结

• ArrayList 和 LinkedList 的选择取决于具体的增删查改需求。
• HashMap 在现代 Java 中提供了高效的键值存储能力，但需要注意哈希冲突和扩容机制。