Java 集合是包括了 java.util.Collection
和 java.util.Map
两个接口的集合类的总称。
下面的图展示了它们的继承关系。
Collection
Collection
是集合的根接口,表示一组对象的集合。所有 Collection
都拥有以下方法:
-
boolean add(E e)
:添加元素e
-
boolean addAll(Collection<? extends E> c)
:添加集合c
中的所有元素 -
void clear()
:清空集合 -
boolean contains(Object o)
:判断集合中是否包含元素o
-
boolean containsAll(Collection<?> c)
:判断集合中是否包含集合c
中的所有元素 -
boolean isEmpty()
:判断集合是否为空 -
Iterator<E> iterator()
:返回集合的迭代器 -
boolean remove(Object o)
:删除元素o
,如果有多个满足条件的元素,只删除第一个 -
boolean removeAll(Collection<?> c)
:删除集合c
中的所有元素 -
boolean retainAll(Collection<?> c)
:删除集合中不在集合c
中的所有元素 -
int size()
:返回集合的元素个数 -
Object[] toArray()
:将集合转换为数组
集合的遍历方式有三种:
-
使用
for
循环遍历集合for (int i = 0; i < collection.size(); i++) { System.out.println(collection.get(i)); }
-
使用
for-each
循环遍历集合for (Object o : collection) { System.out.println(o); }
-
使用迭代器遍历集合,可以在遍历时删除元素
Iterator<Object> iterator = collection.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); iterator.remove(); }
-
使用
ListIterator
遍历集合,它支持双向遍历,并且可以在遍历时修改集合ListIterator<Object> listIterator = collection.listIterator(); while (listIterator.hasNext()) { System.out.println(listIterator.next()); listIterator.remove(); }
-
使用
Stream
遍历集合collection.stream().forEach(System.out::println) .collect(Collectors.toList());
-
使用
forEach
遍历集合collection.forEach(System.out::println);
List
List
是 Collection
的子接口,表示一个有序的集合。它允许重复元素,并且可以通过索引访问元素。List
分为三类
ArrayList
ArrayList
:基于动态数组实现,支持随机访问,适合频繁读取的场景
除了 Collection
的方法外,它包括了以下方法:
-
E get(int index)
:返回指定索引位置的元素 -
int indexOf(Object o)
:返回元素o
在列表中第一次出现的位置,如果不存在则返回 -1 -
int lastIndexOf(Object o)
:返回元素o
在列表中最后一次出现的位置,如果不存在则返回 -1 -
E set(int index, E element)
:将指定索引位置的元素替换为element
-
List<E> subList(int fromIndex, int toIndex)
:返回一个新的List
,包含 \([\text{fromIndex}, \text{toIndex})\) 范围内的元素
ArrayList
的元素本身存储在一个 Object[]
数组中,里面还有一个成员变量 size
,表示当前元素的个数。
transient Object[] elementData;
private int size;
transient
关键字表示这些变量不会被序列化。
ArrayList
的默认初始容量为 10。容量不足时,它会创建 1.5 倍大小的新数组,并将旧数组中的元素复制到新数组中。
private static final int DEFAULT_CAPACITY = 10;
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
LinkedList
LinkedList
:基于双向链表实现,支持频繁插入和删除的场景
它包括了以下方法:
-
void addFirst(E e)
:在列表的开头添加元素e
-
void addLast(E e)
:在列表的末尾添加元素e
-
E getFirst()
:返回列表的第一个元素 -
E getLast()
:返回列表的最后一个元素 -
E removeFirst()
:删除列表的第一个元素并返回它 -
E removeLast()
:删除列表的最后一个元素并返回它
LinkedList
存储了头节点、尾节点、以及元素的个数。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
每个节点都包含了具体的元素、前后两个指针。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
至于其插入、删除等操作就是平平无奇的双向链表操作了。
Vector
Vector
是一个动态数组,支持随机访问。它基本就是 ArrayList
的古早版本。
Vector
的方法与 ArrayList
基本相同。
Vector
有个子类 Stack
,表示一个后进先出的集合。它额外包括了以下方法:
-
E push(E item)
:添加元素item
-
E pop()
:删除并返回栈顶元素 -
E peek()
:返回栈顶元素 -
boolean empty()
:判断栈是否为空 -
int search(Object o)
:返回元素o
在栈中的位置,如果不存在则返回 -1
Vector
是线程安全的,而如果不需要线程安全,不建议使用 Vector
,而是使用 ArrayList
。
它使用数组来存储元素。当容量不足时,它会创建两倍大小的新数组,并将旧数组中的元素复制到新数组中。
Set
Set
是 Collection
的子接口,表示一个不允许重复元素的集合。我们正常会使用 HashSet
和 TreeSet
。
HashSet
HashSet
:基于哈希表实现,支持快速查找和插入
它的方法与 Collection
相同
他有一个有序的子类 LinkedHashSet
,它保持插入顺序。
TreeSet
TreeSet
:基于红黑树实现,支持有序的元素
除了 Collection
的方法外,它包括了以下方法:
-
E first()
:返回集合中的第一个元素 -
E last()
:返回集合中的最后一个元素 -
E poolFirst()
:删除集合中的第一个元素并返回它 -
E poolLast()
:删除集合中的最后一个元素并返回它 -
SortedSet<E> subSet(E fromElement, E toElement)
:返回一个新的SortedSet
,包含 \([\text{fromElement}, \text{toElement})\) 范围内的元素 -
SortedSet<E> headSet(E toElement)
:返回一个新的SortedSet
,包含 \([, \text{toElement})\) 范围内的元素 -
SortedSet<E> tailSet(E fromElement)
:返回一个新的SortedSet
,包含 \([\text{fromElement}, ]\) 范围内的元素
TreeSet
是有序的,它的元素必须实现 Comparable
接口,或者在创建 TreeSet
时传入一个 Comparator
对象。
Queue
Queue
是 Collection
的子接口,表示一个先进先出的集合。它额外包括了以下方法:
-
boolean offer(E e)
:添加元素e
-
E poll()
:删除并返回队列的第一个元素 -
E peek()
:返回队列的第一个元素 -
E element()
:返回队列的第一个元素
虽然也能使用 add
和 remove
方法,但不推荐使用,因为它们在队列为空时会抛出异常。相比之下,offer
和 poll
方法在队列为空时会返回 null
。
Queue
有两个重要的实现类:
PriorityQueue
PriorityQueue
:基于堆实现,支持优先级队列。
它的方法与 Queue
相同。
PriorityQueue
默认情况下是小根堆,如果想要实现大根堆,可以在创建时传入一个 Comparator
对象。以下三种写法都是可以的:
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
ArrayDeque
ArrayDeque
:双端队列,支持在两端添加和删除元素
它额外包括了以下方法:
-
boolean offerFirst(E e)
:在队列的开头添加元素e
-
boolean offerLast(E e)
:在队列的末尾添加元素e
-
E peekFirst()
:返回队列的第一个元素 -
E peekLast()
:返回队列的最后一个元素 -
E pollFirst()
:删除队列的第一个元素并返回它 -
E pollLast()
:删除队列的最后一个元素并返回它 -
E getFirst()
:返回队列的第一个元素 -
E getLast()
:返回队列的最后一个元素
Map
Map
是一个键值对集合,表示一组映射关系。它不允许重复的键,但允许重复的值。
Map
的方法包括:
-
void clear()
:清空所有键值对 -
boolean containsKey(Object key)
:判断是否包含键key
-
boolean containsValue(Object value)
:判断是否包含值value
-
V get(Object key)
:返回键key
对应的值 -
V put(K key, V value)
:添加键值对key
和value
-
void putAll(Map<? extends K, ? extends V> m)
:添加Map
m
中的所有键值对 -
V remove(Object key)
:删除键key
对应的键值对 -
Set entrySet()
:返回所有键值对的集合,集合中的元素是Map.Entry
对象-
K getKey()
:返回键 -
V getValue()
:返回值 -
V setValue(V value)
:设置值并返回旧值
-
-
Set keySet()
:返回所有键的集合 -
Collection values()
:返回所有值的集合 -
boolean isEmpty()
:判断Map
是否为空 -
int size()
:返回键值对的个数 -
V getOrDefault(Object key, V defaultValue)
:返回键key
对应的值,如果不存在则返回defaultValue
-
V putIfAbsent(K key, V value)
:添加键值对key
和value
,如果键key
已经存在则不添加 -
void forEach(BiConsumer<? super K, ? super V> action)
:对每个键值对执行操作action
例如想要将
Map
中的每个值加 1,可以这样写:map.forEach((k, v) -> { map.put(k, v + 1); });
-
V replace(K key, V value)
:将键key
对应的值替换为value
,如果键key
不存在则不替换
Map
有多个实现类,最常用的有:
HashMap
HashMap
基于哈希表实现,支持快速查找和插入。
与其类似的还有:
-
TreeMap
:基于红黑树实现,支持有序的键 -
LinkedHashMap
:与HashMap
类似,但保持插入顺序
HashMap
以 Entry
对象的形式存储键值对。
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;
return o instanceof Map.Entry<?, ?> e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}
}
然后将这些 Entry
对象存储在一个数组中,数组的每个元素称为一个桶(bucket)。
transient Node<K,V>[] table;
HashMap
的默认初始容量为 16,最大容量为 \(2^30\)。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
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);
}
然而,这个指定的初始容量并不是直接用来创建数组的,而是用来计算真实的初始容量
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
这个函数的作用是返回大于等于 cap
的最小的 2 的幂次方。例如 cap
为 20 时,返回 32。
HashMap
的负载因子是一个浮点数,表示数组的使用率。默认值为 0.75。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
元素放入 HashMap
时,会先计算出它的哈希值,然后对数组的长度取模,得到它在数组中的位置。不过,它用了位运算来优化:
(tab.length - 1) & hash;
HashMap
处理哈希冲突的方式是链地址法,即每个桶中存储一个链表或则红黑树。
其中,由于 HashMap
在历史原因的影响,并不强制要求键实现 compareTo
方法,因此它使用了一套自己的方法来比较键的大小。
- 先比较 hash 大小
- 如果键实现了
Comparable
接口,则使用它的compareTo
方法 - 否则调用
tieBreakOrder
方法
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
我们来看它的插入操作:
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;
}
这个函数做了这样几件事情:
- 如果数组不存在或者长度为 0,则调用扩容方法创建一个新的数组
- 如果要插入的键已经存在,更具是否允许重复键的标志,替换为新值
- 如果不存在,则创建一个新的
Node
对象,并将它插入到链表或者红黑树中 -
如果链表的长度超过了 8,则将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
如果红黑树的长度小于 6,则将红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
- 如果键值对数量大于阈值,则扩容
接下来来看扩容的代码:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, 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;
}
它做了这样几件事情:
-
计算新的容量和阈值
-
如果当前数组已经初始化过了
- 如果旧的容量 \(\geq 2^{30}\),则不再扩容,并将阈值设为最大值
- 如果新的容量 \(< 2^{30}\),且旧的容量 \(\geq 16\),则将容量翻倍、阈值也翻倍
-
如果阈值大于 0,且桶未被初始化过
- 新的容量为阈值
- 新的阈值为容量乘以负载因子
-
如果阈值为 0 且桶未初始化过
- 新容量为默认值 16
- 新阈值为容量乘以负载因子,即 12
-
-
重新分配桶内的元素
-
如果桶内是链表,计算
hash & oldCap
,决定元素放入新桶的哪个位置- 如果
hash & oldCap == 0
,则放入loHead
- 否则放入
hiHead
- 如果
-
如果桶内是红黑树,则调用
split
方法将它拆分成两个红黑树- 红黑树在插入时,使用一个指针维护了插入的顺序,每个节点都有一个
next
指针指向下一个节点 - 这使得它可以像链表一样拆分,它会先拆分为两个链表,然后再根据条件决定是否树化
- 红黑树在插入时,使用一个指针维护了插入的顺序,每个节点都有一个
-
LinkedHashMap
LinkedHashMap
与 HashMap
类似,但保持插入顺序。
具体来讲,就是它额外使用了两个指针来构成了双向链表。
并发
Java 同时提供了一些线程安全的集合类,位于 java.util.concurrent
包中。
CopyOnWriteArrayList
CopyOnWriteArrayList
为 ArrayList
提供了写时复制的功能。
它的实现思路就是一把大锁保平安,数组本身也用了 volatile
关键字来保证可见性。
final transient Object lock = new Object();
private transient volatile Object[] array;
它的读操作没有锁,因为它是线程安全的:
- 首先直接获取整个数组的引用
- 然后再根据索引获取元素
而写操作则是直接 synchronized
整个方法。
public boolean add(E e) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
es = Arrays.copyOf(es, len + 1);
es[len] = e;
setArray(es);
return true;
}
}
在这个方法中,它首先复制出了一份数组,然后在这份数组上进行操作,最后再将它替换回去。
这把大锁保证了同时只有一个线程能操作数组。
它的删除使用了类似的方法。
public E remove(int index) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
E oldValue = elementAt(es, index);
int numMoved = len - index - 1;
Object[] newElements;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len - 1);
else {
newElements = new Object[len - 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index + 1, newElements, index,
numMoved);
}
setArray(newElements);
return oldValue;
}
}
ConcurrentHashMap
ConcurrentHashMap
是一个线程安全的哈希表,支持高并发的读写操作。
与 HashMap
不同,ConcurrentHashMap
使用了分段锁的机制来提高并发性能。在 JDK 1.8 之后,它采用了 CAS + synchronized
的方式来保证线程安全。
它的核心数据结构与 HashMap
类似,也是一个数组 + 链表/红黑树的结构:
transient volatile Node<K,V>[] table;
不过,它的 Node
类使用了 volatile
关键字来保证可见性:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
// ...existing code...
}
它的插入操作使用了 CAS
和 synchronized
来保证线程安全:
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
// ...existing code...
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
这个方法的核心思路是:
- 如果桶为空,使用
CAS
操作直接插入新节点 - 如果桶正在扩容,帮助扩容
- 否则对桶的头节点加锁,然后在链表或红黑树中插入元素
读操作则不需要加锁,因为 val
和 next
都是 volatile
的:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap
的扩容也是分段进行的,每次只扩容一部分桶,这样可以减少锁的竞争。
ConcurrentLinkedQueue
ConcurrentLinkedQueue
是一个基于链表实现的线程安全的无界队列。
它使用了 CAS
操作来保证线程安全,而不是使用锁。
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
private static class Node<E> {
volatile E item;
volatile Node<E> next;
// ...existing code...
}
它的插入操作使用了 CAS
来保证线程安全:
public boolean offer(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
if (p.casNext(null, newNode)) {
if (p != t)
casTail(t, newNode);
return true;
}
}
else if (p == q)
p = (t != (t = tail)) ? t : head;
else
p = (p != t && t != (t = tail)) ? t : q;
}
}
Comments