Java集合框架是Java语言中处理集合对象的标准库，它提供了丰富的数据结构，如List、Set、Map等，以及操作这些数据结构的算法。本文将深入解析Java集合框架的核心源码，全面总结实用技巧与原理。
1. Java集合框架概述
Java集合框架主要包括以下几个接口：
- Collection接口：是所有集合的根接口，定义了集合的基本操作，如添加、删除、遍历等。
- List接口：继承自Collection接口，表示有序的集合，允许重复元素。
- Set接口：继承自Collection接口，表示无序的集合，不允许重复元素。
- Map接口：表示键值对映射，键是唯一的，值可以重复。
Java集合框架还提供了多种具体的实现类，如ArrayList、LinkedList、HashSet、HashMap等。
2. ArrayList源码解析
ArrayList是List接口的一个实现类，底层使用数组来存储元素。以下是ArrayList的核心方法：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8683452581122892189L;
private transient Object[] elementData; // 存储元素的数组
private int size; // 集合大小
public ArrayList(int initialCapacity) {
if (initialCapacity >= 0) {
this.elementData = new Object[initialCapacity];
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
public ArrayList() {
this(10); // 默认容量为10
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保数组容量足够
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (minCapacity - elementData.length > 0) {
grow(minCapacity); // 扩容
}
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
2.1 扩容机制
当ArrayList的元素个数超过数组容量时，会进行扩容操作。扩容机制如下：
- 如果当前数组容量小于最小容量（默认为10），则直接扩容为最小容量。
- 否则，扩容为原来的1.5倍。
- 如果扩容后的容量小于最小容量，则扩容为最小容量。
- 如果扩容后的容量大于最大数组容量（Integer.MAX_VALUE - 8），则扩容为最大数组容量。
2.2 查找元素
查找元素时，ArrayList会遍历数组，时间复杂度为O(n)。
3. LinkedList源码解析
LinkedList是List接口的一个实现类，底层使用双向链表来存储元素。以下是LinkedList的核心方法：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8683452581122892189L;
transient int size; // 集合大小
transient Node<E> first; // 链表头节点
transient Node<E> last; // 链表尾节点
public LinkedList() {
}
public boolean add(E e) {
linkLast(e); // 添加元素到链表尾部
return true;
}
private void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
}
3.1 查找元素
查找元素时，LinkedList会从头节点开始遍历链表，时间复杂度为O(n)。
4. HashSet源码解析
HashSet是Set接口的一个实现类，底层使用哈希表来存储元素。以下是HashSet的核心方法：
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 1332129227875231411L;
transient int size; // 集合大小
transient HashMap<E, Object> map; // 内部使用HashMap存储元素
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
}
4.1 查找元素
查找元素时，HashSet会使用元素的hashCode()值来定位到哈希表中的位置，时间复杂度为O(1)。
5. HashMap源码解析
HashMap是Map接口的一个实现类，底层使用哈希表来存储键值对。以下是HashMap的核心方法：
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 362498820763181265L;
transient int size; // 集合大小
transient Node<K, V>[] table; // 存储键值对的数组
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量为16
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子为0.75
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
}
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal Load factor: " + loadFactor);
}
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
private V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab; Node<K, V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else {
Node<K, V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
} else if (p instanceof TreeNode) {
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
} else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
if (e != null) { // existing mapping found
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
}
5.1 查找元素
查找元素时，HashMap会使用键的hashCode()值来定位到哈希表中的位置，时间复杂度为O(1)。
6. 总结
本文深入解析了Java集合框架的核心源码，包括ArrayList、LinkedList、HashSet和HashMap等常用实现类。通过分析这些实现类的源码，我们可以更好地理解Java集合框架的原理和实用技巧，从而在编程实践中更加得心应手。