資訊專欄INFORMATION COLUMN
摘要：迭代器迭代器簡單來說就是用來對集合的元素進(jìn)行遍歷操作的。調(diào)用集合的或方法將實(shí)例出從第一個結(jié)點(diǎn)開始的迭代器，也可以傳入?yún)?shù)作為第一個迭代的結(jié)點(diǎn)。
基礎(chǔ)集合 Collection
List
- LinkedList
- ArrayList
- Vector
- Stack
Queue
- PriorityQueue
- Deque
- ArrayDeque
Set
- HashSet
- LinkedHashSet
- TreeSet
Map
HashMap
- LinkedHashMap - TreeMap
HashTable
List LinkedList先看字段聲明
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node last;
我們看到有三個字段，分別是size、first、last，命名和注釋已非常簡單明顯，不難看出這是一個雙向鏈表。
注意到這三個字段都有個修飾關(guān)鍵字transient，這是比較不常見的，這是與類序列化相關(guān)的內(nèi)容，為了不讓這篇將集合的文章太跳，將會在寫完LinkedList相關(guān)的內(nèi)容后再講述。
最核心內(nèi)容，LinkedList的信息儲存單元是一個內(nèi)部類Node。
三個字段分別是前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)、節(jié)點(diǎn)內(nèi)容，沒什么特別的。
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
關(guān)于對鏈表的增刪結(jié)點(diǎn)，獲取結(jié)點(diǎn)，更換結(jié)點(diǎn)等操作比較簡單，下面只挑在某個結(jié)點(diǎn)前插入一個結(jié)點(diǎn)的操作進(jìn)行講述：
/**
* Inserts element e before non-null Node succ.
*/
//非public方法，public void add(int index, E element)為上層方法
void linkBefore(E e, Node succ) {//在succ結(jié)點(diǎn)前加入以e為值的結(jié)點(diǎn)
// assert succ != null;
final Node pred = succ.prev;
//1.將e構(gòu)造成結(jié)點(diǎn)，后繼結(jié)點(diǎn)為succ，前驅(qū)結(jié)點(diǎn)為succ的前驅(qū)結(jié)點(diǎn)，這用在e結(jié)點(diǎn)的角度就已經(jīng)加入到鏈表中succ前面的位置了，但此時e結(jié)點(diǎn)的前后結(jié)點(diǎn)指針還未指向e
final Node newNode = new Node<>(pred, e, succ);
//2.將e后面的結(jié)點(diǎn)即succ的前驅(qū)指向e
succ.prev = newNode;
//3.將e前面的結(jié)點(diǎn)的后繼指向e，若e此時為第一個結(jié)點(diǎn)則將first指針指向e
if (pred == null)
first = newNode;
else
pred.next = newNode;
//4.鏈表容量增加1
size++;
//5.鏈表修改次數(shù)記錄加1
modCount++;
}
通過了解在某個結(jié)點(diǎn)前插入一個結(jié)點(diǎn)這個操作的實(shí)現(xiàn)，不難發(fā)現(xiàn)鏈表一個兩個非常重要的特點(diǎn)，一是方便動態(tài)增刪結(jié)點(diǎn)，只需要調(diào)整鏈表局部位置的結(jié)點(diǎn)指向，二是隨機(jī)查詢速度較慢，因?yàn)樾枰獜念^結(jié)點(diǎn)一直向前查詢。
注意到，其實(shí)會對鏈表結(jié)構(gòu)發(fā)生改變的每一個操作，鏈表都會將修改次數(shù)記錄modCount加1，那這個modCount的作用是什么呢？其實(shí)是用于輔助迭代器正常使用的。
迭代器簡單來說就是用來對集合的元素進(jìn)行遍歷操作的。調(diào)用集合的iterator()或listIterator()方法將實(shí)例出從第一個結(jié)點(diǎn)開始的迭代器，也可以傳入int參數(shù)作為第一個迭代的結(jié)點(diǎn)。
private class ListItr implements ListIterator{ private Node lastReturned; private Node next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } public void forEachRemaining(Consumer action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
從內(nèi)部類ListItr看到，LinkedList的迭代器可以雙向進(jìn)行迭代的，迭代過程中只能使用迭代器的add()、set()、remove()對鏈表進(jìn)行修改，為什么重點(diǎn)標(biāo)出只能，因?yàn)楹芏嘈率趾苋菀讓懗鲞@樣的代碼：
//雖然沒有顯式地使用迭代器，但其實(shí)底層實(shí)現(xiàn)也是使用迭代器進(jìn)行迭代
for (Object o : linkedList) {
if(o.equals(something)){
linkedList.remove(o);
}
}
這樣是會報錯的，通過注釋，我們可以看到這是在迭代過程中是不允許直接修改鏈表的結(jié)構(gòu)的，fail-fast機(jī)制，可以看到，在迭代器的代碼中，有個非public方法checkForComodification(),迭代器中幾乎每個操作都會調(diào)用一下該方法，而該方法的方法體內(nèi)僅僅做的一件事就是檢查鏈表的modCount是否等于迭代器expectedModCount，不相等將拋出ConcurrentModificationException，從而實(shí)現(xiàn)不允許在迭代過程中直接修改鏈表結(jié)構(gòu)，至于為什么要這樣做則自行研究上述迭代的代碼看如果在迭代過程中修改了鏈表結(jié)構(gòu)會有什么錯誤發(fā)生。因此，正確的使用迭代器刪除元素應(yīng)該是像下面這樣：
while (iterator.hasNext()){
Object o = iterator.next();
if(o.equals(something)){
iterator.remove();
}
}
迭代器的高級用法
從LinkedList的迭代器代碼中可以看到一個方法forEachRemaining(),我們查看Iterator接口的描述：
/**
* Performs the given action for each remaining element until all elements
* have been processed or the action throws an exception. Actions are
* performed in the order of iteration, if that order is specified.
* Exceptions thrown by the action are relayed to the caller.
*
* @implSpec
* The default implementation behaves as if:
*
{@code
* while (hasNext())
* action.accept(next());
* }
*
* @param action The action to be performed for each element
* @throws NullPointerException if the specified action is null
* @since 1.8
*/
default void forEachRemaining(Consumer action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
看到該方法是在jdk1.8版本后才加入的，用于實(shí)現(xiàn)對集合每個元素做特定操作，傳入?yún)?shù)為Consumer接口，Consumer接口是一個只有一個方法需要實(shí)現(xiàn)的接口，所以不難看出其實(shí)該方法是用于配合lambda來使用的，以此更加簡化java的表達(dá)，舉例：
iterator.forEachRemaining(System.out::println);
iterator.forEachRemaining(item -> {
System.out.println(item);
});
高級迭代器
繼續(xù)看Linked的源代碼，我們看到一個Spliterator，這是jdk1.8才加入的迭代器，該迭代器其實(shí)就是可分割的迭代器，可分割，意味著可以將迭代過程分給不同的線程去完成，從而提高效率。為了方便，源碼分析將在下述代碼以注釋方式進(jìn)行：
@Override
public Spliterator spliterator() {
return new LLSpliterator(this, -1, 0);
}
/** A customized variant of Spliterators.IteratorSpliterator */
//變種的IteratorSpliterator，區(qū)別：IteratorSpliterator使用interator進(jìn)行迭代，LLSpliterator直接使用Node的next指針迭代，原則上迭代速度更快
static final class LLSpliterator implements Spliterator {
static final int BATCH_UNIT = 1 << 10; // batch array size increment;分割的長度增加單位，每分割一次下次分割長度增加1024
static final int MAX_BATCH = 1 << 25; // max batch array size;最大分割長度，大于2^25分割長度將不再增加
final LinkedList list; // null OK unless traversed
Node current; // current node; null until initialized
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
int batch; // batch size for splits;當(dāng)前分割長度
LLSpliterator(LinkedList list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getEst() {
int s; // force initialization
final LinkedList lst;
if ((s = est) < 0) {
if ((lst = list) == null)
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first;
s = est = lst.size;
}
}
return s;
}
public long estimateSize() { return (long) getEst(); }
//分割出batch長度的Spliterator
public Spliterator trySplit() {
Node p;
int s = getEst();
if (s > 1 && (p = current) != null) {
//每次分割長度增加BATCH_UNIT，達(dá)到MAX_BATCH便不再增加
int n = batch + BATCH_UNIT;
if (n > s)
n = s;
if (n > MAX_BATCH)
n = MAX_BATCH;
//將需要分割的元素生成數(shù)組
Object[] a = new Object[n];
int j = 0;
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p;
batch = j;
est = s - j;
//返回新的Spliterator，注意：新的Spliterator為ArraySpliterator類型，實(shí)現(xiàn)上有所區(qū)別，ArraySpliterator每次分割成一半一半，而IteratorSpliterator算術(shù)遞增
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
//遍歷當(dāng)前迭代器中所有元素并對獲取元素值進(jìn)行action操作（操作所有元素）
public void forEachRemaining(Consumer action) {
Node p; int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null;
est = 0;
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
//對當(dāng)前迭代元素的元素值進(jìn)行action操作（只操作一個元素）
public boolean tryAdvance(Consumer action) {
Node p;
if (action == null) throw new NullPointerException();
if (getEst() > 0 && (p = current) != null) {
--est;
E e = p.item;
current = p.next;
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
序列化和Transient
來自百度百科的解釋：
java語言的關(guān)鍵字，變量修飾符，如果用transient聲明一個實(shí)例變量，當(dāng)對象存儲時，它的值不需要維持。換句話來說就是，用transient關(guān)鍵字標(biāo)記的成員變量不參與序列化過程。
解釋了跟沒解釋差不多。好，其實(shí)對象存儲就是一個對象序列化的過程，下面提供一個程序以便更好的理解：
package Serializable;
import java.io.*;
public class SerializableTest {
private static void testSerializable(AbstractClass cl) throws IOException {
//依次讀取對象的各個字段值
System.out.printf("Minor version number: %d%n", cl.getMinorVer());
System.out.printf("Major version number: %d%n", cl.getMajorVer());
cl.showString();
System.out.println();
//將對象寫入硬盤
File file = new File("resource/ObjectRecords.txt");
if (!file.exists()) {
file.createNewFile();
}
try (FileOutputStream fos = new FileOutputStream(file);
ObjectOutputStream oos = new ObjectOutputStream(fos))
{
oos.writeObject(cl);
}
//置空對象的引用
cl = null;
//將對象重新從硬盤讀回
try (FileInputStream fis = new FileInputStream("resource/ObjectRecords.txt");
ObjectInputStream ois = new ObjectInputStream(fis))
{
cl = (AbstractClass) ois.readObject();
//依次讀取反序列化后的對象的各個字段值
System.out.printf("Minor version number: %d%n", cl.getMinorVer());
System.out.printf("Major version number: %d%n", cl.getMajorVer());
cl.showString();
System.out.println();
} catch (ClassNotFoundException cnfe) {
System.err.println(cnfe.getMessage());
}
}
public static void main(String[] args) throws IOException {
ClassSerializable cl1 = new ClassSerializable("string");
testSerializable(cl1);
ClassAllSerializable cl2 = new ClassAllSerializable("string");
testSerializable(cl2);
ClassNotSerializable cl3 = new ClassNotSerializable("string");
testSerializable(cl3);
}
}
從main方法可以看到這里用來測試的有三個類，分別是ClassSerializable、ClassAllSerializable、ClassNotSerializable，其中前兩個實(shí)現(xiàn)了Serializable接口，代表這兩個類是可以進(jìn)行序列化的，所以前兩個類的對象在進(jìn)行writeObject的時候不會報錯，而ClassNotSerializable則拋出java.io.NotSerializableException: Serializable.ClassNotSerializable，而前兩個類區(qū)別在于ClassSerializable所有字段均帶有Transient關(guān)鍵字，而ClassAllSerializable沒有，以下是程序輸出結(jié)果：
ClassSerializable called
Minor version number: 1
Major version number: 2
string
Minor version number: 0
Major version number: 0
null
ClassAllSerializable called
Minor version number: 1
Major version number: 2
string
Minor version number: 1
Major version number: 2
string
ClassNotSerializable called
Minor version number: 1
Major version number: 2
string
Exception in thread "main" java.io.NotSerializableException: Serializable.ClassNotSerializable
at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1184)
at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:348)
at Serializable.SerializableTest.testSerializable(SerializableTest.java:19)
at Serializable.SerializableTest.main(SerializableTest.java:42)
可以明顯看到，被transient修飾的字段經(jīng)過對象的序列化和反序列化后沒有被保存起來。
ArrayList先看字段聲明進(jìn)行初步分析：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
顯然，elementData是用來存儲元素的，也就是說ArrayList底層由數(shù)組維護(hù)的。
我們都知道，數(shù)組的大小初始化之后就是固定的，而數(shù)組表的元素是需要進(jìn)行增刪操作的，那么ArrayList是如何實(shí)現(xiàn)改變大小的呢？
不難想象，當(dāng)進(jìn)行add()操作的時候需要進(jìn)行擴(kuò)容：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
可以看到，重點(diǎn)是grow()方法，我們分析一下grow()的行為，參數(shù)變量minCapacity其實(shí)只是一個參考大小，通常為當(dāng)前大小加新增元素個數(shù)，grow首要考慮是將容量增加兩倍，若此時minCapacity更大的話才考慮取minCapacity，最后考慮值若比MAX_ARRAY_SIZE還要大則只能盡可能大進(jìn)行擴(kuò)容，最后使用Arrays.copyOf()進(jìn)行新建數(shù)組后復(fù)制。
其實(shí)Arraylist的所有add和remove操作都是基于Arrays.copyOf()進(jìn)行的，此時，ArrayList相較于LinkedList的特點(diǎn)很明顯了，一是因?yàn)槠涞讓邮菙?shù)組，所以ArrayList非常擅長與隨機(jī)讀取，二是因?yàn)榛贏rrays.copyOf()實(shí)現(xiàn)的原因，ArrayList增刪元素效率很低，而且導(dǎo)致內(nèi)存占用增加，提高GC觸發(fā)的幾率。
分別是foreach、removeIf、replaceAll、sort，其參數(shù)均可使用lumbda表達(dá)式，這四個方法來自不同的接口，其實(shí)LinkedList也有這幾個方法，不過LinkedList均使用的是上級接口的default實(shí)現(xiàn)，而ArrayList則對其進(jìn)行覆蓋了，下面將在代碼中增加注釋加以分析：
@Override
//default使用迭代器迭代，下面實(shí)現(xiàn)原理一樣，簡化檢查過程
public void forEach(Consumer action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
@Override
//default使用迭代器迭代，后滿足條件進(jìn)行remove()，上面也講了ArrayList隨機(jī)增減元素效率很低，所以default的實(shí)現(xiàn)是絕對不可取的，下面實(shí)現(xiàn)的思想其實(shí)是吧需要刪除的元素序號記錄下來，然后跳過這些元素把剩余元素按順序排回this.elementData中
public boolean removeIf(Predicate filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
@Override
@SuppressWarnings("unchecked")
//default使用迭代器迭代，下面實(shí)現(xiàn)原理一樣，簡化檢查過程
public void replaceAll(UnaryOperator operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
@Override
@SuppressWarnings("unchecked")
//default方法先將集合用toArray()轉(zhuǎn)換成數(shù)組再用Arrays.sort,而這對于ArrayList來說肯定是多余的，因?yàn)锳rrayList的元素容器就是數(shù)組
public void sort(Comparator c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
Vector和Stack
簡單翻看了Vector的源碼和注釋，發(fā)現(xiàn)它在jdk1.0就存在的，而ArrayList、LinkedList這種都是jdk1.2才增加的，然后在jdk1.2版本的時候稍微改造增加了對List的實(shí)現(xiàn)，而其大部分內(nèi)容和ArrayList沒什么大的差別，只是對public方法加上了synchronized關(guān)鍵字，也就是說jdk1.2以后Vector其實(shí)相當(dāng)于是線程安全的ArrayList，這一點(diǎn)注釋上也有提及：
/** ... *As of the Java 2 platform v1.2, this class was retrofitted to * implement the {@link List} interface, making it a member of the * * Java Collections Framework. Unlike the new collection * implementations, {@code Vector} is synchronized. If a thread-safe * implementation is not needed, it is recommended to use {@link * ArrayList} in place of {@code Vector}. ... */
而Stack，繼承自Vector，在它之上增加了棧的操作（push、pop）。
在注釋中我們也注意到，對棧這種后進(jìn)先出的操作也在雙端隊(duì)列Deque接口的實(shí)現(xiàn)中提供，例子給出的是ArrayDeque，關(guān)于隊(duì)列及雙端隊(duì)列我們后續(xù)在講：
/** ... *Queue PriorityQueueA more complete and consistent set of LIFO stack operations is * provided by the {@link Deque} interface and its implementations, which * should be used in preference to this class. For example: *
{@code * Deque... */stack = new ArrayDeque ();}
我們先看Queue接口方法：
public interface Queueextends Collection { /** * Inserts the specified element into this queue if it is possible to do so * immediately without violating capacity restrictions, returning * {@code true} upon success and throwing an {@code IllegalStateException} * if no space is currently available. * * @param e the element to add * @return {@code true} (as specified by {@link Collection#add}) * @throws IllegalStateException if the element cannot be added at this * time due to capacity restrictions * @throws ClassCastException if the class of the specified element * prevents it from being added to this queue * @throws NullPointerException if the specified element is null and * this queue does not permit null elements * @throws IllegalArgumentException if some property of this element * prevents it from being added to this queue */ boolean add(E e); /** * Inserts the specified element into this queue if it is possible to do * so immediately without violating capacity restrictions. * When using a capacity-restricted queue, this method is generally * preferable to {@link #add}, which can fail to insert an element only * by throwing an exception. * * @param e the element to add * @return {@code true} if the element was added to this queue, else * {@code false} * @throws ClassCastException if the class of the specified element * prevents it from being added to this queue * @throws NullPointerException if the specified element is null and * this queue does not permit null elements * @throws IllegalArgumentException if some property of this element * prevents it from being added to this queue */ boolean offer(E e); /** * Retrieves and removes the head of this queue. This method differs * from {@link #poll poll} only in that it throws an exception if this * queue is empty. * * @return the head of this queue * @throws NoSuchElementException if this queue is empty */ E remove(); /** * Retrieves and removes the head of this queue, * or returns {@code null} if this queue is empty. * * @return the head of this queue, or {@code null} if this queue is empty */ E poll(); /** * Retrieves, but does not remove, the head of this queue. This method * differs from {@link #peek peek} only in that it throws an exception * if this queue is empty. * * @return the head of this queue * @throws NoSuchElementException if this queue is empty */ E element(); /** * Retrieves, but does not remove, the head of this queue, * or returns {@code null} if this queue is empty. * * @return the head of this queue, or {@code null} if this queue is empty */ E peek(); }
element()和peek()均是獲取隊(duì)列頭元素，但不刪除，區(qū)別是在隊(duì)列空時peek()返回null，element()拋出NoSuchElementException。
對于隊(duì)列來說，我們知道，普通隊(duì)列的特性是先進(jìn)先出（區(qū)別于棧的先進(jìn)后出），比如LinkedList，隊(duì)列的特有方法offer()和poll()就是用來對隊(duì)列插入和取出元素的，而另外兩個方法add()和remove()通常也是在隊(duì)列尾插入在隊(duì)列頭取出，因此通常與offer()和poll()實(shí)現(xiàn)的其實(shí)是一樣的，但是在使用隊(duì)列時，使用后者方法名語義更強(qiáng)。而PriorityQueue與普通的隊(duì)列不同，因?yàn)樵赜袃?yōu)先級，所以不具備先進(jìn)先出的特點(diǎn)，下面看PriorityQueue的源碼,還是先來看字段信息：
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements"
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
*/
private int size = 0;
/**
* The comparator, or null if priority queue uses elements"
* natural ordering.
*/
private final Comparator comparator;
/**
* The number of times this priority queue has been
* structurally modified. See AbstractList for gory details.
*/
transient int modCount = 0; // non-private to simplify nested class access
很明顯，queue是底層存儲元素的隊(duì)列，是一個Object數(shù)組，但是不同的是，該數(shù)組其實(shí)代表的是一顆平衡二叉堆（上面的元素小，下面的元素大），queue[n]為父節(jié)點(diǎn)時，queue[2n+1]為左孩子，queue[2(n+1)]為右孩子，其大小關(guān)系也就是優(yōu)先級關(guān)系通過comparator作比較決定。
繼續(xù)看插入過程的源碼：
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
可以看到，插入的過程充分體現(xiàn)堆的特點(diǎn)，從二叉樹的最后的位置依次向上與父節(jié)點(diǎn)比較，比父節(jié)點(diǎn)小（優(yōu)先級大）則將父節(jié)點(diǎn)下移，繼續(xù)比較，知道比父節(jié)點(diǎn)大停止并且插入，目的是將優(yōu)先級小的放到堆的下面使得取出時優(yōu)先取出優(yōu)先級大的元素，下面看取出元素的方法：
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable key = (Comparable)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
取出０號元素（即優(yōu)先級最大的元素），然后從０號的左孩子依次向上填補(bǔ)直至最后的元素小于當(dāng)前左孩子則填補(bǔ)。
DequeDeque繼承于queue，區(qū)別在于Deque是一個雙端隊(duì)列，兩頭均可當(dāng)作隊(duì)列頭或隊(duì)列尾。
ArrayDeque比較有代表性的雙端隊(duì)列實(shí)現(xiàn)為ArrayDeque，基于數(shù)組實(shí)現(xiàn)的雙端循環(huán)隊(duì)列,雖然使用對象模擬C語言前驅(qū)后繼指針的方式實(shí)現(xiàn)雙端循環(huán)隊(duì)列更為直觀，但是在不需要隨機(jī)增刪節(jié)點(diǎn)情況下在java使用數(shù)組實(shí)現(xiàn)比模擬鏈表開銷更小，下面直接看源碼：
/**
* The array in which the elements of the deque are stored.
* The capacity of the deque is the length of this array, which is
* always a power of two. The array is never allowed to become
* full, except transiently within an addX method where it is
* resized (see doubleCapacity) immediately upon becoming full,
* thus avoiding head and tail wrapping around to equal each
* other. We also guarantee that all array cells not holding
* deque elements are always null.
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
我們看到有兩個int字段，從名字上看也能判斷到是頭尾指針（并不是說它是真的指針，就是那個效果相當(dāng)于指針），方法源碼不贅述，循環(huán)的原理就是移動頭尾指針，而不需要說比如獲取0號元素后將后面元素依次向前移動，這種操作十分花費(fèi)開銷，增加頭尾指針只需直接修改頭尾指針數(shù)值，因此整個數(shù)組雖然是線性的但是可以實(shí)現(xiàn)環(huán)形的效果。
Set HashSet、LinkedHashSet和TreeSet依然先看看字段信息，這個PRESENT先不理，直接看不太知道是什么，先看這個map，看到這個map其實(shí)可以猜HashSet的底層是通過HashMap儲存的了：
