1. 二叉樹、BST、AVL、B樹、B+樹、紅黑樹：節(jié)點存儲方式、時間復雜度、特點

1. 二叉樹：節(jié)點存值
   1. 遍歷方式：前(根左右)、中(左根右)、后(左右根)
   2. 時間復雜度
      1. 查找、插入、刪除都是On
   3. 容易形成單向鏈表
2. BST：節(jié)點存值，節(jié)點值按照左根右從小到大排序，中序遍歷為遞增
   1. 時間復雜度
      1. 查找、插入、刪除都是On
3. AVL：節(jié)點存值，左右子樹高度不超過1
   1. 時間復雜度
      1. 查找、插入、刪除都是Ologn
4. B樹：節(jié)點可以存m-1個值，葉子節(jié)點位于同一層
   1. 時間復雜度：O(logn)，二分查找比較節(jié)點的值
5. B+樹：節(jié)點可以存m個值，葉子節(jié)點存數(shù)據(jù)且升序，非葉子節(jié)點存數(shù)據(jù)索引。
   1. 查找效率穩(wěn)定，數(shù)據(jù)必定在葉子節(jié)點
   2. 葉子節(jié)點數(shù)據(jù)通過指針指向連接，形成升序鏈表。
   3. 時間復雜度：O(logn)
6. 紅黑樹：節(jié)點紅黑相間，根節(jié)點為黑，從任一節(jié)點出發(fā)到葉子節(jié)點都有相同數(shù)量的黑節(jié)點
   1. 紅黑樹不是嚴格的AVL樹，查詢效率可能比AVL樹低，但是插入操作進行的旋轉(zhuǎn)次數(shù)比AVL樹要少，至多3次。
   2. 適合頻繁插入和刪除且數(shù)據(jù)量大的情況
   3. 時間復雜度：同AVL

2. 數(shù)組和鏈表：內(nèi)存存儲、時間復雜度、優(yōu)缺點、使用場景

1. 數(shù)組：在內(nèi)存中連續(xù)存儲，通過索引來隨機獲取元素，查詢快增刪慢。
   1. 時間復雜度：查詢O1，刪除On，頭插On，尾插O1
   2. 大小固定，擴容要新建數(shù)組，類型單一
   3. 適用于數(shù)據(jù)量少且查詢較多
2. 鏈表：在內(nèi)存中非連續(xù)存儲，只能順序訪問，查詢慢增刪快
   1. 時間復雜度：查詢On，刪除O1，頭插On，尾插O1
   2. 無初始容量，無上限，但內(nèi)存消耗大，因為存在大量的指針
   3. 適合數(shù)據(jù)量少增刪多

3. 集合類：List接口、Set接口、Queue接口、Map。從數(shù)據(jù)結(jié)構(gòu)以及特點來講

1. List
   1. ArrayList：數(shù)組，查詢快增刪慢，線程不安全
   2. LinkedList：雙向鏈表，查詢慢增刪快，線程不安全
   3. Vector：線程安全版的ArrayList
2. Set
   1. TreeSet：紅黑樹，有序且唯一，底層是treemap，compareTo實現(xiàn)唯一，比較器實現(xiàn)有序
   2. HashSet：哈希表，無序且唯一，底層是hashmap，compareTo實現(xiàn)唯一
   3. LinkedHashSet：雙向鏈表維護HashSet集合
3. Queue
   1. LinkedList
   2. PriorityQueue：優(yōu)先隊列，大根堆小根堆
4. Map
   1. HashMap：數(shù)組+鏈表+紅黑樹，key無序且唯一，通過hashcode和equals實現(xiàn)唯一
   2. TreeMap：紅黑樹，key有序且唯一，compareTo實現(xiàn)唯一，比較器實現(xiàn)有序
   3. LinkedHashMap：雙向鏈表+HashMap，有序的HashMap
   4. HashTable：數(shù)組+鏈表，線程安全
   5. concurrentHashMap：線程安全的HashMap。

4. HashMap概述：數(shù)據(jù)結(jié)構(gòu)、初始容量、擴容、樹化、時間復雜度、為什么線程不安全。好文：https://zhuanlan.zhihu.com/p/76735726

1. 1.8之前

1. 數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表，數(shù)組存KV鍵值對，查詢時間復雜度：On，最好O1。存儲時間復雜度O1。
2. 初始容量：16，加載因子0.75。擴容2倍。當threshold == 加載因子 * 當前數(shù)組長度時，擴容
3. 節(jié)點存入方式：頭插法，多線程先可能出現(xiàn)節(jié)點翻轉(zhuǎn)時導致循環(huán)鏈表
4. 數(shù)組是用來確定桶的位置，利用key的hash值與數(shù)組長度-1取模得到. 鏈表是用來解決hash沖突問題，當出現(xiàn)hash值一樣的情形，就在數(shù)組上的對應位置通過頭插法形成一條鏈表。

