jdk8中常用數據結構及其設計原理是什么

今天小編給大家分享一下jdk8中常用數據結構及其設計原理是什么的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

1. LinkedList

LinkedList經典的雙鏈表結構，適用于亂序插入，刪除。指定序列操作則性能不如ArrayList，這也是其數據結構決定的。

add(E) / addLast(E)

add(index, E)

這邊有個小的優化，他會先判斷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; }

靠隊尾

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，再次循環。

private E dequeue() {   // assert lock.getHoldCount() == 1;   // assert items[takeIndex] != null;   final Object[] items = this.items;   @SuppressWarnings("unchecked")   E x = (E) items[takeIndex];   items[takeIndex] = null;   if (++takeIndex == items.length)   takeIndex = 0;  count--;  if (itrs != null)  itrs.elementDequeued();  notFull.signal();  return x;  }

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".

//定義兩條鏈  //原來的hash值新增的bit為0的鏈，頭部和尾部  Node<K,V> loHead = null, loTail = null;  //原來的hash值新增的bit為1的鏈，頭部和尾部  Node<K,V> hiHead = null, hiTail = null;  Node<K,V> next;  //循環遍歷出鏈條鏈  do {  next = e.next;  if ((e.hash & oldCap) == 0) {  if (loTail == null)  loHead = e;  else  loTail.next = e;  loTail = e;  }  else {  if (hiTail == null)  hiHead = e;  else  hiTail.next = e;  hiTail = e;  }  } while ((e = next) != null);  //擴容前后位置不變的鏈  if (loTail != null) {  loTail.next = null;  newTab[j] = loHead;  }  //擴容后位置加上原數組長度的鏈  if (hiTail != null) { 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 刪除最老的元素

以上就是“jdk8中常用數據結構及其設計原理是什么”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。