一、數組的索引為什么從0開始？

尋址公式： 數組的首地址+索引乘以存儲數據的類型大小
在根據數組索引獲取元素的時候，會用索引和尋址公式來計算內存所對應的元素數據。如果數組的索引從1開始，尋址公式中，就需要增加一次減法操作（數組的首地址-1），對于CPU來說就多了一次指令，性能會降低。

二、數組進行查找操作的時間復雜度

• 如果是通過下標，查詢的時間復雜度是O(1)
• 如果不通過下標，和使用的查找方式有關
  – 從頭往后順序查找是O(n)
  – 排序后，使用二分查找發是O(log)

三、數組進行修改操作的時間復雜度

進行插入或者修改操作是，為了保證數組的連續性，需要挪動元素，平均復雜度是O（n）

四、ArrayList的底層實現原理

• ArrayList底層是用動態的數組實現的
• ArrayList初始容量為0，當第一次添加數據的時候才會初始化容量為10
• ArrayList在進行擴容的時候是原來容量的1.5倍，每次擴容都需要拷貝數組
• ArrayList在添加數據的時候
  1. 確保數組已使用長度（size）加1之后足夠存下下一個數據
  2. 計算數組的容量，如果當前數組已使用長度+1后的大于當前的數組長度，則調用grow方法擴容，擴容為原來的1.5倍
  3. 確保新增的數據有地方存儲之后，則將新元素添加到位于size的位置上。
  4. 返回添加成功布爾值。

五、List list = new ArrayList(10)中list擴容了幾次

未進行擴容，該語句只是聲明了一個長度為10的ArrayList。

六、數組和List之間如何轉換

• 數組轉List
  – 調用Arrays.asList()方法

// 轉換完成后，進行的修改會影響生成的List,因為只進行了地址的引用
String[] strArr = {"1","2"};
List<String> stringList = Arrays.asList(strArr);

• List轉數組
  – 調用list的toArray方法（）

// 轉換完成后，進行的修改不會影響生成的Array數組，因為底層進行了數據的拷貝
List<String> list = new ArrayList(n);
String[] toArray = list.toArray(new String[list.size()]);

七、單向鏈表和雙向鏈表的區別是什么

• 單向鏈表只有一個方向，結點只有一個后繼指針next。
• 雙向鏈表它支持兩個方向，每個結點不止有一個后繼指針next指向后面的結點，還有一個前驅指針prev指向前面的結點
• 單項鏈表的增刪查操作時間復雜度在頭結點是O(1)，其他是O(n)。
• 雙向鏈表的增刪查操作時間復雜度在頭尾結點是O(1)，其他是O(n)，如果給定節點，則增刪是O(1)

八、ArrayList好LinkedList區別是什么

• ArrayList是動態數組的數據結構實現； LinkedList是雙向鏈表的數據結構實現
• ArrayList按照下標查詢的時間復雜度O(1）；LinkedList按照下標查詢的時間復雜度O(n)
• ArrayList插入或者刪除元素的速度是O(n)；LinkedList插入或者刪除元素的速度是O(1)
• ArrayList底層是連續的數組，占用內存更小；LinkedList是雙向鏈表需要存儲數據，和兩個指針，更占用內存

線程方面
ArrayList和LinkedList都不是線程安全的，想要保證安全有兩個方法

1. 在方法內使用，局部變量大多數情況下是線程安全的（在內部開多線程或者引用了共享的變量就不安全了）
2. 使用線程安全的ArrayList和LinkedList（用Collections.synchronizedList方法包一下）

// 性能會下降
List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());

九、說一說二叉樹和二叉搜索樹

二叉樹

1. 每個節點最多有兩個“叉”，分別是左子節點和右子節點。
2. 不要求每個節點都有兩個子節點，有的節點只有左子節點，有的節點只有右子節點。
3. 二叉樹每個節點的左子樹和右子樹也分別滿足二叉樹的定義

二叉搜索樹

1. 二叉搜索樹(Binary Search Tree,BST)又名二叉查找樹，有序二叉樹
2. 在樹中的任意一食節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值
3. 沒有鍵值相等的節點
4. 通常情況下二叉樹搜索的時間復雜度為O(logn)

十、說一說紅黑樹

1. 紅黑樹也是一種自平衡二叉樹
2. 紅黑樹的增刪查時間復雜度都是O(logn)
3. 紅黑樹節點要么是紅色要么是黑色
4. 紅黑樹節點根節點都是黑色，葉子結點也是黑色且為空值
5. 紅黑樹紅色節點的子節點都是黑色
6. 從任意節點到葉子節點的所有路徑都包含相同數目的黑色節點
7. 紅黑樹所有規則都是為了保證平衡