2. 1.8之后

1. 數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹，當鏈表長度大于等于8時，樹化。存儲時間復雜度O1，查詢時間復雜度降為Ologn
2. 初始容量不變，擴容也不變。但是擴容會重新計算長度和閾值。
3. 節(jié)點存入方式：尾插法，解決了環(huán)形鏈表問題，但是多線程下可能會發(fā)生數(shù)據(jù)覆蓋，依舊是線程不安全
4. hashmap的rehash采用的是位運算函數(shù)

5. HashMap的put機制：1.8前后

1. 1.8之前：
   1. 先判斷數(shù)組是否為空，如果為空，新建一個數(shù)組，長度為16
   2. 如果key為null，存入table[0]，遍歷table[0]數(shù)組下的鏈表，通過hashcode和equals判斷是否存在相同的key，如果是，替換，否則，存入鏈表頭
   3. 如果key不為null，將key的hashcode傳入indexFor，計算出index位置，遍歷table[index]下的鏈表，通過hashcode和equals判斷是否存在相同的key，如果是，替換value。
   4. 如果key不重復，addEntry添加節(jié)點到鏈表頭，判斷是否需要擴容
2. 1.8之后：調(diào)用putVal方法
   1. 先判斷數(shù)組是否為空，如果為空，新建一個數(shù)組，長度為16
   2. 根據(jù)key的hashcode和數(shù)組長度-1進行與運算得到index位置，如果table[index]位置下沒有Node節(jié)點，將key和value封裝成Node節(jié)點存入。如果第一個節(jié)點的hash和key相同，替換value值
   3. 否則先提取節(jié)點，如果節(jié)點是樹節(jié)點，調(diào)用樹方法將key和value存入樹中。如果是鏈表節(jié)點，如果遍歷鏈表的過程中通過hashcode和equals沒有發(fā)現(xiàn)相同的key，將key和value封裝成Node節(jié)點，存入鏈表尾部。如果發(fā)現(xiàn)相同key，替換value。判斷鏈表長度是否大于等于8，如果是，進行樹化。
   4. 判斷數(shù)組是否需要擴容

6. HashMap的get機制：1.8前后

1. 1.8之前
   1. 先判斷數(shù)組是否為空，如果為空，直接返回null
   2. 判斷key是否為null，如果為null，調(diào)用getForNullKey查找table[0]數(shù)組，遍歷鏈表，通過hashcode和equals查找key，找到，返回value，否則返回null
   3. 如果key不為null，調(diào)用getForEntry，將key的hashcode傳入indexfor計算得到index，遍歷table[index]下的鏈表，通過hashcode和equals查找key，找到返回value，否則返回null
2. 1.8之后
   1. 調(diào)用getNode
      1. 如果數(shù)組為空，返回null
      2. 如果數(shù)組不為空，查找第一個Node節(jié)點是否與key相同，如果相同，直接返回
      3. 如果節(jié)點是樹節(jié)點，調(diào)用getTreeNode查找
      4. 如果節(jié)點是鏈表節(jié)點，遍歷鏈表，通過hashcode和equals查找key，找到返回value，否則返回null

7. HashMap的resize機制：1.8

1. 1.8之前的resize
   1. 在put的addEntry中判斷是否需要擴容，先判斷數(shù)組長度是否大于threshold閾值，如果是，調(diào)用resize擴容
   2. resize先提取舊數(shù)組容量，判斷舊容量是否已經(jīng)到達MAXVALUE，如果是，將threshold設(shè)置為Integer.MAX_VALUE，不再擴容，直接返回。否則新建一個數(shù)組，長度為原來的兩倍，調(diào)用transfer進行轉(zhuǎn)移
   3. transfer遍歷舊數(shù)組元素，調(diào)用rehash判斷是否需要重新進行hash，調(diào)用indexFor計算index，頭插法將節(jié)點轉(zhuǎn)移到新數(shù)組中
