Java 基礎數據結構分析

java -version java version "13.0.2" 2020-01-14 Java(TM) SE Runtime Environment (build 13.0.2+8) Java HotSpot(TM) 64-Bit Server VM (build 13.0.2+8, mixed mode, sharing)

Array

數組能夠做到快速隨機訪問元素，這是因為當我們創建一個數組時：

<code>
var
 
array
 = 
new
 Person[
3
];
array
[
0
] = 
new
 Person();/<code>

java 首先把這個數組的引用存入棧中，然後到堆空間開闢一片連續的地址空間，並將數組引用指向堆地址空間。

當我們訪問指定的數組元素時，則只需要根據 array 的引用地址 + 下標地址， 就能快速定位元素了。

需要注意的是，數組需要連續空間的特性，讓數組擴容難以實現，所以各種語言實現的數組，數組的大小都是固定的。

數組有 length 屬性，這個屬性記錄的是數組的大小，而不是元素的個數。

List

java 中 list 常用的有 ArrayList 和 LinkedList。

ArrayList

底層基於數組 Object[] 實現，繼承數組的優勢，可快速隨機訪問元素，對於增刪操作，則最壞需要 O(n) 。

我們知道 array 不能擴容，但是 ArrayList 明顯可以，所以我們去看看，ArrayList ，是怎樣擴容的。

<code>
public
 
class
 
ArrayList
<
E
> 
extends 
 
AbstractList
<
E
>
        
implements
 
List
<
E
>, 
RandomAccess
, 
Cloneable
, 
java
.
io
.
Serializable
 
{
    
private
 
static
 
final
 
int
 DEFAULT_CAPACITY = 
10
;
    
transient
 Object[] elementData;  
    
private
 
int
 size;
    
protected
 
transient
 
int
 modCount = 
0
;
}/<code>

• DEFAULT_CAPACITYP ： 默認的容量大小
• elementData ： 用來記錄元素的數組，當我們初始化時，如果未指定容量，則用默認值初始化該數組，但是注意，此時 size 的值是零
• size ： 記錄列表中的元素個數，與數組的容量大小無關
• modCount ： 該屬性繼承自 AbstractList 。所有會修改 list 大小的操作，該值都會增加。當我們通過 iterator 遍歷時， 如果該值發生了改變(被另一個線程增加/刪除了元素)，就會拋出 ConcurrentModificationException

ArrayList 實現了 List / RandomAccess / Cloneable / Serializable 四個標記接口，標記接口 RandomAccess 在排序時會用到，用來選擇迭代方式(for or iterator) 。

通過源碼能看到， 當我們執行 add 操作時：

<code>
public
 boolean 
add
(
E e
)
 {
    modCount++;
    
add
(e, elementData, size);
    
return
 
true
;
}
​
 
private
 
void
 
