【查漏補缺】Java 集合詳解！
前言
資料結構作為每一個開發者不可回避的問題，而 Java 對于不同的資料結構提供了非常成熟的實作，這一個又一個實作既是面試中的難點，也是工作中必不可少的工具，在此，筆者經曆漫長的剖析，将其抽絲剝繭的呈現出來，在此僅作抛磚引玉，望得諸君高見，若君能有所獲則在下甚是不亦樂乎，若有疑惑亦願與諸君共求之！本文一共 3.5 W字，25 張圖，預計閱讀 2h。可以收藏這篇文章，用的時候防止找不到，這可能是你能看到的最詳細的一篇文章了。
完整版Java面試題位址：JAVA後端面試題整合
1、集合架構
Java整個集合架構如上圖所示（這兒不包括Map，Map的結構将放在集合後邊進行講述），可見所有集合實作類的最頂層接口為Iterable和Collection接口，再向下Collection分為了三種不同的形式，分别是List，Queue和Set接口，然後就是對應的不同的實作方式。
1.1頂層接口Iterable
//支援lambda函數接口
import java.util.function.Consumer;
public interface Iterable<T> {
//iterator()方法
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
複制代碼
Iterable接口中隻有iterator()一個接口方法，Iterator也是一個接口，其主要有如下兩個方法hasNext()和next()方法。
package java.util;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
boolean retainAll(Collection<?> c);
void clear();
int hashCode();
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
複制代碼
可見Collection的主要接口方法有：
2、List
List表示一串有序的集合，和Collection接口含義不同的是List突出有序的含義。
2.1 List接口
package java.util;
import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> {
<T> T[] toArray(T[] a);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
boolean equals(Object o);
E get(int index);
E set(int index, E element);
void add(int index, E element);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}
複制代碼
可見List其實比Collection多了添加方法add和addAll查找方法get,indexOf,set等方法，并且支援index下标操作。Collection 與 List 的差別？a. 從上邊可以看出Collection和List最大的差別就是Collection是無序的，不支援索引操作，而List是有序的。Collection沒有順序的概念。b. List中Iterator為ListIterator。c. 由a推導List可以進行排序，是以List接口支援使用sort方法。d. 二者的Spliterator操作方式不一樣。**為什麼子類接口裡重複申明父類接口呢?**官方解釋: 在子接口中重複聲明父接口是為了友善看文檔。比如在 java doc 文檔裡，在 List 接口裡也能看到 Collecion 聲明的相關接口。
2.2 List實作ArrayList
ArrayList是List接口最常用的一個實作類，支援List接口的一些列操作。
2.2.1 ArrayList繼承關系
2.2.2 ArrayList組成
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
//真正存放元素的數組
transient Object[] elementData; // non-private to simplify nested class access
private int size;
複制代碼
一定要記住ArrayList中的transient Object[] elementData，該elementData是真正存放元素的容器，可見ArrayList是基于數組實作的。
2.2.3 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;
}
複制代碼
- Object[] elementData 是ArrayList真正存放資料的數組。
- ArrayList支援預設大小構造，和空構造，當空構造的時候存放資料的Object[] elementData是一個空數組{}。
2.2.4 ArrayList中添加元素
>public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
複制代碼
注意ArrayList中有一個modCount的屬性，表示該執行個體修改的次數。（所有集合中都有modCount這樣一個記錄修改次數的屬性），每次增改添加都會增加一次該ArrayList修改次數，而上邊的add(E e)方法是将新元素添加到list尾部。
2.2.4 ArrayList擴容
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
複制代碼
可見當初始化的list是一個空ArrayList的時候，會直接擴容到DEFAULT_CAPACITY，該值大小是一個預設值10。而當添加進ArrayList中的元素超過了數組能存放的最大值就會進行擴容。注意到這一行代碼
int newCapacity = oldCapacity + (oldCapacity >> 1);
複制代碼
采用右移運算，就是原來的一般，是以是擴容1.5倍。比如10的二進制是1010，右移後變成101就是5。
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);
}
複制代碼
2.2.5 數組copy
Java 是無法自己配置設定空間的，是底層C和C++的實作。以 C 為例，我們知道 C 中數組是一個指向首部的指針，比如我們 C 語言對數組進行配置設定記憶體。Java 就是通過 arraycopy 這個 native 方法實作的數組的複制。
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
複制代碼
p = (int *)malloc(len*sizeof(int));
複制代碼
這樣的好處何在呢？**Java裡記憶體是由jvm管理的，而數組是配置設定的連續記憶體，而arrayList不一定是連續記憶體，當然jvm會幫我們做這樣的事，jvm會有内部的優化，會在後續的例子中結合問題來說明。
2.2.6 why?elementData用transient修飾？
- transient的作用是該屬性不參與序列化。
- ArrayList繼承了标示序列化的Serializable接口
- 對arrayList序列化的過程中進行了讀寫安全控制。是如何實作序列化安全的呢?
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
複制代碼
在序列化方法writeObject()方法中可以看到，先用預設寫方法，然後将size寫出，最後周遊寫出elementData，因為該變量是transient修飾的，所有進行手動寫出，這樣它也會被序列化了。那是不是多此一舉呢？
protected transient int modCount = 0;
複制代碼
當然不是，其中有一個關鍵的modCount, 該變量是記錄list修改的次數的，當寫入完之後如果發現修改次數和開始序列化前不一緻就會抛出異常，序列化失敗。這樣就保證了序列化過程中是未經修改的資料,保證了序列化安全。（java集合中都是這樣實作）
2.3 LinkedList
衆所周知LinkedList是一種連結清單結構，那麼Java裡LinkedList是如何實作的呢？
2.3.1 LinkedList繼承關系
可見LinkedList既是List接口的實作也是Queue的實作（Deque），故其和ArrayList相比LinkedList支援的功能更多，其可視作隊列來使用，當然下文中不強調其隊列的實作。
2.3.2 LinkedList的結構
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
複制代碼
LinkedList由一個頭節點和一個尾節點組成，分别指向連結清單的頭部和尾部。 LinkedList中Node源碼如下，由目前值item，和指向上一個節點prev和指向下個節點next的指針組成。并且隻含有一個構造方法，按照(prev, item, next)這樣的參數順序構造。
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;
}
}
複制代碼
那LinkedList裡節點Node是什麼結構呢？ LinkedList由一個頭節點，一個尾節點和一個預設為0的size構成，可見其是雙向連結清單。
<pre style="margin: 0px; padding: 0px; max-width: 100%; background-image: none; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; box-sizing: border-box !important; overflow-wrap: break-word !important;">transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
複制代碼
資料結構中連結清單的頭插法linkFirst和尾插法linkLast
/**
* Links e as first element. 頭插法
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element. 尾插法
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
複制代碼
2.3.3 LinkedList查詢方法
按照下标擷取某一個節點**：get方法，擷取第index個節點。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
複制代碼
node(index)方法是怎麼實作的呢？判斷index是更靠近頭部還是尾部，靠近哪段從哪段周遊擷取值。
Node<E> node(int index) {
// assert isElementIndex(index);
//判斷index更靠近頭部還是尾部
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
複制代碼
查詢索引修改方法，先找到對應節點，将新的值替換掉老的值。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
複制代碼
這個也是為什麼ArrayList随機通路比LinkedList快的原因**，LinkedList要周遊找到該位置才能進行修改，而ArrayList是内部數組操作會更快。
2.4.3 LinkedList修改方法
新增一個節點，可以看到是采用尾插法将新節點放入尾部。
public boolean add(E e) {
linkLast(e);
return true;
}
複制代碼
2.5 Vector
和ArrayList一樣，Vector也是List接口的一個實作類。其中List接口主要實作類有ArrayLIst，LinkedList，Vector，Stack，其中後兩者用的特别少。
2.5.1 vector組成
和ArrayList基本一樣。
//存放元素的數組
protected Object[] elementData;
//有效元素數量，小于等于數組長度
protected int elementCount;
//容量增加量，和擴容相關
protected int capacityIncrement;
複制代碼
2.5.2 vector線程安全性
vector是線程安全的，synchronized修飾的操作方法。
2.5.3 vector擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//擴容大小
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
複制代碼
看源碼可知，擴容當構造沒有capacityIncrement時，一次擴容數組變成原來兩倍，否則每次增加capacityIncrement。
2.5.4 vector方法經典示例
移除某一進制素
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
//複制數組，假設數組移除了中間某元素，後邊有效值前移1位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//引用null ，gc會處理
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
複制代碼
這兒主要有一個兩行代碼需要注意，筆者在代碼中有注釋。數組移除某一進制素并且移動後，一定要将原來末尾設為null，且有效長度減1。總體上vector實作是比較簡單粗暴的，也很少用到，随便看看即可。
2.6 Stack
Stack也是List接口的實作類之一，和Vector一樣，因為性能原因，更主要在開發過程中很少用到棧這種資料結構，不過棧在計算機底層是一種非常重要的資料結構，下邊将探讨下Java中Stack。
2.6.1 Stack的繼承關系
Stack繼承于Vector，其也是List接口的實作類。之前提到過Vector是線程安全的，因為其方法都是synchronized修飾的，故此處Stack從父類Vector繼承而來的操作也是線程安全的。
2.6.2 Stack的使用
正如Stack是棧的實作，故其主要操作為push入棧和pop出棧，而棧最大的特點就是LIFO（Last In First Out）。
Stack<String> strings = new Stack<>();
strings.push("aaa");
strings.push("bbb");
strings.push("ccc");
System.err.println(strings.pop());
複制代碼
上邊代碼可以看到，最後push入棧的字元串"ccc"也最先出棧。
2.6.3 Stack源碼
/**
* Stack源碼（Jdk8）
*/
public
class Stack<E> extends Vector<E> {
public Stack() {
}
//入棧，使用的是Vector的addElement方法。
public E push(E item) {
addElement(item);
return item;
}
//出棧，找到數組最後一個元素，移除并傳回。
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
private static final long serialVersionUID = 1224463164541339165L;
}
複制代碼
從Stack的源碼中可見，其用的push方法用的是Vector的addElement（E e）方法，該方法是将元素放在集合的尾部，而其pop方法使用的是Vector的removeElementAt(Index x)方法，移除并擷取集合的尾部元素，可見Stack的操作就是基于線性表的尾部進行操作的。
3、Queue
正如資料結構中描述，queue是一種先進先出的資料結構，也就是first in first out。可以将queue看作一個隻可以從某一段放元素進去的一個容器，取元素隻能從另一端取，整個機制如下圖所示，不過需要注意的是，隊列并沒有規定是從哪一端插入，從哪一段取出。
3.1 什麼是Deque
Deque英文全稱是Double ended queue，也就是俗稱的雙端隊列。就是說對于這個隊列容器，既可以從頭部插入也可以從尾部插入，既可以從頭部擷取，也可以從尾部擷取，其機制如下圖所示。
3.1.1 Java中的Queue接口
此處需要注意，Java中的隊列明确有從尾部插入，頭部取出，是以Java中queue的實作都是從頭部取出。
package java.util;
public interface Queue<E> extends Collection<E> {
//集合中插入元素
boolean add(E e);
//隊列中插入元素
boolean offer(E e);
//移除元素，當集合為空，抛出異常
E remove();
//移除隊列頭部元素并傳回，如果為空，傳回null
E poll();
//查詢集合第一個元素，如果為空，抛出異常
E element();
//查詢隊列中第一個元素，如果為空，傳回null
E peek();
}
複制代碼
Java queue常常使用的方法如表格所示，對于表格中接口和表格中沒有的接口方法差別為：隊列的操作不會因為隊列為空抛出異常，而集合的操作是隊列為空抛出異常。
3.1.2 Deque接口
package java.util;
public interface Deque<E> extends Queue<E> {
//deque的操作方法
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// 省略一堆stack接口方法和collection接口方法
}
複制代碼
和Queue中的方法一樣，方法名多了First或者Last，First結尾的方法即從頭部進行操作，Last即從尾部進行操作。
3.1.3 Queue，Deque的實作類
Java中關于Queue的實作主要用的是雙端隊列，畢竟操作更加友善自由，Queue的實作有PriorityQueue，Deque在java.util中主要有ArrayDeque和LinkedList兩個實作類，兩者一個是基于數組的實作，一個是基于連結清單的實作。在之前LinkedList文章中也提到過其是一個雙向連結清單，在此基礎之上實作了Deque接口。
3.2 PriorityQueue
PriorityQueue是Java中唯一一個Queue接口的直接實作，如其名字所示，優先隊列，其内部支援按照一定的規則對内部元素進行排序。
3.2.1 PriorityQueue繼承關系
先看下PriorityQueue的繼承實作關系，可知其是Queue的實作類，主要使用方式是隊列的基本操作，而之前講到過Queue的基本原理，其核心是FIFO（First In First Out）原理。 Java中的PriorityQueue的實作也是符合隊列的方式，不過又略有不同，卻别就在于PriorityQueue的priority上，其是一個支援優先級的隊列，當使用了其priority的特性的時候，則并非FIFO。
3.2.2 PriorityQueue的使用
案列1：
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(20);queue.add(14);queue.add(21);queue.add(8);queue.add(9);
queue.add(11);queue.add(13);queue.add(10);queue.add(12);queue.add(15);
while (queue.size()>0){
Integer poll = queue.poll();
System.err.print(poll+"->");
}
複制代碼
上述代碼做的事為往隊列中放入10個int值，然後使用Queue的poll()方法依次取出，最後結果為每次取出來都是隊列中最小的值，說明 了PriorityQueue内部确實是有一定順序規則的。
案例2：
<pre style="margin: 0px; padding: 0px; max-width: 100%; background-image: none; background-position: // 必須實作Comparable方法，想String,數值本身即可比較
private static class Test implements Comparable<Test>{
private int a;
public Test(int a) {
this.a = a;
}
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
@Override
public String toString() {
return "Test{" +
"a=" + a +
'}';
}
@Override
public int compareTo(Test o) {
return 0;
}
}
public static void main(String[] args) {
PriorityQueue<Test> queue = new PriorityQueue<>();
queue.add(new Test(20));queue.add(new Test(14));queue.add(new Test(21));queue.add(new Test(8));queue.add(new Test(9));
queue.add(new Test(11));queue.add(new Test(13));queue.add(new Test(10));queue.add(new Test(12));queue.add(new Test(15));
while (queue.size()>0){
Test poll = queue.poll();
System.err.print(poll+"->");
}
}
複制代碼
上述代碼重寫了compareTo方法都傳回0，即不做優先級排序。發現我們傳回的順序為Test{a=20}->Test{a=15}->Test{a=12}->Test{a=10}->Test{a=13}->Test{a=11}->Test{a=9}->Test{a=8}->Test{a=21}->Test{a=14}，和放入的順序還是不同，是以這兒需要注意在實作Comparable接口的時候一定要按照一定的規則進行優先級排序，關于為什麼取出來的順序和放入的順序不一緻後邊将從源碼來分析。
3.2.3 PriorityQueue組成
/**
* 預設容量大小，數組大小
*/
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 存放元素的數組
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 隊列中存放了多少元素
*/
private int size = 0;
/**
* 自定義的比較規則，有該規則時優先使用，否則使用元素實作的Comparable接口方法。
*/
private final Comparator<? super E> comparator;
/**
* 隊列修改次數，每次存取都算一次修改
*/
transient int modCount = 0; // non-private to simplify nested class access
複制代碼
可以看到PriorityQueue的組成很簡單，主要記住一個存放元素的數組，和一個Comparator比較器即可。
3.2.4 PriorityQueue操作方法
offer方法
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;
//i=size，當queue為空的時候
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
複制代碼
首先可以看到當Queue中為空的時候，第一次放入的元素直接放在了數組的第一位，那麼上邊案例二中第一個放入的20就在數組的第一位。而當queue中不為空時，又使用siftUp(i, e)方法，傳入的參數是隊列中已有元素數量和即将要放入的新元素，現在就來看下究竟siftUp(i, e)做了什麼事。
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
複制代碼
還記得上邊提到PriorityQueue的組成，是一個存放元素的數組，和一個Comparator比較器。這兒是指當沒有Comparator是使用元素類實作compareTo方法進行比較。其含義為優先使用自定義的比較規則Comparator，否則使用元素所在類實作的Comparable接口方法。
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
//為什麼-1， 思考數組位置0，1，2。0是1和2的父節點
int parent = (k - 1) >>> 1;
//父節點
Object e = queue[parent];
//當傳入的新節點大于父節點則不做處理，否則二者交換
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
複制代碼
可以看到，當PriorityQueue不為空時插入一個新元素，會對其新元素進行堆排序處理（對于堆排序此處不做描述），這樣每次進來都會對該元素進行堆排序運算，這樣也就保證了Queue中第一個元素永遠是最小的（預設規則排序）。
pool方法
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
//s = --size,即原來數組的最後一個元素
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
複制代碼
此處可知，當取出一個值進行了siftDown操作，傳入的參數為索引0和隊列中的最後一個元素。
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)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 &&
//c和right是parent的兩個子節點，找出小的那個成為新的c。
((Comparable<? super E>) 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;
}
複制代碼
當沒有Comparator比較器是采用的siftDown方法如上，因為索引0位置取出了，找索引0的子節點比它小的作為新的父節點并在循環内遞歸。PriorityQueue是不是很簡單呢，其他細節就不再詳解，待諸君深入。
3.3 ArrayDeque
ArrayDeque是Java中基于數組實作的雙端隊列，在Java中Deque的實作有LinkedList和ArrayDeque，正如它兩的名字就标志了它們的不同，LinkedList是基于雙向連結清單實作的，而ArrayDeque是基于數組實作的。
3.3.1 ArrayDeque的繼承關系
可見ArrayDeque是Deque接口的實作，和LinkedList不同的是，LinkedList既是List接口也是Deque接口的實作。
3.3.2 ArrayDeque使用
案列
ArrayDeque<String> deque = new ArrayDeque<>();
deque.offer("aaa");
deque.offer("bbb");
deque.offer("ccc");
deque.offer("ddd");
//peek方法隻擷取不移除
System.err.println(deque.peekFirst());
System.err.println(deque.peekLast());
複制代碼
案例二：
ArrayDeque<String> deque = new ArrayDeque<>();
deque.offerFirst("aaa");
deque.offerLast("bbb");
deque.offerFirst("ccc");
deque.offerLast("ddd");
String a;
while((a = deque.pollLast())!=null){
System.err.print(a+"->");
}
複制代碼
上述程式最後得到隊列中排列結果為ccc,aaa,bbb,ddd是以循環使用pollLast(),結果ddd,bbb,aaa,ccc，圖示案列二的插入邏輯如下：
3.3.4 ArrayDeque内部組成
//具體存放元素的數組，數組大小一定是2的幂次方
transient Object[] elements; // non-private to
//隊列頭索引
transient int head;
//隊列尾索引
transient int tail;
//預設的最小初始化容量，即傳入的容量小于8容量為8，而預設容量是16
private static final int MIN_INITIAL_CAPACITY = 8;
複制代碼
3.3.5 數組elements長度
此處elements數組的長度永遠是2的幂次方，此處的實作方法和hashMap中基本一樣，即保證長度的二進制全部由1組成，然後再加1，則變成了100…，故一定是2的幂次方。
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
複制代碼
3.3.6 ArrayDeque實作機制
如下圖所示：
此處應将數組視作首尾相連的，最初頭部和尾部索引都是0，addLast方向往右，addFirst方向往左，是以數組中間可能是空的，當頭指針和尾指針相遇的時候對數組進行擴容，并對元素位置進行調整。 源碼：
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
複制代碼
注意下邊這行代碼，表示當head-1大于等于0時，head=head-1，否則head=elements.length - 1。
head = (head - 1) & (elements.length - 1)
複制代碼
換一種寫法就是下邊這樣，是不是就是上邊addFirst的指針移動方向？
head = head-1>=0?head-1:elements.length-1
複制代碼
這個就是位運算的神奇操作了，因為任何數與大于它的一個全是二進制1做&運算時等于它自身，如1010&1111 = 1010，此處不贅述。 再看addLast方法：
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
複制代碼
同樣的注意有一串神奇代碼。
(tail = (tail + 1) & (elements.length - 1))
複制代碼
該表達式等于
tail = tail+1>element-1?0:tail+1
,是不是很神奇的寫法，其原理是一個二進制數全部由1組成和一個大于它的數做&運算結果為0，如
10000&1111 = 0
。poll方法和add方法邏輯是相反的，此處就不再贅述，諸君共求之！
4. Set
如果說List對集合加了有序性的化，那麼Set就是對集合加上了唯一性。
4.1 Set接口
java中的Set接口和Colletion是完全一樣的定義。
package java.util;
public interface Set<E> extends Collection<E> {
// Query Operations
int size();
boolean isEmpty();
Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
//此處和Collection接口由差別
Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT);
}
}
複制代碼
4.2 HashSet
Java中的HashSet如其名字所示，其是一種Hash實作的集合，使用的底層結構是HashMap。
4.2.1 HashSet繼承關系
4.2.2 HashSet源碼
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
}
複制代碼
可以看到HashSet内部其實是一個HashMap。
4.2.3 HashSet是如何保證不重複的呢？
可見HashSet的add方法，插入的值會作為HashMap的key，是以是HashMap保證了不重複。map的put方法新增一個原來不存在的值會傳回null，如果原來存在的話會傳回原來存在的值。關于HashMap是如何實作的，見後續！
4.3 LinkedHashSet
LinkedHashSet用的也比較少，其也是基于Set的實作。
4.3.1 LinkedHashSet繼承關系
和HashSet一樣，其也是Set接口的實作類，并且是HashSet的子類。
4.3.2 LinkedHashSet源碼
package java.util;
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2851667679971038690L;
public LinkedHashSet(int initialCapacity, float loadFactor) {
//調用HashSet的構造方法
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT |
Spliterator.ORDERED);
}
}
複制代碼
其操作方法和HashSet完全一樣，那麼二者差別是什麼呢？1.首先LinkedHashSet是HashSet的子類.2.LinkedHashSet中用于存儲值的實作LinkedHashMap，而HashSet使用的是HashMap。LinkedHashSet中調用的父類構造器，可以看到其實列是一個LinkedHashMap。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
複制代碼
LinkedHashSet的實作很簡單，更深入的了解需要去看LinkedHashMap的實作，對LinkedHashMap的解析将單獨提出。
5、Map
Map是一種鍵值對的結構，就是常說的Key-Value結構，一個Map就是很多這樣K-V鍵值對組成的，一個K-V結構我們将其稱作Entry，在Java裡，Map是用的非常多的一種資料結構。上圖展示了Map家族最基礎的一個結構（隻是指java.util中）。
完整版Java面試題位址：JAVA後端面試題整合
5.1 Map接口
package java.util;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.Serializable;
public interface Map<K,V> {
// Query Operations
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
// Modification Operations
V put(K key, V value);
V remove(Object key);
// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// Comparison and hashing
boolean equals(Object o);
int hashCode();
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}
複制代碼
Map接口本身就是一個頂層接口，由一堆Map自身接口方法和一個Entry接口組成，Entry接口定義了主要是關于Key-Value自身的一些操作，Map接口定義的是一些屬性和關于屬性查找修改的一些接口方法。
5.2 HashMap
HashMap是Java中最常用K-V容器，采用了哈希的方式進行實作，HashMap中存儲的是一個又一個Key-Value的鍵值對，我們将其稱作Entry，HashMap對Entry進行了擴充（稱作Node），使其成為連結清單或者樹的結構使其存儲在HashMap的容器裡（是一個數組）。
5.2.1 HashMap繼承關系
5.2.2 HashMap存儲的資料
Map接口中有一個Entry接口，在HashMap中對其進行了實作，Entry的實作是HashMap存放的資料的類型。其中Entry在HashMap的實作是Node，Node是一個單連結清單的結構，TreeNode是其子類，是一個紅黑樹的類型，其繼承結構圖如下：
HashMap存放資料的資料是什麼呢？代碼中存放資料的容器如下：
transient Node<K,V>[] table;
複制代碼
說明了該容器中是一個又一個node組成，而node有三種實作，是以hashMap中存放的node的形式既可以是Node也可以是TreeNode。
5.2.3 HashMap的組成
有了上邊的概念之後來看一下HashMap裡有哪些組成吧！
//是hashMap的最小容量16，容量就是數組的大小也就是變量，transient Node<K,V>[] table。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大數量，該數組最大值為2^31一次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設的加載因子，如果構造的時候不傳則為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一個位置裡存放的節點轉化成樹的門檻值，也就是8，比如數組裡有一個node，這個
// node連結清單的長度達到該值才會轉化為紅黑樹。
static final int TREEIFY_THRESHOLD = 8;
//當一個反樹化的門檻值，當這個node長度減少到該值就會從樹轉化成連結清單
static final int UNTREEIFY_THRESHOLD = 6;
//滿足節點變成樹的另一個條件，就是存放node的數組長度要達到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具體存放資料的數組
transient Node<K,V>[] table;
//entrySet，一個存放k-v緩沖區
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少個鍵值對
transient int size;
//對map的修改次數
transient int modCount;
//加載因子
final float loadFactor;
複制代碼
這兒要說兩個概念，table是指的存放資料的數組，bin是指的table中某一個位置的node，一個node可以了解成一批/一盒資料。
5.2.4 HashMap中的構造函數*
//隻有容量，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);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 容量不能為負數
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//當容量大于2^31就取最大值1<<31;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//目前數組table的大小，一定是是2的幂次方
// tableSizeFor保證了數組一定是是2的幂次方，是大于initialCapacity最結進的值。
this.threshold = tableSizeFor(initialCapacity);
}
複制代碼
tableSizeFor()方法保證了數組大小一定是是2的幂次方,是如何實作的呢？
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
複制代碼
該方法将一個二進制數第一位1後邊的數字全部變成1，然後再加1，這樣這個二進制數就一定是100…這樣的形式。此處實作在ArrayDeque的實作中也用到了類似的方法來保證數組長度一定是2的幂次方。
5.2.5 put方法
開發人員使用的put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
複制代碼
真正HashMap内部使用的put值的方法：
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;
//當hash到的位置，該位置為null的時候，存放一個新node放入
// 這兒p指派成了table該位置的node值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//該位置第一個就是查找到的值，将p賦給e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是紅黑樹，調用紅黑樹的putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//是連結清單，周遊，注意e = p.next這個一直将下一節點指派給e，直到尾部，注意開頭是++binCount
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//當連結清單長度大于等于7，插入第8位，樹化
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;
}
複制代碼
5.2.6 查找方法
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 &&
//這一行是找到要查詢的Key在table中的位置，table是存放HashMap中每一個Node的數組。
(first = tab[(n - 1) & hash]) != null) {
//Node可能是一個連結清單或者樹，先判斷根節點是否是要查詢的key,就是根節點，友善後續周遊Node寫法并且
//對于隻有根節點的Node直接判斷
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;
}
//周遊連結清單，當連結清單後續為null則推出循環
while ((e = e.next) != null);
}
}
return null;
}
複制代碼
5.3 HashTable
和HashMap不同，HashTable的實作方式完全不同，這點從二者的類繼承關系就可以看出端倪來，HashTable和HashMap雖然都實作了Map接口，但是HashTable繼承了DIctionary抽象類，而HashMap繼承了AbstractMap抽象類。
5.3.1 HashTable的類繼承關系圖
HashTable
HashMap
5.3.2 Dictionary接口
public abstract
class Dictionary<K,V> {
public Dictionary() {
}
public abstract int size();
public abstract boolean isEmpty();
public abstract Enumeration<K> keys();
public abstract Enumeration<V> elements();
public abstract V get(Object key);
public abstract V put(K key, V value);
public abstract V remove(Object key);
}
複制代碼
Dictionary類中有這樣一行注釋，當key為null時會抛出空指針NullPointerException,這也說明了HashTabel是不允許Key為null的。
//throws NullPointerException if the {@code key} is {@code null}.</pre>
複制代碼
5.3.3 HashTable組成
/**
* The hash table data.
* 真正存放資料的數組
*/
private transient Entry<?,?>[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
* 重新hash的門檻值
* @serial
*/
private int threshold;
/**
* The load factor for the hashtable.
* @serial
*/
private float loadFactor;
複制代碼
HashTable中的元素存在Entry[] table中，是一個Entry數組，Entry是存放的節點，每一個Entry是一個連結清單。
5.3.4 HashTable中的Entry
final int hash;
final K key;
V value;
Entry<K,V> next;
複制代碼
知道Entry是一個單連結清單即可，和HashMap中的Node結構相同，但是HashMap中還有Node的子類TreeNode。
5.3.5 put方法
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//在數組中的位置 0x7fffffff 是31位二進制1
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
//如果周遊連結清單找到了則替換舊值并傳回
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
複制代碼
本質上就是先hash求索引，周遊該索引Entry連結清單，如果找到hash值和key都和put的key一樣的時候就替換舊值，否則使用addEntry方法添加新值進入table，因為添加新元素就涉及到修改元素大小，還可能需要擴容等，具體看下邊的addEntry方法可知。
private void addEntry(int hash, K key, V value, int index) {
Entry<?,?> tab[] = table;
//如果擴容需要重新計算hash，是以index和table都會被修改
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
//插入新元素
tab[index] = new Entry<>(hash, key, value, e);
count++;
modCount++;
}
複制代碼
tab[index] = new Entry<>(hash, key, value, e);
複制代碼
這行代碼是真正插入新元素的方法，采用頭插法，單連結清單一般都用頭插法（快）。
5.3.6 get方法
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
複制代碼
get方法就簡單很多就是hash，找到索引，周遊連結清單找到對應的value，沒有則傳回null。相比諸君都已經看到，HashTable中方法是用synchronized修飾的，是以其操作是線程安全的，但是效率會受影響。
最後
最近針對網際網路公司面試問到的知識點，總結出了Java程式員面試涉及到的絕大部分面試題及答案分享給大家，希望能幫助到你面試前的複習且找到一個好的工作，也節省你在網上搜尋資料的時間來學習。
内容涵蓋：Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Memcached、Redis、MySQL、Spring、SpringBoot、SpringCloud、RabbitMQ、Kafka、Linux等技術棧。
完整版Java面試題位址：JAVA後端面試題整合