2. 1.8之后要重新規(guī)劃長度和閾值，會重新排序
   1. 重新規(guī)劃長度和閾值
      1. 最大容量：先判斷舊容量是否到達最大容量，如果是，將threshold設(shè)置為Integer.MAX_VALUE，不再擴容，返回
      2. 兩倍擴容：如果當前容量的兩倍小于最大容量并且當前容量大于16，當前容量擴大兩倍
      3. threshold：如果都不滿足且threshold大于0，將threshold設(shè)置為容量
      4. 初始16和12：否則將長度設(shè)置為16，threshold為12
   2. 重新排序節(jié)點
      1. 如果節(jié)點為null，不處理
      2. 如果是樹節(jié)點，調(diào)用split方法處理。
      3. 如果是鏈表節(jié)點：將鏈表拆分為hash值超出舊容量和未超出舊容量的情況。如果hash計算結(jié)果為0，原位置，不處理。否則將節(jié)點存入到新下標，新下標 = 舊容量+舊下標

8. 線程安全問題:環(huán)形鏈表和數(shù)據(jù)覆蓋

1. 1.8之前：
   1. 環(huán)形鏈表：transfer采用頭插法，多線程下可能出現(xiàn)節(jié)點翻轉(zhuǎn)指向同一個位置
2. 1.8之后
   1. 尾插法可能導致數(shù)據(jù)覆蓋。

9. HashMap的初始容量為什么是2的n次方：防止數(shù)組越界、hash分別更均勻、轉(zhuǎn)換為與運算

1. 防止數(shù)組越界，因為數(shù)組index位置是通過key的hash值跟數(shù)組的長度-1進行與運算得到的，如果數(shù)組長度為2的n次方，那么長度-1的二進制就是11111...的數(shù)，與運算，最大的結(jié)果也不會發(fā)生數(shù)組越界
2. 為了使hash分布更均勻，長度-1的二進制位1111....，這種二進制數(shù)進行與運算時，出現(xiàn)重復數(shù)的概率低，hash沖突發(fā)生概率低
3. 將取模運算轉(zhuǎn)換為與運算，效率更高

10. hash沖突如何解決(hash碰撞是指兩個不同的對象計算出同一個hashcode。hash沖突是指hashmap中桶位置重疊)，hash函數(shù)類型：開放定址法、rehash、拉鏈法

1. 開放定址法：線性探測，當發(fā)生hash沖突時，從該hash值的地址往下搜索，直到找到一個不沖突的hash值為止
2. rehash：定義多個hash函數(shù)，當發(fā)生hash沖突時，輪番調(diào)用函數(shù)重新進行計算，直到不發(fā)生沖突為止。常見的hash函數(shù)有：位運算(HashMap)、乘法(String)、加法
3. 拉鏈法：頭插和尾插
4. image

   。紫色的為數(shù)組，綠色的為鏈表

11. HashTable如何解決線程安全：put和get方法加synchronized、初始容量、擴容、key-value

1. hashtable的初始容量為11，擴容2倍+1。key和value都不能為null
2. 通過在put和get方法加synchronized實現(xiàn)線程安全

12. ConcurrentHashMap如何解決線程安全問題：1.8前后

1. hashtable主要的問題就是對整個put方法加鎖，并發(fā)低。
2. concurrentHashMap在1.8之前通過Segment分段鎖 + Entry節(jié)點實現(xiàn)，每個分段鎖維護一段數(shù)組，多個線程可以同時訪問不同的分段鎖，并發(fā)提高
3. concurrentHashMap在1.8之后通過Cas + synchronized + Node節(jié)點實現(xiàn)，鎖住Node節(jié)點，鎖粒度小。當數(shù)組index位置下沒有元素時，通過CAS方式存入節(jié)點

13. ConcurrentHashMap的put機制：1.8版本

1. 先判斷key和value是否為null，concurrentHashMap的key和value不能為null，如果為null，break
2. 計算key的hash值，確定index位置。
3. while true循環(huán)，因為可能會發(fā)生擴容和初始化數(shù)組
   1. 提取節(jié)點
   2. 如果數(shù)組為空，創(chuàng)建一個數(shù)組
   3. 如果數(shù)組不為空，但是table[index]位置下沒有元素，將key和value封裝成Node節(jié)點，CAS方式存入
   4. 如果正在發(fā)生擴容，table數(shù)組提取擴容后返回的數(shù)組
   5. 對節(jié)點上鎖
      1. 遍歷鏈表，如果在鏈表中找到相同的key，替換value，如果沒有找到，尾插法存入鏈表
      2. 如果節(jié)點是樹節(jié)點，putTreeVal存入
      3. 判斷鏈表長度是否大于等于8，如果是，進行樹化
4. 容量+1，判斷數(shù)組是否需要擴容

14. ConcurrentHashMap的get機制要加synchronized嗎：Node節(jié)點加volatile，線程間可見

1. 因為Node節(jié)點的value和Node節(jié)點.next都是使用volatile修飾，多線程下修改value或者增刪Node節(jié)點都是線程間可見的