add
(
E e, Object[] elementData, 
int
 s
)
 {
    
if
 (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 
1
;
}/<code>

ArrayList 首先會比較數組長度和元素大小，如果相等，則執行 grow() 方法，進行擴容，擴容完成後，再把元素加到 elementData 數組元素中。注意，此時的 elementData ，事實上，已經不是它了，它已經變成可擴容後的它。

現在看看 grow 方法的實現：

<code>
private
 Object[] 
grow
(
)
 {
    
return
 grow(size + 
1
);
}
private
 Object[] 
grow
(
int
 minCapacity
) 
 {
    
int
 oldCapacity = elementData.length;
    
if
 (oldCapacity > 
0
 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
int
 newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity,  
                    oldCapacity >> 
1
            );
        
return
 elementData = Arrays.copyOf(elementData, newCapacity);
    } 
else
 {
        
return
 elementData = 
new
 Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}/<code>

實現的也很清晰，把原始元素大小，需要的最小擴容量(左移一位)，和期待的擴容量，做比較，最終得到一個新的容量大小。

之後通過 Arrays.copy 方法，將老數組的元素拷貝到新元素。

具體比較方式不貼了，簡單描述下：

0. 取最小擴容量和期待擴容量中的最大值，加上源數組大小，作為新的容量，我們設為 newLength。
1. 如果這個值在允許的最大數組長度(Integer.MAX_VALUE - 8) 內，返回
2. 否則，直接比較最大數組長度和 源數組長度 + 最小擴容量，滿足則返回
3. 否則，拋出 OutOfMemoryError

正常情況下，一次擴容的容量，會增加源數組大小的二分之一(即上面左移一位的操作)

LinkedList

底層基於雙向鏈表 實現，對於增刪，效率極高。

<code>
public
 
class
 
LinkedList
<
E
>
    
extends
 
AbstractSequentialList
<
E
>
    
implements
 
List
<
E
>, 
Deque
<
E
>, 
Cloneable
,  
java
.
io
.
Serializable
 
{
​
    
transient
 
int
 size = 
0
;
    
transient
 Node first;
    
transient
 Node last;
    
protected
 
transient
 
int
 modCount = 
0
;
}
​
private
 
static
 
class
 
Node
<
E
> 
{
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        
this
.item = element;
        
this
.next = next;
        
this
.prev = prev;
    }
}/<code>

可以看到， LinkedList 實現了 List，Deque，Cloneable 和 Serializable 接口。Deque 即我們所說的雙端隊列。在 util 包下，還有 ArrayDeque 的實現。

Node 的結構中，主要有 prev ， next 和 item ，分別指向上一個節點，下一個節點，item 保存當前節點數據。

因為每個節點都需要保存上下兩個節點的信息，所以必然比 ArrayList 要消耗更多的空間

Map

這裡以 HashMap 為主。

<code>
public
 
class
 
HashMap
<
K
,
V
> 
extends
 
AbstractMap
<
K
,
V
>
    
implements
 
Map
<
K
,
V
>, 
Cloneable
, 
Serializable
  
{
    
    
static
 
final
 
int
 DEFAULT_INITIAL_CAPACITY = 
1
 <
4
;  
    
static
 
final
 
int
 MAXIMUM_CAPACITY = 
1
 <
30
;
    
static
 
final
 
float
 DEFAULT_LOAD_FACTOR = 
0.75f
;
    
int
 threshold;
    
static
 
final
 
int
 TREEIFY_THRESHOLD = 
8
;
    
static
 
final
 
int
 UNTREEIFY_THRESHOLD = 
6
;
    
transient 
 Node[] table;
}/<code>

HashMap 幾個重要的參數：

• TREEIFY_THRESHOLD ： 樹化閾值， 即當 map 中的鏈表長度大於該值時， 會將鏈表轉為紅黑樹[1]
• UNTREEIFY_THRESHOLD ： 當紅黑樹 size 小於該值時，重新轉為鏈表
• DEFAULT_INITIAL_CAPACITY ： hashmap 初始化的容量大小
• table ： 即 hash 表，hashmap 做 hash 時，最終散列到這張表上，長度適中為 2n
• DEFAULT_LOAD_FACTOR ：常說的裝載因子 。hashmap 判斷是否需要 resize 時，會根據 threshold 判斷，而 threshold 則是根據 裝載因子 * table.length 算出來的

我們 new HashMap(9) 時， HashMap 就會去初始化 loadFactor 和 threshold [2]

HashMap 大概就長這個樣子：

HashMap 的擴容

當我們執行 put 操作時， HashMap 會先將元素添加到 Map 中，然後查看 size(即 Map 中的元素個數) 是否大於 threshold (閾值， 即上面根據 loadFactory * capacity 即 table.length 算出來的) ，如果大於，就進行擴容，即 resize() 方法。

<code>
if
 (++size > threshold)
    
resize
();/<code>

