本文發(fā)表于KuTear's Blog,轉(zhuǎn)載請(qǐng)注明
基本功能
Arrays & Collections
常用的方法
//Arrays.java
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
注意這里返回的ArrayList不同于我們平時(shí)使用的ArrayList,根據(jù)該ArrayLsit的源碼
private static class ArrayList<E> extends AbstractList<E>
知道其繼承至AbstractList,但是沒(méi)有實(shí)現(xiàn)它的add()和delete()方法，因此若調(diào)用會(huì)拋出UnsupportedOperationException的提示，這是由于該List的底層就是一個(gè)數(shù)組，而且不會(huì)擴(kuò)容,所以不支持添加等操作，在使用的時(shí)候要特別注意。
List list = ...;
List lists1 = new ArrayList(list);
List lists2 = Collections.addAll(list);
上面代碼，相比lists1,lists2更為高效。
集合類基本介紹
- List 以特定順序保存的一組元素
- Set 以特定順序保存的不重復(fù)的一組元素
- Queue 同數(shù)據(jù)結(jié)構(gòu)隊(duì)列
- Map 使用KV保存兩組值
具體介紹
List
相比Collection,多 了一些方法,如listIterator()等.
ArrayList
概述
根據(jù)類圖可以知道ArrayList的繼承結(jié)構(gòu),RandomAccess是一個(gè)說(shuō)明性接口,沒(méi)有任何的方法實(shí)現(xiàn).ArrayList的底層實(shí)現(xiàn)任然是數(shù)組,當(dāng)容量達(dá)到一定時(shí),會(huì)新建一個(gè)數(shù)組,再把原來(lái)的數(shù)據(jù)拷貝過(guò)去,所以性能并不是太好.下面詳細(xì)的看看.
準(zhǔn)備
由于ArrayList的底層是由數(shù)組實(shí)現(xiàn)的,并且ArrayList是動(dòng)態(tài)大小,因此修改擴(kuò)容,這里用到Arrays.copyOf(...)方法
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength)); //native
return copy;
}
源碼閱讀
transient Object[] elementData; // 為什么是Object而不是泛型E?
private int size; //實(shí)際大小 size()函數(shù)就是返回該值
它的三個(gè)構(gòu)造函數(shù)的作用都是初始化上面兩個(gè)參數(shù)的值.都是非常的簡(jiǎn)單,不多說(shuō),下面看看最常用的add()函數(shù).
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 判斷數(shù)組容量是否夠,不夠就擴(kuò)容
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index); //index > size || index < 0拋異常
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);//index后的往后移一位
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> 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;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
本身這段代碼是非常容易理解的,下面看看它擴(kuò)容的實(shí)現(xiàn).
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { //還沒(méi)有數(shù)據(jù)時(shí)
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//注意elementData.length只是表示現(xiàn)有的容量,不是size
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//增加1.5倍容量,位操作效率遠(yuǎn)遠(yuǎn)高于做除法
if (newCapacity - minCapacity < 0) //容量還沒(méi)有達(dá)到申請(qǐng)的量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //Integer.MAX_VALUE - 8
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//把原來(lái)的數(shù)據(jù)移動(dòng)到新數(shù)組中
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // int 溢出變?yōu)樨?fù)數(shù)了
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
通過(guò)上面的代碼,可以看到ArrayList的最大容量為Integer.MAX_VALUE,接下來(lái)就看看同等常用的get()函數(shù).
public E get(int index) {
rangeCheck(index); //檢查index是否在[0,size)范圍內(nèi),具體實(shí)現(xiàn)就這一個(gè)條件判斷
return elementData(index); //取得元素elementData[index]
}
根據(jù)他的名稱我們很容易的了解他的功能,并且對(duì)于數(shù)組的隨機(jī)存取,這個(gè)實(shí)現(xiàn)太簡(jiǎn)單了,就不必多說(shuō).下面看看set()方法.
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
臥槽,我都不想多說(shuō)什么了,就是簡(jiǎn)單的判斷index的范圍,然后就是對(duì)數(shù)組操作.函數(shù)indexOf()/contains()和lastIndexOf()都是簡(jiǎn)單的對(duì)數(shù)組的遍歷過(guò)程,也跳過(guò).下面看看remove()相關(guān)的方法.
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;
}
/**
* 先遍歷查找到index,在移除
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
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
}
下面看看retainAll()和removeAll()的實(shí)現(xiàn)函數(shù)batchRemove().
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r]; //保留相等/或者不等的部分
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
下面看看排序函數(shù)sort()
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
由上面的代碼可以看出sort()在排序過(guò)程重中是不允許執(zhí)行修改/添加等等操作的.subList()返回一個(gè)List,但是這個(gè)List是依附在原本的ArrayList的,也就是說(shuō)subList()得到的List其實(shí)是ArrayList的鏡像,當(dāng)ArrayList修改后,取得的subList也會(huì)顯示出修改后的狀態(tài).這里可以看看它的一部分實(shí)現(xiàn)
//構(gòu)造函數(shù)
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
//從這里可以看出,它的數(shù)據(jù)是外部類ArrayList的.
return ArrayList.this.elementData(offset + index);
}
最后看看函數(shù)listIterator()和函數(shù)iterator(),他們分別返回一個(gè)雙向迭代器和單向迭代器.本質(zhì)他們的遍歷過(guò)程還是數(shù)組的遍歷,想要了解詳情可以去看看具體的源碼,這里就不介紹了.
LinkedList
概述
inkedList實(shí)現(xiàn)了List、Deque、Cloneable以及Serializable接口。其中Deque是雙端隊(duì)列接口，所以LinkedList可以當(dāng)作是棧、隊(duì)列或者雙端隊(duì)隊(duì)列。在使用它的時(shí)候,通?？梢园阉蛏限D(zhuǎn)型為List,Queue已達(dá)到縮小她的接口的功能(限制了不需要的方法).
源碼閱讀
由于是由鏈表實(shí)現(xiàn),首先需要查看的就是結(jié)點(diǎn)了.
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的內(nèi)部,保存著first和last結(jié)點(diǎn)的引用,這樣就方便了兩端的插入刪除等操作.
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
下面看看它的關(guān)鍵實(shí)現(xiàn)函數(shù),添加結(jié)點(diǎn)相關(guān)函數(shù).
//尾部添加
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); //注意構(gòu)造函數(shù)已經(jīng)綁定的前結(jié)點(diǎn)
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//頭部添加
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++;
}
//在某個(gè)結(jié)點(diǎn)前添加
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
刪除結(jié)點(diǎn)相關(guān)函數(shù).
E unlink(Node<E> x) {
// assert x != null;
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;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
以上兩組函數(shù)實(shí)現(xiàn)都是非常的簡(jiǎn)單,和數(shù)據(jù)結(jié)構(gòu)書中講的都幾乎一樣,想必大家也可以看懂,就不多廢話了,而該類的其他方法多依賴于以上方法的實(shí)現(xiàn).還有一個(gè)其他函數(shù)的依賴函數(shù)是node()
//獲取第index個(gè)結(jié)點(diǎn)
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
可以看出他是遍歷鏈表的操作,只是因?yàn)橛?code>first和last的存在,可以稍微優(yōu)化一下.
Stack
根據(jù)上面LinkedList的實(shí)現(xiàn),其實(shí)使用LinkedList實(shí)現(xiàn)一個(gè)Stack是非常的容易的,可以看看實(shí)現(xiàn)方式.
public class Stack<T> {
private LinkedList<T> storage = new LinkedList<T>();
/** 入棧 */
public void push(T v) {
storage.addFirst(v);
}
/** 出棧，但不刪除 */
public T peek() {
return storage.getFirst();
}
/** 出棧 */
public T pop() {
return storage.removeFirst();
}
/** 棧是否為空 */
public boolean empty() {
return storage.isEmpty();
}
/** 打印棧元素 */
public String toString() {
return storage.toString();
}
}
但是Java中任然提供了Stack類,而且實(shí)現(xiàn)方式與上面的完全不同,它的內(nèi)部存儲(chǔ)結(jié)構(gòu)是數(shù)組,基本的實(shí)現(xiàn)其實(shí)還是和ArrayList差不多,而且在<<Think In Java>>中并不建議使用它,因此這里不講了.
Map
HashMap
本文的代碼均來(lái)至于JDK1.8,HashMap與前面版本的變化比較大,Android SDK V23中的是舊版本的
源碼閱讀
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
// HashMap的閾值，用于判斷是否需要調(diào)整HashMap的容量（threshold = 容量*加載因子）
int threshold;
final float loadFactor; //加載因子,注意Android SDK寫死的0.75
在這里可以看看構(gòu)造函數(shù)的參數(shù)
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;
//tableSizeFor(n) Returns the smallest power of two >= its argument
this.threshold = tableSizeFor(initialCapacity);
}
可以看出threshold在沒(méi)到達(dá)最大值之前是$2^n$.下面再看看常用的方法.
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;
//還沒(méi)有初始化數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//找到要添加的位置
if ((p = tab[i = (n - 1) & hash]) == null)
//如果還沒(méi)有元素,就放入
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))))
//已經(jīng)存在了一個(gè)相同KEY的元素
e = p;
//紅黑樹(shù),JDK1.8的優(yōu)化點(diǎn),當(dāng)鏈表的長(zhǎng)度大于8時(shí),不再使用鏈表,轉(zhuǎn)為紅黑樹(shù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//鏈表結(jié)構(gòu)
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); //鏈表長(zhǎng)度為8了,轉(zhuǎn)紅黑樹(shù)
break;
}
//在鏈表中找到了同KEY值得元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key ,已經(jīng)存在的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;
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//到此得到一個(gè)雙向鏈表的格式.
if ((tab[index] = hd) != null)
hd.treeify(tab); //形成從該節(jié)點(diǎn)連接的節(jié)點(diǎn)的樹(shù)。實(shí)現(xiàn)有點(diǎn)復(fù)雜
}
}
關(guān)于紅黑樹(shù)的操作本身是非常復(fù)雜的,可以參考Wiki,接下來(lái)看看get()操作.
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) {
//Fiest為鏈表的首節(jié)點(diǎn)或紅黑樹(shù)的根節(jié)點(diǎn)
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)
//在紅黑樹(shù)中查找
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;
}
之理也只是大體說(shuō)明一下HashMap的結(jié)構(gòu),核心的東西就是紅黑樹(shù),它的其他方法也是大體一致,都是對(duì)鏈表和紅黑樹(shù)的操作.entrySet()和keySet()也是和List中的iterator一樣,內(nèi)部的操作都是由HashMap本身來(lái)完成.
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
這個(gè)函數(shù)大家可能也會(huì)有一點(diǎn)困惑,為什么這里就只討論了鏈表的情況,并根據(jù)next()遍歷整個(gè)鏈表?其實(shí)TreeNode是繼承至Node,并且在生成紅黑樹(shù)的時(shí)候并沒(méi)有修改next的指向,所以通過(guò)next()遍歷就沒(méi)問(wèn)題了.
TreeMap
TreeMap的底層實(shí)現(xiàn)也是基于紅黑樹(shù)的.
源碼閱讀
還是老規(guī)矩,先看最常用的方法put().
public V put(K key, V value) {
Entry<K,V> t = root;
//紅黑樹(shù)為空,直接添加一個(gè)結(jié)點(diǎn)接OK
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//優(yōu)先使用主動(dòng)提供的比較器,
//在使用該類(KEY)自帶的比較器(繼承Comparable)
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//找到key值相同的結(jié)點(diǎn),覆蓋該值即可
return t.setValue(value);
} while (t != null);
}
else {
//key不允許為NULL
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//到此找到了要插入到結(jié)點(diǎn)parent的子結(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//插入完成,此時(shí)的紅黑樹(shù)結(jié)構(gòu)可能已經(jīng)被破壞,需要重新構(gòu)建
//過(guò)程和HasmMap的其實(shí)是一樣的.了解更多可以看文章后面的參考
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
接下來(lái)看看get()函數(shù).
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
//自定義比較器的時(shí)候
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
//實(shí)現(xiàn)就是查找二叉樹(shù)查找問(wèn)題
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
//這個(gè)函數(shù)的實(shí)現(xiàn)
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
遍歷的時(shí)候調(diào)用了一個(gè)函數(shù)
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e); //中序遍歷的E的后一節(jié)點(diǎn)
lastReturned = e;
return e;
}
這樣輸入的數(shù)據(jù)就是按照紅黑樹(shù)中序遍歷的數(shù)據(jù),也就是有序數(shù)據(jù).
LinkedHashMap
根據(jù)最上面的繼承關(guān)系圖我們知道LinkedHashMap繼承至HashMap,所以重復(fù)型的東西我就不說(shuō)了,LinkedHashMap的核心功能就是維持了原有的輸入順序或者指定為訪問(wèn)順序(LRU).下面也是主要看看這個(gè)功能的實(shí)現(xiàn).
源碼閱讀
LinkedHashMap中的字段
// 頭部放舊結(jié)點(diǎn)(最久沒(méi)使用或最久放入)
transient LinkedHashMap.Entry<K,V> head;
// 尾部放新節(jié)點(diǎn)
transient LinkedHashMap.Entry<K,V> tail;
通過(guò)上面的分析,我們知道HashMap的put()時(shí)調(diào)用了函數(shù)newNode(),而LinkedHashMap就重寫了這個(gè)方法.
//結(jié)點(diǎn),相比HashMap多了before和after
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//創(chuàng)建一個(gè)結(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
//內(nèi)部保存了一個(gè)鏈表
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
這樣就要求在以后的插入刪除的工作中需要額外的維護(hù)這個(gè)鏈表.另外,如果開(kāi)啟了按訪問(wèn)順序排序的話,在每次get()或者put()了重復(fù)數(shù)據(jù)是都會(huì)要求把訪問(wèn)的結(jié)點(diǎn)放到鏈表尾部.
//把E移動(dòng)到雙向鏈表的尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null) //P本身為首節(jié)點(diǎn)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else //P本身為尾接點(diǎn)
last = b;
//到此P被移除了
if (last == null) //原本鏈表只有一個(gè)元素,移除光了
head = p;
else {
//P放在最后
p.before = last;
last.after = p;
}
//修改指向末尾結(jié)點(diǎn)的指針
tail = p;
++modCount;
}
}
接下來(lái)就看看LinkedHashMap的遍歷.entrySet()返回的是一個(gè)LinkedEntrySet的實(shí)例,而LinkedEntrySet的迭代器是LinkedEntryIterator,LinkedEntryIterator的next()方法調(diào)用nextNode()函數(shù).
//構(gòu)造函數(shù)
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
可以很明顯的看到,它的實(shí)現(xiàn)完全依賴于構(gòu)建的鏈表,不像HashMap對(duì)組數(shù)和鏈表(紅黑樹(shù))的遍歷.相比HashMap其實(shí)就是多了一個(gè)雙向鏈表而已.
Set
Set是一個(gè)不包含重復(fù)元素的Collection。更確切地講，Set 不包含滿足 e1.equals(e2) 的元素對(duì) e1 和 e2，并且最多包含一個(gè) null 元素.
HashSet
HashSet的底部是使用一個(gè)HashMap,把值存在HashMap的KEY,HashMap的VALUE字段為固定的值,根據(jù)HashMap的KEY的唯一性,可以保證HashSet的值得唯一性.額外,有一個(gè)構(gòu)造器使用的是LinkedHashMap,只有包權(quán)限,是后面要講的LinkedHashSet的實(shí)現(xiàn).
//dummy 參數(shù)只是使用來(lái)區(qū)別構(gòu)造函數(shù)
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
源碼閱讀
其實(shí)HashSet的源碼并沒(méi)有什么東西,都是調(diào)用HashMap的基本操作.下面隨便看兩個(gè)函數(shù).
private transient HashMap<E,Object> map;
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
由于這些方法前面都已經(jīng)說(shuō)過(guò)了,這里就不說(shuō)了.
TreeSet
有了上面HashSet的介紹,可能你已經(jīng)猜到TreeSet的實(shí)現(xiàn)方式是基于TreeMap了.將值存放在TreeMap的KEY中,保證了不會(huì)重復(fù)并且有序,最后只需要遍歷TreeSet的KEY就行了.具體的操作可以看看TreeMap.
LinkedHashSet
它的實(shí)現(xiàn)是最簡(jiǎn)單的,繼承至HashSet,調(diào)用前面說(shuō)的特殊構(gòu)造器,相當(dāng)于把HashSet的HashMap換成了LinkedHashMap,并且按照插入順序排序.
Queue
LinkedList
這個(gè)上面已經(jīng)分析過(guò)了，這里跳過(guò)。
PriorityQueue
準(zhǔn)備
在數(shù)據(jù)結(jié)構(gòu)的課程中，我們都學(xué)過(guò)用數(shù)組表示完全二叉樹(shù)，這里有一些固定的公式
Index(parent) = (Index(Child)-1) >> 1 //索引0開(kāi)始
而優(yōu)先級(jí)隊(duì)列Priority就是使用了數(shù)組表示最小堆，每次插入刪除都會(huì)重新排列內(nèi)部數(shù)據(jù)。
最小堆，是一種經(jīng)過(guò)排序的完全二叉樹(shù)
源碼閱讀
有用的字段
priavte transient Object[] queue; //內(nèi)部表示最小堆的數(shù)組
private int size = 0; //實(shí)際大小
常用方法add()的實(shí)現(xiàn)
public boolean add(E e) {
return offer(e); // add方法內(nèi)部調(diào)用offer方法
}
public boolean offer(E e) {
if (e == null) // 元素為空的話，拋出NullPointerException異常
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) // 如果當(dāng)前用堆表示的數(shù)組已經(jīng)滿了，調(diào)用grow方法擴(kuò)容
grow(i + 1); // 擴(kuò)容
size = i + 1; // 元素個(gè)數(shù)+1
if (i == 0) // 堆還沒(méi)有元素的情況
queue[0] = e; // 直接給堆頂賦值元素
else // 堆中已有元素的情況
siftUp(i, e); // 重新調(diào)整堆，從下往上調(diào)整，因?yàn)樾略鲈厥羌拥阶詈笠粋€(gè)葉子節(jié)點(diǎn)
return true;
}
private void siftUp(int k, E x) {
if (comparator != null) // 比較器存在的情況下
siftUpUsingComparator(k, x); // 使用比較器調(diào)整
else // 比較器不存在的情況下
siftUpComparable(k, x); // 使用元素自身的比較器調(diào)整
}
private void siftUpUsingComparator(int k, E x) {
while (k > 0) { // 一直循環(huán)直到父節(jié)點(diǎn)還存在
int parent = (k - 1) >>> 1; // 找到父節(jié)點(diǎn)索引,依賴完全二叉樹(shù)性質(zhì)
Object e = queue[parent]; // 賦值父節(jié)點(diǎn)元素
if (comparator.compare(x, (E) e) >= 0) // 新元素與父元素進(jìn)行比較，如果滿足比較器結(jié)果，直接跳出，否則進(jìn)行調(diào)整
break;
queue[k] = e; // 進(jìn)行調(diào)整，新位置的元素變成了父元素
k = parent; // 新位置索引變成父元素索引，進(jìn)行遞歸操作
}
queue[k] = x; // 新添加的元素添加到堆中
}
private void siftUpComparable(int k, E x) {
...//同上面類似
}
下面看看函數(shù)remove()的實(shí)現(xiàn)
public boolean remove(Object o) {
int i = indexOf(o); //按數(shù)組索引遍歷
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element,移除最后的元素，該數(shù)組依舊是最小堆
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null; //數(shù)組最后一個(gè)位置置空
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
//為什么是一半？？
//因?yàn)榇笥趆alf的元素必然是沒(méi)有葉子節(jié)點(diǎn)的，這是只需要用末節(jié)點(diǎn)X替換要?jiǎng)h除的節(jié)點(diǎn)index(K),然后重新排序。
//而對(duì)于小于half的節(jié)點(diǎn)，由于存在(左)/(右)節(jié)點(diǎn)，用較小的節(jié)點(diǎn)替換要?jiǎng)h除的節(jié)點(diǎn)，這樣帶刪除節(jié)點(diǎn)的Index = (左)/(右)的索引，然后繼續(xù)遞歸執(zhí)行，直到大于half，在用末節(jié)點(diǎn)替換她。
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<? 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;
}
函數(shù)poll()和remove()的實(shí)現(xiàn)基本一致。
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;
}
其他的比如擴(kuò)容函數(shù)和ArrayList的原理都是一樣的，這里就不說(shuō)了。到此，基本的集合類的源碼大體上都說(shuō)完了。
其他技術(shù)點(diǎn)
Java 8 default關(guān)鍵字
interface A {
void doSomeThing();
}
static class B implements A {
@Override
public void doSomeThing() {
System.out.println("B");
}
}
static class C implements A {
@Override
public void doSomeThing() {
System.out.println("C");
}
}
以上代碼如果想在A中添加一個(gè)函數(shù)，必然需要修改B和C的實(shí)現(xiàn)，但是在Java 8支持為接口添加一個(gè)默認(rèn)的實(shí)現(xiàn)，這樣和抽象類就很相似了。
interface A {
void doSomeThing();
default void doAction() {
System.out.println("Default");
}
}
static class B implements A {
@Override
public void doSomeThing() {
System.out.println("B");
}
}
static class C implements A {
@Override
public void doSomeThing() {
System.out.println("C");
}
}
就向上面就OK了。
Integer比較問(wèn)題
System.out.println(Integer.valueOf(127)==Integer.valueOf(127));
System.out.println(Integer.valueOf(128)==Integer.valueOf(128));
System.out.println(Integer.parseInt("128")==Integer.valueOf("128"));
輸出
true
false
true
為什么會(huì)有這問(wèn)題？通過(guò)源代碼
public static Integer valueOf(int i) {
if (i >= IntegerCache.low && i <= IntegerCache.high)
return IntegerCache.cache[i + (-IntegerCache.low)];
return new Integer(i);
}
代碼中的IntegerCache.low為固定值-128，IntegerCache.high根據(jù)VM系統(tǒng)參數(shù)不同會(huì)有區(qū)別，默認(rèn)127，因此在[-128,127]范圍內(nèi)，實(shí)例化的時(shí)候是返回的同一個(gè)對(duì)象，必然相等。當(dāng)Integer修改的時(shí)候，由于他是不可變對(duì)象（參考String,每次修改都是重新生成對(duì)象），也不會(huì)出現(xiàn)問(wèn)題。對(duì)于第三個(gè)例子，parseInt（）的返回是int,這時(shí)和Integer比較，Integer會(huì)拆包為int,當(dāng)然也就相等。
另外補(bǔ)充一點(diǎn)，當(dāng)我們調(diào)用
Integer i = 1;
其實(shí)也是執(zhí)行
Integer i = Integer.valueOf(1);
可以從反編譯中看出
//源碼
public static void main(String[] args){
Integer i = 1;
int r = i + 1;
}
//反編譯結(jié)果
public static void main(java.lang.String[]);
Code:
0: iconst_1
1: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
4: astore_1
5: aload_1
6: invokevirtual #3 // Method java/lang/Integer.intValue:()I
9: iconst_1
10: iadd
11: istore_2
12: return
自動(dòng)拆箱調(diào)用intValue（），自動(dòng)裝箱調(diào)用valueOf()。
List&Set&Map在遍歷過(guò)程中刪除添加元素錯(cuò)誤
for(int i:list){
if(i == 2){
list.remove(Integer.valueOf(2));
}
}
以上這段代碼會(huì)拋出java.util.ConcurrentModificationException異常。這是因?yàn)閒oreach本質(zhì)還是調(diào)list.iterator()，這里用ArrayList說(shuō)明。
public Iterator<E> iterator() {
return new Itr();
}
這里返回一個(gè)迭代器，其內(nèi)部參數(shù)包括
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; //修改次數(shù),注意int為值傳遞
}
也就是說(shuō)保存了修改的次數(shù)，在迭代器的next()中有檢測(cè)這個(gè)值是否被篡改（可以修改的地方包括ArrayList的add(...)和remove()）。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
解決方案是使用迭代器的remove(...)
Iterator iterator = list.iterator();
while (iterator.hasNext()){
Integer i = (Integer) iterator.next();
if(i == 2){
iterator.remove();
}
}
instanceof 關(guān)鍵字
Object obj = null;
if(obj instanceof Object){
System.out.println("會(huì)輸出嗎?還是崩潰");
}
上面的例子不會(huì)輸出,也不會(huì)崩潰,instanceof會(huì)檢測(cè)左邊對(duì)象是否為null,若是,返回false.
HashMap的容量為什么為$ 2^n $
在put()函數(shù)中,選取數(shù)組索引的方式為
tab[i = (n - 1) & hash]
重點(diǎn)關(guān)注(n - 1) & hash,這里的n是容量,若n=$2^n$,n-1的二進(jìn)制形式為11...11,做&運(yùn)算后只有hash的后幾位相關(guān),保證足夠散列,而若其他情況,下n-1為01..01,運(yùn)算后只有hash的后幾位中的某幾位相關(guān),縮小了散列范圍,如n-1最末尾為0,這樣&之后始終是一個(gè)偶數(shù),導(dǎo)致分布過(guò)于集中.