十一、說一說散鏈表

1. 散列表(Hash Table)又名哈希表/Hash表，是根據鍵(Key)直接訪問在內存存儲位置值(Value)的數據結構。是由數組演化而來的，利用了數組支持按照下標進行隨機訪問數據
2. 散列表的key是根據hash計算得來的，相同和key算出來的hash值一定相同。當不同的key計算出相同的hash值時，就會發生散列沖突，又名哈希碰撞
3. 解決散列表沖突方方法是鏈表法，又名拉鏈。存儲hashkey數組的每個下標位置稱之為桶(bucket)或者槽(slot)，每個桶會對應一條鏈表。hash沖突后的元素都放到相同的桶對應的鏈表中或紅黑樹中。

十二、說一說HashMap的實現原理

1. HashMap的底層的數據結構是hash表，即數組加鏈表或數組加紅黑樹
2. 當我們往HashMap中put元素時，利用尋址算法算出當前對象的元素在數組中的下標。此時如果出現hash值相同的key會再次對key進行比較：如果key相同，則覆蓋原始值；如果key不同，則將當前的key-value放入鏈表或紅黑樹中
3. 獲取時，尋址算法得到對應的桶索引位置，在進一步判斷key是否相同，從而找到對應值。
4. jdk1.8之后當鏈表的長度大于8且數組長度大于64時，會轉換為紅黑樹；擴容resize()時，紅黑樹拆分成的樹的結點數小于等于臨界值6個，則退化成鏈表

十三、說一說HashMapput方法的具體流程

1. 判斷鍵值對數組table是否為空或為null,否則執行resize()進行擴容(初始化)
2. 根據尋址算法得到對應的桶索引位置table[i]
3. 判斷table[i]==null,條件成立，直接新建節點添加
4. 如果table[i]==null,不成立
   4.1 判斷table[i的首個元素是否和key一樣，如果相同直接覆蓋value
   4.2 判斷table[i]是否為treeNode,即table[i]是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對
   4.3 否則遍歷table[i]，鏈表的尾部插入數據，然后判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，若遍歷過程中若發現key已經存在則直接覆蓋value
5. 插入成功后，判斷實際存在的鍵值對數量size是否超過了最大容量threshold(數組長度*0.75)，如果超過，進行擴容。

十四、說一說HashMap的擴容機制

1. 在添加元素或初始化的時候需要調用resize方法進行擴容，第一次添加數據初始化數組長度為16，以后每次擴容都是達到了擴容閾值（數組長度*0.75）
2. 每次擴容的時候，都是擴容之前容量的2倍；
3. 擴容之后，會新創建一個數組，需要把老數組中的數據挪動到新的數組中
   – 沒有hash沖突的節點，則直接使用e.hash&(newCap-1)計算新數組的索引位置（newCap是新數組長度）
   – 如果是紅黑樹，走紅黑樹的添加
   – 如果是鏈表，則需要遍歷鏈表，可能需要拆分鏈表，判斷(e.hash&oldCap)是否為0，為0該元素的位置停留在原始位置，否則移動到原始位置+增加的數組大小這個位置上（oldCap是老數組長度）

十五、說一說HashMap的尋址算法

1. 計算對象的hashCode()
2. 再進行調用hash()方法進行二次哈希，hashcode值右移16位再異或運算，讓哈希分布更為均勻
3. 最后(capacity-1)&hash得到索引。這個運算相當于hash%capacity且更快，但是這個只對2的冪數生效

十六、為何HashMap的數組長度一定是2的次冪？

1. 計算索引時效率更高：如果是2的n次冪可以使用位與運算代替取模
2. 擴容時重新計算索引效率更高：hash&oldCap==0的元素留在原來
   位置，否則新位置=舊位置+oldCap

十七、說一說hashmap在jdk1.7情況下的多線程死循環問題

在jdk1.7的hashmap中在數組進行擴容的時候，因為鏈表是頭插法，在進行數據遷移的過程中，有可能導致死循環

比如說，現在有兩個線程
線程一：讀取到當前的hashmap數據，數據中一個鏈表，在準備擴容時，線程二介入
線程二：也讀取hashmap，直接進行擴容。因為是頭插法，鏈表的順序會進行顛倒過來。比如原來的順序是AB，擴容后的順序是BA，線程二執行結束。
線程一：繼續執行的時候就會出現死循環的問題。
線程一先將A移入新的鏈表，再將B插入到鏈頭，由于另外一個線程的原因，B的next指向了A，所以B->A->B,形成循環。
當然，JDK8將擴容算法做了調整，不再將元素加入鏈表頭（而是保持與擴容前一樣的順序），尾插法，就避免了jdk7中死循環的問題。