作者:大道方圓
來源:http://www.cnblogs.com/xdecode/p/9321848.html
最近在整理數據結構方面的知識,系統化看了下Java中常用數據結構,突發奇想用動畫來繪製數據流轉過程。
主要基於jdk8,可能會有些特性與jdk7之前不相同,例如LinkedList LinkedHashMap中的雙向列表不再是迴環的。HashMap中的單鏈表是尾插,而不是頭插入等等,後文不再贅敘這些差異,本文目錄結構如下:
1. LinkedList
LinkedList經典的雙鏈表結構,適用於亂序插入,刪除。指定序列操作則性能不如ArrayList,這也是其數據結構決定的。
add(E) / addLast(E)
add(index, E)
這邊有個小的優化,他會先判斷index是靠近隊頭還是隊尾,來確定從哪個方向遍歷鏈入。
if (index < (size >> 1)) {
Nodex = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Nodex = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
靠隊尾
get(index)
也是會先判斷index,不過性能依然不好,這也是為什麼不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist,而是使用iterator的方式遍歷。
remove(E)
2. ArrayList
ArrayList底層就是一個數組,因此按序查找快,亂序插入,刪除因為涉及到後面元素移位所以性能慢。
add(index, E)
擴容
一般默認容量是10,擴容後,會length*1.5。
remove(E)
循環遍歷數組,判斷E是否equals當前元素,刪除性能不如LinkedList。
3. Stack
Stack是經典的數據結構,底層也是數組,繼承自Vector,先進後出FILO,默認new Stack()容量為10,超出自動擴容。
push(E)
pop()
4. 後綴表達式
Stack的一個典型應用就是計算表達式如 9 + (3 - 1) * 3 + 10 / 2,計算機將中綴表達式轉為後綴表達式,再對後綴表達式進行計算。
中綴轉後綴
- 數字直接輸出
- 棧為空時,遇到運算符,直接入棧
- 遇到左括號, 將其入棧
- 遇到右括號, 執行出棧操作,並將出棧的元素輸出,直到彈出棧的是左括號,左括號不輸出。
- 遇到運算符(加減乘除):彈出所有優先級大於或者等於該運算符的棧頂元素,然後將該運算符入棧
- 最終將棧中的元素依次出棧,輸出。
計算後綴表達
- 遇到數字時,將數字壓入堆棧
- 遇到運算符時,彈出棧頂的兩個數,用運算符對它們做相應的計算, 並將結果入棧
- 重複上述過程直到表達式最右端
- 運算得出的值即為表達式的結果
5. 隊列
與Stack的區別在於:Stack的刪除與添加都在隊尾進行,而Queue刪除在隊頭,添加在隊尾。
ArrayBlockingQueue
生產消費者中常用的阻塞有界隊列,FIFO。
put(E)
put(E) 隊列滿了
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length)
notFull.await();
enqueue(e);
} finally {
lock.unlock();
}
take()
當元素被取出後,並沒有對數組後面的元素位移,而是更新takeIndex來指向下一個元素。
takeIndex是一個環形的增長,當移動到隊列尾部時,會指向0,再次循環。
1 private E dequeue() {
2 // assert lock.getHoldCount() == 1;
3 // assert items[takeIndex] != null;
4 final Object[] items = this.items;
5 @SuppressWarnings("unchecked")
6 E x = (E) items[takeIndex];
7 items[takeIndex] = null;
8 if (++takeIndex == items.length)
9 takeIndex = 0;
10 count--;
11 if (itrs != null)
12 itrs.elementDequeued();
13 notFull.signal();
14 return x;
15 }
6. HashMap
最常用的哈希表,面試的童鞋必備知識了,內部通過數組 + 單鏈表的方式實現。dk8中引入了紅黑樹對長度 > 8的鏈表進行優化,我們另外篇幅再講。
put(K, V)
put(K, V) 相同hash值
resize 動態擴容
當map中元素超出設定的閾值後,會進行resize (length * 2)操作,擴容過程中對元素一通操作,並放置到新的位置。
具體操作如下:
- 在jdk7中對所有元素直接rehash, 並放到新的位置.
- 在jdk8中判斷元素原hash值新增的bit位是0還是1, 0則索引不變, 1則索引變成"原索引 + oldTable.length".
1 //定義兩條鏈
2 //原來的hash值新增的bit為0的鏈,頭部和尾部
3 NodeloHead = null, loTail = null;
4 //原來的hash值新增的bit為1的鏈,頭部和尾部
5 NodehiHead = null, hiTail = null;
6 Nodenext;
7 //循環遍歷出鏈條鏈
8 do {
9 next = e.next;
10 if ((e.hash & oldCap) == 0) {
11 if (loTail == null)
12 loHead = e;
13 else
14 loTail.next = e;
15 loTail = e;
16 }
17 else {
18 if (hiTail == null)
19 hiHead = e;
20 else
21 hiTail.next = e;
22 hiTail = e;
23 }
24 } while ((e = next) != null);
25 //擴容前後位置不變的鏈
26 if (loTail != null) {
27 loTail.next = null;
28 newTab[j] = loHead;
29 }
30 //擴容後位置加上原數組長度的鏈
31 if (hiTail != null) {
32 hiTail.next = null;
33 newTab[j + oldCap] = hiHead;
34 }
7. LinkedHashMap
繼承自HashMap,底層額外維護了一個雙向鏈表來維持數據有序。可以通過設置accessOrder來實現FIFO(插入有序)或者LRU(訪問有序)緩存。
put(K, V)
get(K)
accessOrder為false的時候,直接返回元素就行了,不需要調整位置。
accessOrder為true的時候,需要將最近訪問的元素,放置到隊尾。
removeEldestEntry 刪除最老的元素
(完)
閱讀更多 Java面經 的文章