resize [3] 時， 首先判斷 table 是否初始化，沒有則先初始化 table ，然後根據 old table 以及初始化時的 loadFactor ，threshold 參數，計算新的 threshold ，以及需要擴容的大小，一般為 old table length 的 兩倍 。

介紹數組時，我們已經說過，數組無法擴容，而 HashMap 使用數組來維護 hash 表的，所以需要新建一個數組，這個數組的長度就是之前數組的兩倍 。

之後會進行元素移動，為什麼說創建 HashMap 時，要先規劃好大小，因為擴容這個操作是很消耗性能的，在一個 double for 循環中(for + while) 。

元素移動完畢後，擴容結束。

Queue

隊列，FIFO， first in first out， 先進先出。

java 中 Queue 實現 Collection 接口。具體的實現有

• LinkedBlockingQueue ：基於 LinkedList 的阻塞隊列
• ArrayBlockingQueue ：基於 Array 的阻塞隊列
• ArrayDeque ： 基於 Array 的雙端隊列
• LinkedList ： 是的， LinkedList 實現了 Deque 接口，也是一個雙端隊列，Deque deque = new LinkedList();

隊列常用方法：

• add ：添加節點，加入隊列尾部， tail
• remove ：刪除頭節點， head
• peek ：獲取 head 節點，但是不刪除 , 偷取元素
• poll ：獲取 head 節點，並刪除
• offer ：立即插入節點到 tail ， 對於定長隊列，有空間且插入成功則返回 true ， 若插入失敗，則返回 false 。add 會拋出異常。
• push ： Deque 接口所有，插入元素到 head 。
• take ： BlockingQueue 接口所有 ，獲取並刪除 head 節點。 如果當前 queue 沒有元素，則會阻塞 。

Stack

棧， FILO ， first in last out ，先進後出。

• peek ： 獲取 head ，但不會刪除，偷取元素
• pop ： 獲取 head ， 同時刪除， 彈出元素
• push ： 壓入棧

註釋

[1]

看 HashMap 源碼的時候，發現在 resize 時，對 for i 循環的時候，都是用 for(;;++1) 的寫法：

<code>
for
 (
int
 j = 
0
; j < oldCap; ++j) { ... }/<code>

平時不都是 fro(;;i++) 的嗎？然後想了下，i++ 會產生一箇中間變量，用於暫時寄存自增前的變量，這一步會消耗一定的性能。

當然，平時我們寫代碼，最後編譯的時候，編譯器會把這部分優化成 ++i

[2]

HashMap 初始化時(帶 capacity 參數)，我們跟蹤下代碼，就會發現，最終調用：

<code>
static
 
final
 
int
 
tableSizeFor(int
 
cap)
 
{
    
int
 
n
 
=
 
-1
 
>>>
 
Integer.numberOfLeadingZeros(cap
 
-
 
1
);
    
return
 
(n
 
<
 
0
)
  
?
 
1 :
 
(n
 
>=
 
MAXIMUM_CAPACITY)
 
?
 
MAXIMUM_CAPACITY :
 
n
 
+
 
1
;
}
//
 
Integer.numberOfLeadingZeros
public
 
static
 
int
 
numberOfLeadingZeros(int
 
i)
 
{
    
if
 
(i
 
 
0
)
         
return
 
i
 
==
 
0
 
?
 
32 :
 
0
;
    
int
 
n
 
=
 
31
;
    
if
 
(i
 
>=
 
1
 
 
16
)
 
{
 
n
 
-=
 
16
;
  
i
 
>>>=
 
16
;
 
}
    
if
 
(i
 
>=
 
1
 
  
8
)
 
{
 
n
 
-=
  
8
;
 
i
 
>>>=
  
8
;
 
}
    
if
 
(i
 
>=
  
1
 
  
4
)
 
{
 
n
 
-=
  
4
;
 
i
 
>>>=
  
4
;
 
}
    
if
 
(i
 
>=
 
1
 
  
2
)
 
{
 
n
 
-=
  
2
 
;
 
i
 
>>>=
  
2
;
 
}
    
return
 
n
 
-
 
(i
 
>>>
 
1
);
}
/<code>

