Java集合框架是Java语言中处理集合数据结构的标准库,它提供了丰富的接口和类,用于存储、检索、更新和删除集合中的元素。深入理解Java集合框架不仅有助于提高代码的效率,还能帮助我们更好地利用Java语言进行编程。本文将详细解析Java集合框架的源码,并分享一些实战技巧。
1. Java集合框架概述
Java集合框架主要包括以下几部分:
- 集合接口:如Collection和Map接口,定义了集合的基本操作。
- 抽象类:如AbstractCollection和AbstractMap,提供了部分实现,方便子类继承。
- 实现类:如ArrayList、LinkedList、HashMap、TreeMap等,实现了具体的集合操作。
- 迭代器:如Iterator和ListIterator,用于遍历集合中的元素。
- 比较器:如Comparator,用于对集合中的元素进行排序。
2. 集合接口与实现类
2.1 Collection接口
Collection接口是所有集合类的父接口,它定义了集合的基本操作,如添加、删除、查找等。以下是一些常用的实现类:
- ArrayList:基于动态数组实现的集合,提供了快速的随机访问,但插入和删除操作较慢。
- LinkedList:基于双向链表实现的集合,插入和删除操作较快,但随机访问较慢。
- HashSet:基于哈希表实现的集合,元素唯一,无顺序。
- LinkedHashSet:基于链表和哈希表实现的集合,元素唯一,保持插入顺序。
2.2 Map接口
Map接口表示键值对映射,键和值可以是任意类型的对象。以下是一些常用的实现类:
- HashMap:基于哈希表实现的集合,提供了快速的键值对查找,但元素无顺序。
- TreeMap:基于红黑树实现的集合,键值对按照自然顺序或自定义顺序排列。
- LinkedHashMap:基于链表和哈希表实现的集合,键值对按照插入顺序排列。
3. 源码解读
3.1 ArrayList源码解析
ArrayList是基于动态数组实现的集合,以下是其部分源码:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private transient Object[] elementData;
private int size;
public ArrayList() {
this.elementData = DEFAULT_CAPACITY;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1) + 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) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
return (E) elementData[index];
}
public E set(int index, E element) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
public E remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
}
3.2 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;
static class Node<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Node<K, V> next;
int hash;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
if (key == null) {
if (e.getKey() != null) {
return false;
}
} else if (!key.equals(e.getKey())) {
return false;
}
if (value == null) {
if (e.getValue() != null) {
return false;
}
} else if (!value.equals(e.getValue())) {
return false;
}
return true;
}
public final int hashCode() {
int h = hash;
if (h == 0) {
if (key instanceof String) {
return key.hashCode();
}
h = key.hashCode() ^ (key instanceof Comparable ? ((Comparable) key).compareTo(key) : 0);
}
return h;
}
}
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int HASH_TABLE_SIZE = 1 << 4;
transient Node<K, V>[] table;
transient int size;
transient int modCount;
int threshold;
float loadFactor;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
this.threshold = (int) (DEFAULT_INITIAL_CAPACITY * loadFactor);
table = new Node[DEFAULT_INITIAL_CAPACITY];
}
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null) {
return putForNullKey(value);
}
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Node<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key instanceof Comparable && key.compareTo(k) == 0))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, i);
return null;
}
private void addEntry(int hash, K key, V value, int bucketIndex) {
Node<K, V> e = table[bucketIndex];
table[bucketIndex] = new Node<>(hash, key, value, e);
if (++modCount > threshold) {
resize();
}
}
private void resize() {
int oldCapacity = table.length;
int newCapacity = oldCapacity << 1;
Node<K, V>[] newTable = new Node[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
private void transfer(Node<K, V>[] newTable) {
for (Node<K, V> e : table) {
while (e != null) {
Node<K, V> next = e.next;
int i = indexFor(e.hash, newTable.length);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
private static int hash(Object x) {
int h = 0;
if (x != null) {
h = x.hashCode();
}
return h ^ (h >>> 16);
}
private static int indexFor(int h, int length) {
return h & (length - 1);
}
public V get(Object key) {
Node<K, V> e = getNode(hash(key), key);
if (e == null) {
return null;
}
return e.value;
}
private Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab; Node<K, V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[indexFor(hash, n)]) != null) {
if (first.hash == hash &&
((k = first.key) == key || (key instanceof Comparable && key.compareTo(k) == 0))) {
return first;
}
for (e = first.next; e != null; e = e.next) {
if (e.hash == hash &&
((k = e.key) == key || (key instanceof Comparable && key.compareTo(k) == 0))) {
return e;
}
}
}
return null;
}
}
4. 实战技巧
4.1 选择合适的集合类型
根据实际需求选择合适的集合类型,例如:
- 顺序性:如果需要保持元素的插入顺序,可以使用LinkedList或LinkedHashSet。
- 唯一性:如果需要保证元素的唯一性,可以使用HashSet或LinkedHashSet。
- 有序性:如果需要按照自然顺序或自定义顺序排列元素,可以使用TreeMap或TreeSet。
4.2 使用泛型提高代码安全性
在Java集合框架中,泛型可以避免类型转换异常,提高代码安全性。例如:
List<String> list = new ArrayList<>();
list.add("Hello");
list.add("World");
String first = list.get(0); // 直接使用String类型,无需进行类型转换
4.3 注意内存泄漏
在使用集合时,要注意避免内存泄漏。例如,在遍历集合时,要确保在迭代器外部关闭资源,避免出现内存泄漏。
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
// 处理元素
}
// 关闭迭代器
iterator = null;
5. 总结
Java集合框架是Java语言中处理集合数据结构的标准库,它提供了丰富的接口和类,方便我们进行编程。通过深入解析Java集合框架的源码,我们可以更好地理解其原理和实现方式,从而在实际开发中更加灵活地使用它。本文介绍了Java集合框架的概述、接口与实现类、源码解析以及实战技巧,希望对您有所帮助。
