2，Java中的數據結構
- 2020 年 3 月 6 日
- 筆記
1，字元串（String）
···String為特殊的引用類型，不可變。
···常用實例方法：
獲取子串：substring(start, end);
獲取索引：indexOf(char);
獲取字元：charAt(index)；
···常用靜態方法：
格式字元串：String.format(“%s”, 12);
轉為字元串：String.valueOf();
格式拼接：String.join(“, “, list);
···擴展：
StringBuilder：可變對象，用來高效拼接字元串。
StringBuffer：是StringBuilder的執行緒安全版。
··· 注意：
· String.valueOf()比str.toString()安全；
· 常量池默認只會在編譯期對字元串字面量和常量進行優化；可以通過””.intern()方法在運行期將堆中的字元串放入常量池。
2，數組
···可以通過索引訪問，初始化必須指定大小，並且不可改變。
···常用方法：
排序：Arrays.sort(int[]);
轉list：Arrays.asList(int[]); // 返回的list是固定長度的，不能改變。最好用for一個個轉。
擴容：Arrays.copyOf(int[], newlenght);
填充：Arrays.fill(int[], int);
···轉Set：
Set<T> set = new HashSet<>(Arrays.aslist(int[]));
由於Set構造方法的參數必須繼承自Collection介面，所以要先把數組轉list。
···逆序排序：
Integer[] a = new Integer[5];
Comparator<Integer> cmp = new Comparator<>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 – o1;
}
};
Arrays.sort(a, cmp);
3，列表（List）
···實現類：
ArrayList：數組實現；LinkedList：鏈表實現；Vector：執行緒安全；
···常用實例方法：
根據索引查找：get(index);
判斷是否存在：contains(obj);
查找索引：indexOf(obj);
排序：sort(Comparator)；
合併兩個list：addAll(list);
轉數組：toArray(new Obj[]{});
···常用靜態方法：
排序：Collections.sort(list,Comparator);
逆序：Collections.reverse(list);
求最值：Collections.max(list); Collection.min(list)；
淺拷貝：Collections.copy(dest, src); // dest的實際長度必須大於或等於src
···List的stream方法：
List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3));
List<Integer> a = list.stream().map(x-> x*2).collect(Collectors.toList());
4，集合（Set）
···實現類：
HashSet：數組實現，無序(有規律)；TreeSet：自動排序；LinkedHashSet：鏈表實現，保持原序；
···注意：
由於Set也繼承自Collection介面，所以其他方法與List類似，底層實現也是Hash，相當於是沒有value的Map。
5，鍵值對（Map）
···實現類：
HashMap：數組實現，無序；TreeSet：根據Key排序；LinkedHashMap：保持原序；
···常用實例方法：
獲得所有Key：KeySet()，返回值為Set類型；
獲得所有Value：values();
···排序：
先把map.entrySet()放入list，再用Collection.sort(list, Compartor)；對list的value排序，再把list放入LinkedHashMap中即可。
···注意：
HashMap中的key和value都可以為null。而Hashtable不可以。
··· *底層理解*：
·大致實現：HashMap底層使用的是哈希表加鏈表。輸入的key是對象的hashCode；哈希函數是hashCode & （lenght – 1）；哈希衝突的解決辦法是使用鏈表保存哈希值相同的對象。當鏈表長度大於8時使用紅黑樹保存(jdk1.8開始)；查詢時先通過對象的hashCode找到對象在數組的位置，然後通過equals()遍歷鏈表，找到目標對象。
·細節優化： 哈希函數hashCode & (lenght-1)是位運算， 比模運算快很多；由於哈希函數是hashCode & (lenght-1)，所以當哈希表的長度lenght是2的冪次方時哈希表的利用率最高，哈希衝突也就越小，比如：當lenght為15時hashCode & 14，hashCode & 1110 時第一位0與上任何數都為0，所以哈希函數的結果永遠不會出現第一位為1的情況，即0001、0011等位置上永遠不會存值，導致實際利用長度變小，也就越容易出現哈希衝突。
·擴容：由於數組的長度固定(默認是16)，所以當實際長度超過最大長度的75%時，需要對哈希數組進行擴容，增大為原最大長度的2倍，並將舊哈希表的元素重新計算哈希值放入新的哈希表中，非常消耗性能，所以在初始化時盡量指定長度，以避免擴容。例如：需要存放1000個元素時，指定初始化大小為2048（1024*75%<1000所以還會擴容，因此選擇2048）。
6，包裝類型
···概念：包裝類型是把基本類型包裝為引用類型，把基本類型轉為引用類型稱為裝箱，反之為拆箱。
···優點：
· 與基本類型相比，包裝類型提供了大量實用的方法。
· 在項目中盡量使用包裝類型，因為包裝類型的null和0可以區分有值和沒值。
注意事項
· a=a+12 與 a+=12 的區別：當a為short時，使用會把12當成int類型；而使用 += 時，會把右邊的字面量12轉為左邊變數的類型。
· 進位顯示：二進位(0b)：int b=0b101; 八進位(0)：int e=032; 十六進位(0x)：int h=0xf1;
· Boolean類型：boolean類型可以進行 位運算，並且運算符優先順序：>, &, &&，且位運算符與邏輯運算符的效果一樣，但是不會短路。