這個方法在幹嘛呢？

我們知道， java 是通過 補碼 計數的。

原碼 ： 原碼很好理解，就是一個數的二進制表示， 對於一個四位數，則 2 的原碼為 0010， -2 為 1010

反碼 ： 對於正數而言，其原碼 = 反碼， 對於負數而言，則只需要將其原碼除符號位以外的數取反即可。同樣對於四位數，2 為 0010 ， -2 為 1101

補碼 ： 對於正數而言， 其原碼 = 補碼，對於負數而言，則是將其反碼 + 1 。 還是對於四位數， 2 為 0010 ， -2 則為 1110

溢出 ： java 中，我們偶爾會碰到溢出 。我們知道， java 的基本數據類型中， 如 byte ,長度是一個字節，也就是 8 位，範圍是 -128 ~ 127 。1111 1111 = 255 啊！ 為什麼最大是 127 呢？ 因為他們都是有符號數據類型(最高位 0 表示正數， 1 表示負數)，最高位是符號位， 所以 1111 1111 事實上應該是 -1

當我們計算兩個 byte 類型的 如 127 + 127 時，輸出了 -2 。因為 0111 1111 + 0111 1111 = 1111 1110 ， 對於 byte 類型，最高位符號位變成了 1 。這個二進制補碼還原成十進制，就是 -2 。

關於補碼的更多介紹，可參考 這裡

現在回到代碼。

numberOfLeadingZeros 這個方法，java init 是一個 32 位數，我們假設 i > 1<< 16 ， 這表明 i 的高 16 位中，至少有一個 1 ， 所以將 n (從左往右，連續的 0 的個數) - 16 ，即低 16 位可以不考慮了。

然後將 i 無符號右移(感覺這裡 >> 和 >>> 都一樣，因為負數已經在第一步就 return 掉了) 16 位 ， 繼續判斷，直到最後。假設 i = 0011 ， 則最後變成 ： 31 - (0011 >>> 1) = 31 - 0001 = 30 。

取得這個數後，對 -1 做無符號右移， -1 是 ffff ffff ， 右移 n 位後， 再加上 1，可保證得到一個 cap 向上的 2 的次冪。

至於為什麼 HashMap 的 capacity 一定要是 2 次冪， 這就要說到它的 hash 算法了：

<code>
static
 
final
 
int
 
hash
(Object key)
 
{
    
int
 h;
    
return
 (key == 
null
) ? 
0
 : (h = key.hashCode()) ^ (h >>> 
16
);
}/<code>

可以看到， 這裡將 key 的 hashcode 低 32 位和高 32 位做亦或運算 。

<code>
if
 
((p
 
=
 
tab[i
 
=
  
(n
 
-
 
1
)
 
&
 
hash])
 
==
 
null
)
 
{
    
tab[i]
 
=
 
newNode(hash,
 
key,
 
value,
 
null
);
}
/<code>

放 node 時， index 是根據 (n-1) & hash 來運算的。

因為 n 是一個 2 次冪，所以 n-1 是一個全 f 的數， 對 hash 做與運算，即拿到 hash 的低位。

如， HashMap capacity = 8 ，即 n = 8 ，則 n-1 = 0000 0111 假設 key 的 hash 為 0111 0010 ， 則 (n-1) & hash = 0000 0010 = 2，會被放入 tab[2] 中。

這樣有什麼問題呢？ 即每次都只有 key 的低位參與了運算，會導致較大概率的 hash 碰撞。

所以 HashMap 的 hash 算法，將其 hash 的低 16 位和高 16 位做了亦或，保證數據的更大的隨機性，從而減小 hash 碰撞的可能性。

同時，全程的位操作，也給計算帶來了性能上的優勢。

[3]

參見 樹 -- 算法淺析