深入理解JDK源码：HashMap、ArrayList等核心集合类的设计哲学
大家好，今天我们来深入探讨JDK源码中一些核心集合类的设计哲学，重点会放在HashMap和ArrayList这两个类上。通过剖析它们的实现细节，我们可以更好地理解Java集合框架的设计思想，提升代码质量和性能。
1. Java集合框架概述
Java集合框架提供了一组接口和类，用于存储和操作对象集合。它的核心接口包括：
- Collection: 集合层次结构的根接口，定义了集合的基本操作，如添加、删除、判断包含等。
- List: 有序集合，允许重复元素。
- Set: 无序集合，不允许重复元素。
- Map: 键值对集合，键不允许重复。
Java集合框架的设计目标是：
- 高性能: 提供高效的数据结构和算法，满足各种应用场景的需求。
- 易用性: 提供简洁的API，方便开发者使用。
- 扩展性: 允许开发者自定义集合类，满足特定的需求。
2. ArrayList：动态数组的实现
ArrayList是List接口的一个实现类，它基于动态数组实现。这意味着ArrayList可以根据需要动态地调整数组的大小。
2.1 ArrayList的核心数据结构
ArrayList的核心数据结构是一个Object数组：
transient Object[] elementData; // non-private to simplify nested class accesselementData用于存储ArrayList中的元素。transient关键字表示该字段不会被序列化。ArrayList还维护了一个size字段，用于记录ArrayList中元素的个数：
private int size;2.2 ArrayList的构造方法
ArrayList提供了多个构造方法：
ArrayList()：创建一个空的ArrayList，初始容量为10。ArrayList(int initialCapacity)：创建一个具有指定初始容量的ArrayList。ArrayList(Collection<? extends E> c)：创建一个包含指定集合元素的ArrayList。
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 ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}2.3 ArrayList的添加元素方法
ArrayList提供了add(E e)方法用于添加元素。当ArrayList的容量不足时，会自动扩容。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int DEFAULT_CAPACITY = 10;
private void grow(int minCapacity) {
// overflow-conscious code
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}add(E e)方法首先调用ensureCapacityInternal方法，确保ArrayList有足够的容量。如果容量不足，则调用grow方法扩容。grow方法会将ArrayList的容量扩容为原来的1.5倍。然后，将新元素添加到elementData数组的末尾。
2.4 ArrayList的删除元素方法
ArrayList提供了remove(int index)方法用于删除指定索引处的元素。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}remove(int index)方法首先调用rangeCheck方法，检查索引是否越界。然后，将指定索引处的元素删除，并将后面的元素向前移动。最后，将elementData数组的最后一个元素设置为null，以便垃圾回收器回收。
2.5 ArrayList的优缺点
优点：
- 查找速度快： ArrayList基于数组实现，可以通过索引直接访问元素，查找速度快。
- 动态扩容： ArrayList可以根据需要动态地调整数组的大小，避免了数组越界的问题。
缺点：
- 插入和删除元素速度慢： 在ArrayList中插入或删除元素时，需要移动后面的元素，效率较低。
- 占用内存空间： ArrayList需要占用一定的内存空间来存储元素，并且可能存在一定的空间浪费。
2.6 ArrayList的应用场景
ArrayList适用于以下场景：
- 需要频繁查找元素的场景。
- 元素个数不确定，需要动态扩容的场景。
3. HashMap：键值对存储的利器
HashMap是Map接口的一个实现类，它基于哈希表实现。HashMap可以存储键值对，其中键不允许重复。
3.1 HashMap的核心数据结构
HashMap的核心数据结构是一个Node数组：
transient Node<K,V>[] table;table用于存储HashMap中的元素。Node是HashMap的一个内部类，用于表示键值对：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
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 String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}Node包含四个字段：
hash：键的哈希值。key：键。value：值。next：指向下一个Node的指针，用于解决哈希冲突。
HashMap还维护了一个size字段，用于记录HashMap中元素的个数：
transient int size;以及一个threshold字段，用于记录HashMap的扩容阈值：
int threshold;还有一个loadFactor字段，用于记录HashMap的负载因子：
final float loadFactor;3.2 HashMap的构造方法
HashMap提供了多个构造方法：
HashMap()：创建一个空的HashMap，初始容量为16，负载因子为0.75。HashMap(int initialCapacity)：创建一个具有指定初始容量的HashMap，负载因子为0.75。HashMap(int initialCapacity, float loadFactor)：创建一个具有指定初始容量和负载因子的HashMap。HashMap(Map<? extends K, ? extends V> m)：创建一个包含指定Map元素的HashMap。
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.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;3.3 HashMap的put方法
HashMap提供了put(K key, V value)方法用于添加键值对。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final 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 for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}put(K key, V value)方法首先计算键的哈希值。然后，根据哈希值找到对应的桶（bucket）。如果桶为空，则将键值对添加到桶中。如果桶不为空，则遍历桶中的链表，查找是否已存在相同的键。如果存在相同的键，则更新对应的值。如果不存在相同的键，则将键值对添加到链表的末尾。当链表的长度超过TREEIFY_THRESHOLD时，会将链表转换为红黑树，以提高查找效率。当HashMap中的元素个数超过threshold时，会自动扩容。
3.4 HashMap的get方法
HashMap提供了get(Object key)方法用于获取指定键的值。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final 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[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}get(Object key)方法首先计算键的哈希值。然后，根据哈希值找到对应的桶。如果桶为空，则返回null。如果桶不为空，则遍历桶中的链表，查找是否已存在相同的键。如果存在相同的键，则返回对应的值。如果不存在相同的键，则返回null。如果该节点是TreeNode，则在树中查找。
3.5 HashMap的扩容机制
当HashMap中的元素个数超过threshold时，会自动扩容。扩容会将HashMap的容量扩大为原来的两倍。扩容后，需要重新计算每个元素的哈希值，并将元素重新分配到新的桶中。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap = 0, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}3.6 HashMap的优缺点
优点：
- 查找速度快： HashMap基于哈希表实现，可以通过键快速查找值。
- 高效的键值对存储： HashMap提供了高效的键值对存储机制。
缺点：
- 无序性： HashMap中的元素是无序的。
- 线程不安全： HashMap是线程不安全的，在多线程环境下使用需要进行同步处理。
- 扩容开销： HashMap的扩容操作会带来一定的性能开销。
3.7 HashMap的应用场景
HashMap适用于以下场景：
- 需要频繁查找键值对的场景。
- 对元素的顺序没有要求的场景。
4. 其他核心集合类
除了HashMap和ArrayList之外，Java集合框架还提供了其他一些核心集合类，例如：
- LinkedList: 基于链表实现，插入和删除元素速度快，但查找速度慢。
- HashSet: 基于哈希表实现，不允许重复元素。
- TreeSet: 基于红黑树实现，元素有序。
- TreeMap: 基于红黑树实现，键有序。
下表总结了这些集合类的特点：
| 集合类 | 数据结构 | 特点 | 适用场景 |
|---|---|---|---|
| ArrayList | 数组 | 查找快，插入/删除慢，动态扩容 | 频繁查找，元素个数不确定 |
| LinkedList | 链表 | 插入/删除快，查找慢 | 频繁插入/删除 |
| HashMap | 哈希表 | 查找快，无序，键不允许重复，线程不安全，扩容有开销 | 频繁查找键值对，对顺序没有要求 |
| HashSet | 哈希表 | 不允许重复元素，无序，线程不安全 | 存储不重复元素，对顺序没有要求 |
| TreeSet | 红黑树 | 不允许重复元素，有序 | 存储不重复元素，需要保持元素有序 |
| TreeMap | 红黑树 | 键有序，线程不安全 | 存储键值对，需要保持键有序 |
5. 设计哲学与最佳实践
通过分析这些核心集合类的源码，我们可以总结出以下设计哲学：
- 选择合适的数据结构： 不同的数据结构适用于不同的场景。例如，数组适用于查找，链表适用于插入和删除，哈希表适用于键值对存储，红黑树适用于有序存储。
- 平衡时间和空间复杂度： 在设计集合类时，需要在时间和空间复杂度之间进行权衡。例如，HashMap使用哈希表来提高查找速度，但会占用更多的内存空间。
- 提供高效的API： 集合类应该提供简洁、高效的API，方便开发者使用。
- 考虑线程安全性： 在多线程环境下使用集合类时，需要考虑线程安全性。例如，可以使用ConcurrentHashMap来代替HashMap，以提高并发性能。
在使用Java集合框架时，应该遵循以下最佳实践：
- 根据实际需求选择合适的集合类： 不要盲目使用ArrayList或HashMap，而是应该根据实际需求选择最合适的集合类。
- 设置合适的初始容量： 在创建集合类时，可以设置合适的初始容量，以避免频繁扩容带来的性能开销。
- 使用泛型： 使用泛型可以提高代码的类型安全性。
- 注意线程安全性： 在多线程环境下使用集合类时，需要注意线程安全性。
总结与思考：集合类的选择与应用
理解ArrayList和HashMap等核心集合类的实现原理，有助于我们根据实际应用场景选择最合适的数据结构。 熟悉这些类的优点和缺点，能够帮助我们写出更高效、更健壮的代码。