哈希表

就是一個鏈表數組（Node[]） **在10w數量級上，哈希表的性能要優于紅黑樹

? ? 廣義
? ? 理論
? ? 處理方式（開散列 閉散列）
? ? 考點：四個角度解析源碼（21.1.18）：{
? ? ? ? 成員變量：數據結構，樹化閾值
? ? ? ? 構造函數：Lazy-Load hash方法
? ? ? ? Put與get流程
? ? ? ? 哈希算法，擴容，性能}

***JDK8之后，HashMap引入了紅黑樹，當一個鏈表的長度超過一個值(最小容量64)時，就會“樹化”，將鏈表轉為紅黑樹（就會進一步降低查找的時間復雜度 O(n）->O(logn)
七大排序

排序的穩定性：待排序的序列中若存在值相等的元素，經過排序之后，相等元素之間的原有先后順序保持不變，就叫穩定的排序算法

（基于比較【直接把兩個元素進行大小比較的排序：內部排序，將數據都在內存中操作】）

//外部排序：需要借助硬盤等輔助存儲介質進行的排序操作（大數據排序，數據大到內存放不下：桶排序（基于歸并思想），技術排序，基數排序）

插入圖

? ? 堆排序（heapSort）
? ? 冒泡排序（bubbleSort）
? ? 選擇排序（）：每次在一組待排序的數據中選擇最大（最小值）的一個元素，存放在無序區間的最后或者最前，知道全部待排序元素排列完(所有排序算法，一定要注意變量和區間的嚴格定義)>>優化為雙向選擇排序 ?不穩定
? ? 插入排序（）：打撲克>>天然的插入排序 （直接插入排序+折半插入排序【二分查找法（有序區間）】）
? ? 希爾排序（）：縮小增量排序>>先選定一個整數gap，將待排序的數據中所有記錄按gap分組。所有距離為gap的數據放在同一組，將組內元素排序。然后不斷縮小gap的大小，直到變為1，當gap變為1時，整個數據已經近乎有序（直接插入最好的情況），調用剖同插入排序統一排序即可 不穩定
? ? 歸并排序（）：將集合分為兩大階段 ：歸&并 穩定
? ? 快速排序（）：選取一個分區點（基準值），將數組分為三部分，基準值之前的數組<基準值<大于基準值，重復快排過程 不穩定

輔助測試：

? ? 生成n個隨機數的方法
? ? 生成n個近乎有序的數（測試數據敏感度）
? ? 判斷數組是否是升序集合（測試排序算法是否正確）
? ? 測試賽排序性能-完全相同數據下不同算法耗時情況