15. ArrayList概述：數(shù)據(jù)結(jié)構(gòu)、初始容量、擴容、時間復雜度、線程不安全

1. 數(shù)據(jù)結(jié)構(gòu)：數(shù)組
2. 初始容量：10
3. 擴容：1.5倍，通過Arrays.copyOf()復制到新數(shù)組
4. 線程不安全
5. 時間復雜度：查詢O1，刪除On，頭插On，尾插O1

16. ArrayList的grow：創(chuàng)建新數(shù)組，1.5倍，通過Arrays.copyOf()復制，底層調(diào)用了System.arraycopy()，擴容開銷大

1. add時先判斷容量，如果容量不夠，調(diào)用grow進行擴容
2. grow會創(chuàng)建一個新數(shù)組，長度為1.5倍，使用Arrays.copyOf轉(zhuǎn)移元素。底層調(diào)用System.arraycopy()，開銷大

17. ArrayList的add：先判斷是否越界，判斷是否需要擴容，調(diào)用System.arraycopy()添加

1. 先判斷index是否越界，如果是，拋出越界異常
2. 判斷數(shù)組是否需要擴容
3. 調(diào)用System.arraycopy()添加

18. ArrayList的remove：先判斷是否越界、提取數(shù)組、調(diào)用fastRemove()、調(diào)用System.arraycopy()刪除

1. 先檢查index是否越界，如果越界，拋出越界異常
2. 提取數(shù)組對象
3. 調(diào)用fastRemove，調(diào)用System.arraycopy()刪除，返回刪除后的數(shù)組對象

19. 如何解決ArrayList線程不安全問題：使用Vector、Collections.synchronizedList()、原子類CopyOnWriteArrayList

1. 使用Vector，效率低
2. 使用Collection接口的線程安全方法Collections.synchronizedList()
3. 使用原子類CopyOnWriteArrayList，使用synchronized實現(xiàn)

20. Vector和ArrayList有什么區(qū)別，Vector如何解決線程不安全：就是一個線程安全的ArrayList，通過在add和get方法加synchronized解決，鎖粒度大，效率低

1. Vector就是一個線程安全的ArrayList，初始容量10，擴容2倍，也是通過Arrays.copyOf()
2. 通過對add和get方法加synchronized實現(xiàn)線程安全。

21. ArrayList和LinkedList比較：數(shù)據(jù)結(jié)構(gòu)、初始容量擴容、時間復雜度、線程安全、100W數(shù)據(jù)插入(頭擦和尾插)

1. 數(shù)據(jù)結(jié)構(gòu)：
   1. ArrayList：數(shù)組，可以通過索引隨機訪問
   2. LinkedList：鏈表，只能順序訪問
2. 初始容量：
   1. ArrayList初始容量10，擴容1.5倍
   2. LinkedList無
3. 時間復雜度：
   1. ArrayList
      1. 查詢O1
      2. 刪除On
      3. 頭插On
      4. 尾插O1
   2. LinkedList
      1. 查詢On
      2. 刪除O1
      3. 頭插On
      4. 尾插O1
4. 都是線程不安全
5. 存100W數(shù)據(jù)
   1. 頭插：LinkedList完勝，因為ArrayList的add和grow都要調(diào)用System.arraycopy()進行轉(zhuǎn)移元素
   2. 尾插：ArrayList完勝，且效率越來越高。因為ArrayList需要擴容，前期擴容頻繁，但是后期擴容越來越少。

22. ArrayList的刪除方法：使用Iterator方式、倒序遍歷、remove方法

1. 正序for循環(huán)：元素前移后忽略元素，不可取

    public static void remove(ArrayList<String> list) {
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            if (s.equals("b")) {
                list.remove(s);
            }
        }
    }

2. foreach循環(huán)：不能用
3. Iterator迭代器：正確方式

    public static void remove3(ArrayList<String> list) {
        Iterator<String> it = list.iterator();  
        while (it.hasNext()) {  
            String s = it.next();  
            if (s.equals("b")) {  
                it.remove();  
            }  
        }  
    }

4. 倒序for循環(huán)：解決了前移忽視元素的情況

public static void remove14(List<String> list, String target){
        for(int i = list.size() - 1; i >= 0; i--){
            String item = list.get(i);
            if(target.equals(item)){
                // List 刪除元素的邏輯是將目標元素之后的元素往前移一個索引位置，最后一個元素置為 null，同時 size - 1
                list.remove(item);
            }
        }
        print(list);
    }

5. 使用remove方法
   1. 按照索引刪除：List.remove(index)
   2. 按照value值刪除：List.remove(Integer.valueOf(value))