引言
Java集合框架是Java语言中处理集合数据结构的标准库，它提供了丰富的接口和实现，使得数据操作更加高效和方便。本文将深入剖析Java集合框架的源码，并分享一些实战技巧，帮助读者更好地理解和运用Java集合。
Java集合框架概述
Java集合框架主要包括以下几类接口：
- Collection接口：它是集合框架的根接口，定义了集合的基本操作，如添加、删除、遍历等。
- List接口：继承自Collection接口，表示有序集合，元素可以重复。
- Set接口：继承自Collection接口，表示无序集合，元素不可重复。
- Queue接口：继承自Collection接口，表示先进先出（FIFO）的队列。
- Map接口：表示键值对映射，键和值都是对象。
Java集合框架还包括一些具体的实现类，如ArrayList、LinkedList、HashSet、HashMap等。
源码剖析
ArrayList
ArrayList是基于动态数组实现的，它提供了快速的随机访问能力。以下是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);
}
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);
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
public int size() {
return size;
}
// ... 其他方法 ...
}
LinkedList
LinkedList是基于双向链表实现的，它提供了高效的插入和删除操作。以下是LinkedList的简单源码：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8683452581122892189L;
private Node<E> first;
private Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(E element, Node<E> prev, Node<E> next) {
item = element;
this.prev = prev;
this.next = next;
}
}
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<>(e, l, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
}
public E get(int index) {
checkElementIndex(index);
return node(index).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 & ~-1; i > index; i--) {
x = x.prev;
}
return x;
}
}
// ... 其他方法 ...
}
HashSet
HashSet是基于哈希表实现的，它提供了高效的查找和删除操作。以下是HashSet的简单源码：
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 1331423618298944391L;
private transient HashMap<E, Object> map;
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
public int size() {
return map.size();
}
// ... 其他方法 ...
}
HashMap
HashMap是基于哈希表实现的，它提供了高效的查找和删除操作。以下是HashMap的简单源码：
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 362498820763181265L;
private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private static final Object EMPTY_TABLE = new Object();
private transient Entry<K, V>[] table;
private int size;
private int threshold;
private float loadFactor;
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 HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public V put(K key, V value) {
Entry<K, V> e = putVal(hash(key), key, value, false, true);
return e == null ? null : e.value;
}
private static int hash(Object key) {
int h = key == null ? 0 : (key.hashCode() ^ (key.hashCode() >>> 16));
return h ^ (h >>> 16);
}
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] = new Node<>(hash, key, value, null);
modCount++;
if (++size > threshold)
resize();
return null;
}
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 = e = new Node<>(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;
}
private void treeifyBin(Node<K, V>[] tab, int hash) {
final Node<K, V>[] ntab = (Node<K, V>[]) new Node<?, ?>[tab.length << 1];
int index = (hash & (tab.length - 1));
for (Node<K, V> e : tab) {
if (e != null) {
Node<K, V> p = e;
e = null;
do {
Node<K, V> next = p.next;
int k = p.hash;
int h = k ^ (k >>> 16);
index = h & (ntab.length - 1);
p.next = ntab[index];
ntab[index] = p;
p = next;
} while (p != null);
}
}
tab = ntab;
}
private void resize() {
int oldCapacity = table.length;
int newCapacity = oldCapacity << 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(oldCapacity);
}
Node<K, V>[] newTable = (Node<K, V>[]) new Node<?, ?>[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (loadFactor * newCapacity);
}
private void transfer(Node<K, V>[] newTable) {
for (Node<K, V> e : table) {
while (e != null) {
Node<K, V> next = e.next;
int hash = e.hash;
int i = indexFor(hash, newTable.length);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
private static int indexFor(int h, int length) {
return h & (length - 1);
}
private static int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
if (n < 0) {
n = 1;
}
if (n > MAX_ARRAY_SIZE) {
n = MAX_ARRAY_SIZE;
}
return n;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// ... 其他方法 ...
}
实战技巧
选择合适的集合类型：根据实际需求选择合适的集合类型，例如，如果需要快速随机访问，则选择ArrayList；如果需要高效插入和删除操作，则选择LinkedList。
避免使用原始类型：Java集合框架中的集合类型都是泛型，建议使用泛型类型而不是原始类型，以避免类型转换和装箱拆箱操作。
使用迭代器进行遍历：使用迭代器进行遍历可以避免在遍历过程中修改集合，从而避免出现并发修改异常。
使用泛型方法：Java集合框架提供了许多泛型方法，如
addAll()、removeAll()等，这些方法可以简化代码并提高安全性。自定义集合实现：如果标准集合框架无法满足需求，可以自定义集合实现，例如，实现自己的List、Set或Map。
总结
Java集合框架是Java语言中处理集合数据结构的标准库，它提供了丰富的接口和实现，使得数据操作更加高效和方便。通过源码剖析和实战技巧的学习，读者可以更好地理解和运用Java集合，提高编程效率。