引言
Java集合框架是Java语言中一个非常重要的组成部分,它提供了丰富的数据结构和算法,使得处理数据变得更加高效和方便。本文将深入浅出地剖析Java集合框架的源码,帮助读者更好地理解其原理和用法。
Java集合框架概述
Java集合框架主要包括以下几个接口和类:
Collection:集合框架的根接口,代表一组对象。List:实现了有序集合,允许重复元素。Set:实现了无序集合,不允许重复元素。Queue:实现了先进先出(FIFO)的队列。Deque:实现了双端队列,既可以作为队列使用,也可以作为栈使用。Map:实现了键值对映射。
集合框架实现类
Java集合框架提供了多种实现类,以下是常见的实现类及其特点:
ArrayList:基于动态数组实现,提供了快速的随机访问。LinkedList:基于双向链表实现,提供了高效的插入和删除操作。HashSet:基于哈希表实现,提供了快速的查找操作。TreeSet:基于红黑树实现,提供了有序集合。HashMap:基于哈希表实现,提供了快速的键值对查找。TreeMap:基于红黑树实现,提供了有序键值对映射。
源码剖析之旅
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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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 E get(int index) {
Object[] elementData = this.elementData;
return (E) elementData[index];
}
public E set(int index, E element) {
Object[] elementData = this.elementData;
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - size > 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;
}
private void rangeCheck(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
}
}
LinkedList
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 = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(E item, Node<E> prev, Node<E> next) {
this.item = item;
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;
}
size++;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
private E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
x.item = null;
x.next = x.prev = null;
return element;
}
}
HashSet
HashSet是基于哈希表实现的,以下是其核心代码:
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 0L;
transient int size = 0;
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 size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean containsAll(Collection<?> c) {
for (Object e : c) {
if (!map.containsKey(e)) {
return false;
}
}
return true;
}
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c) {
if (add(e)) {
modified = true;
}
}
return modified;
}
public boolean retainAll(Collection<?> c) {
boolean modified = false;
Set<E> set = map.keySet();
for (Iterator<E> it = set.iterator(); it.hasNext();) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
public boolean removeAll(Collection<?> c) {
boolean modified = false;
for (Object e : c) {
if (remove(e)) {
modified = true;
}
}
return modified;
}
public void clear() {
map.clear();
}
public Object clone() {
HashSet<E> newSet = new HashSet<>(this);
return newSet;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Iterator<E> i = iterator();
sb.append('{');
while (i.hasNext()) {
if (sb.length() > 1) {
sb.append(", ");
}
sb.append(i.next());
}
sb.append('}');
return sb.toString();
}
public static final Object PRESENT = new Object();
}
HashMap
HashMap是基于哈希表实现的,以下是其核心代码:
”`java
public class HashMap
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 value.equals(e.getValue());
}
} else {
if (e.getKey() == null || !key.equals(e.getKey())) {
return false;
}
}
return value.equals(e.getValue());
}
public final int hashCode() {
int h = hash;
if (h == 0) {
if (key instanceof String) {
return key.hashCode();
}
h = key.hashCode();
}
return h ^ (value == null ? 0 : value.hashCode());
}
}
transient int size = 0;
transient Node<K, V>[] table;
transient int threshold;
final float loadFactor;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
this.threshold = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
table = new Node[DEFAULT_INITIAL_CAPACITY];
}
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 = (int) (loadFactor * initialCapacity);
table = new Node[initialCapacity];
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putAll(m);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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 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;
}
final Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
return new Node<>(hash, key, value, next);
}
final void treeifyBin(Node<K, V>[] tab, int hash) {
if (tab.length >= TREEIFY_THRESHOLD) {
// Rehashing
resize();
}
}
final Node<K, V> untreeify(Node<K, V> root) {
Node<K, V>[] tab;
int index = (root.hash & (tab.length - 1));
Node<K, V> first = null;
for (Node<K, V> e = root; e != null; ) {
Node<K, V> next = e.next;
int h = e.hash;
if ((e.next = tab[index]) == null) {
tab[index] = e;
} else {
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
int loHash = 0, hiHash = 0;
for (; e != null; e = next) {
intehash = e.hash;
if ((e.next = next) == null) {
if (ehash < 0) {
if (loTail == null) {
loHead = e;
loTail = e;
} else {
loTail.next = e;
loTail = e;
}
loHash = h;
} else {
if (hiTail == null) {
hiHead = e;
hiTail = e;
} else {
hiTail.next = e;
hiTail = e;
}
hiHash = h;
}
}
}
if (loHead != null) {
tab[index] = loHead;
}
if (hiHead != null) {
tab[index] = hiHead;
}
}
}
}
final void resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int newCap = (oldCap >= MAXIMUM_CAPACITY) ? Integer.MAX_VALUE : (oldCap << 1) + 1;
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
transfer(newTab, oldTab);
table = newTab;
threshold = (int) (loadFactor * newCap);
}
final void transfer(Node<K, V>[] newTab, Node<K, V>[] oldTab) {
for (int i = 0; i < oldTab.length; ++i) {
Node<K, V> e = oldTab[i];
if (e != null) {
Node<K, V> next = e.next;
int hash = e.hash;
int index = (newTab.length - 1) & hash;
e.next = newTab[index];
newTab[index] = e;
}
}
}
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 &&
(e = tab[i = (n - 1) & hash]) != null) {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
while ((first = e.next) != null) {
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
e = first;
}
}
return null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
public V remove(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : removeNode(e);
}
final Node<K, V> removeNode(Node<K, V> e) {
Node<K, V> p = e.prev;
Node<K, V> next = e.next;
if (p == null)
table[e.hash] = next;
else
p.next = next;
if (next == null)
table[e.hash] = p;
else {
next.prev = p;
}
e.next = e.prev = null
