一文搞懂所有Java集合面試題

• 2020 年 11 月 26 日
• 筆記
• HashMap, JAVA, Java基礎知識, Java集合, java面試題

Java集合

剛剛經歷過秋招，看了大量的面經，順便將常見的Java集合常考知識點總結了一下，並根據被問到的頻率大致做了一個標註。一顆星表示知識點需要了解，被問到的頻率不高，面試時起碼能說個差不多。兩顆星表示被問到的頻率較高或對理解Java有著重要的作用，建議熟練掌握。三顆星表示被問到的頻率非常高，建議深入理解並熟練掌握其相關知識，速食麵試時拓展（方便裝逼），給面試官留下個好印象。

推薦閱讀：一文搞懂所有Java基礎知識面試題

常用的集合類有哪些？　＊＊＊

Map介面和Collection介面是所有集合框架的父介面。下圖中的實線和虛線看著有些亂，其中介面與介面之間如果有聯繫為繼承關係，類與類之間如果有聯繫為繼承關係，類與介面之間則是類實現介面。重點掌握的抽象類有HashMap，LinkedList，HashTable，ArrayList，HashSet，Stack，TreeSet，TreeMap。注意：Collection介面不是Map的父介面。

List，Set，Map三者的區別？ ＊＊＊

• List：有序集合（有序指存入的順序和取出的順序相同，不是按照元素的某些特性排序），可存儲重複元素，可存儲多個null。
• Set：無序集合（元素存入和取出順序不一定相同），不可存儲重複元素，只能存儲一個null。
• Map：使用鍵值對的方式對元素進行存儲，key是無序的，且是唯一的。value值不唯一。不同的key值可以對應相同的value值。

常用集合框架底層數據結構　＊＊＊

• List：

  1. ArrayList：數組
  2. LinkedList：雙線鏈表

• Set：

  1. HashSet：底層基於HashMap實現，HashSet存入讀取元素的方式和HashMap中的Key是一致的。
  2. TreeSet：紅黑樹

• Map：

  1. HashMap： JDK1.8之前HashMap由數組+鏈表組成的， JDK1.8之後有數組+鏈表/紅黑樹組成，當鏈表長度大於8時，鏈錶轉化為紅黑樹，當長度小於6時，從紅黑樹轉化為鏈表。這樣做的目的是能提高HashMap的性能，因為紅黑樹的查找元素的時間複雜度遠小於鏈表。
  2. HashTable：數組+鏈表
  3. TreeMap：紅黑樹

哪些集合類是執行緒安全的？　＊＊＊

• Vector：相當於有同步機制的ArrayList
• Stack：棧
• HashTable
• enumeration：枚舉

迭代器 Iterator 是什麼　＊

Iterator 是 Java 迭代器最簡單的實現，它不是一個集合，它是一種用於訪問集合的方法，Iterator介面提供遍歷任何Collection的介面。

Java集合的快速失敗機制 「fail-fast」和安全失敗機制「fail-safe」是什麼？　＊＊＊

• 快速失敗

  Java的快速失敗機制是Java集合框架中的一種錯誤檢測機制，當多個執行緒同時對集合中的內容進行修改時可能就會拋出ConcurrentModificationException異常。其實不僅僅是在多執行緒狀態下，在單執行緒中用增強for循環中一邊遍歷集合一邊修改集合的元素也會拋出ConcurrentModificationException異常。看下面程式碼

  public class Main{
      public static void main(String[] args) {
      List<Integer> list = new ArrayList<>();
          for(Integer i : list){
              list.remove(i);  //運行時拋出ConcurrentModificationException異常
          }
      }
  }
  

  正確的做法是用迭代器的remove()方法，便可正常運行。

  public class Main{
      public static void main(String[] args) {
      List<Integer> list = new ArrayList<>();
      Iterator<Integer> it = list.iterator();
          while(it.hasNext()){
              it.remove();
          }
      }
  }
  

  造成這種情況的原因是什麼？細心的同學可能已經發現兩次調用的remove()方法不同，一個帶參數據，一個不帶參數，這個後面再說，經過查看ArrayList源碼，找到了拋出異常的程式碼

  final void checkForComodification() {
        if (modCount != expectedModCount)
        		throw new ConcurrentModificationException();
  }
  

  從上面程式碼中可以看到如果modCount和expectedModCount這兩個變數不相等就會拋出ConcurrentModificationException異常。那這兩個變數又是什麼呢？繼續看源碼

  protected transient int modCount = 0; //在AbstractList中定義的變數
  

  int expectedModCount = modCount;//在ArrayList中的內部類Itr中定義的變數
  

  從上面程式碼可以看到，modCount初始值為0，而expectedModCount初始值等於modCount。也就是說在遍歷的時候直接調用集合的remove()方法會導致modCount不等於expectedModCount進而拋出ConcurrentModificationException異常，而使用迭代器的remove()方法則不會出現這種問題。那麼只能在看看remove()方法的源碼找找原因了

      public E remove(int index) {
          rangeCheck(index);
  
          modCount++;
          E oldValue = elementData(index);
  
          int numMoved = size - index - 1;
          if (numMoved > 0)
              System.arraycopy(elementData, index+1, elementData, index,
                               numMoved);
          elementData[--size] = null; // clear to let GC do its work
  
          return oldValue;
      }
  

  從上面程式碼中可以看到只有modCount++了，而expectedModCount沒有操作，當每一次迭代時，迭代器會比較expectedModCount和modCount的值是否相等，所以在調用remove()方法後，modCount不等於expectedModCount了，這時就了報ConcurrentModificationException異常。但用迭代器中remove()的方法為什麼不拋異常呢？原來迭代器調用的remove()方法和上面的remove()方法不是同一個！迭代器調用的remove()方法長這樣：

          public void remove() {
              if (lastRet < 0)
                  throw new IllegalStateException();
              checkForComodification();
  
              try {
                  ArrayList.this.remove(lastRet);
                  cursor = lastRet;
                  lastRet = -1;
                  expectedModCount = modCount;    //這行程式碼保證了expectedModCount和modCount是相等的
              } catch (IndexOutOfBoundsException ex) {
                  throw new ConcurrentModificationException();
              }
          }
  

  從上面程式碼可以看到expectedModCount = modCount，所以迭代器的remove()方法保證了expectedModCount和modCount是相等的，進而保證了在增強for循環中修改集合內容不會報ConcurrentModificationException異常。

  上面介紹的只是單執行緒的情況，用迭代器調用remove()方法即可正常運行，但如果是多執行緒會怎麼樣呢？

  答案是在多執行緒的情況下即使用了迭代器調用remove()方法，還是會報ConcurrentModificationException異常。這又是為什麼呢？還是要從expectedModCount和modCount這兩個變數入手分析，剛剛說了modCount在AbstractList類中定義，而expectedModCount在ArrayList內部類中定義，所以modCount是個共享變數而expectedModCount是屬於執行緒各自的。簡單說，執行緒1更新了modCount和屬於自己的expectedModCount，而在執行緒2看來只有modCount更新了，expectedModCount並未更新，所以會拋出ConcurrentModificationException異常。

• 安全失敗

  採用安全失敗機制的集合容器，在遍歷時不是直接在集合內容上訪問的，而是先複製原有集合內容，在拷貝的集合上進行遍歷。所以在遍歷過程中對原集合所作的修改並不能被迭代器檢測到，所以不會拋出ConcurrentModificationException異常。缺點是迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發生了修改，迭代器是無法訪問到修改後的內容。java.util.concurrent包下的容器都是安全失敗，可以在多執行緒下並發使用。

如何邊遍歷邊移除 Collection 中的元素？　＊＊＊

從上文「快速失敗機制」可知在遍歷集合時如果直接調用remove()方法會拋出ConcurrentModificationException異常，所以使用迭代器中調用remove()方法。

Array 和 ArrayList 有何區別？　＊＊＊

• Array可以包含基本類型和對象類型，ArrayList只能包含對象類型。
• Array大小是固定的，ArrayList的大小是動態變化的。(ArrayList的擴容是個常見面試題)
• 相比於Array，ArrayList有著更多的內置方法，如addAll()，removeAll()。
• 對於基本類型數據，ArrayList 使用自動裝箱來減少編碼工作量；而當處理固定大小的基本數據類型的時候，這種方式相對比較慢，這時候應該使用Array。

comparable 和 comparator的區別？　＊＊

• comparable介面出自java.lang包，可以理解為一個內比較器，因為實現了Comparable介面的類可以和自己比較，要和其他實現了Comparable介面類比較，可以使用compareTo(Object obj)方法。compareTo方法的返回值是int，有三種情況：
  1. 返回正整數（比較者大於被比較者）
  2. 返回0（比較者等於被比較者）
  3. 返回負整數（比較者小於被比較者）
• comparator介面出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序，返回值同樣是int，有三種情況，和compareTo類似。

它們之間的區別：很多包裝類都實現了comparable介面，像Integer、String等，所以直接調用Collections.sort()直接可以使用。如果對類裡面自帶的自然排序不滿意，而又不能修改其源程式碼的情況下，使用Comparator就比較合適。此外使用Comparator可以避免添加額外的程式碼與我們的目標類耦合，同時可以定義多種排序規則，這一點是Comparable介面沒法做到的，從靈活性和擴展性講Comparator更優，故在面對自定義排序的需求時，可以優先考慮使用Comparator介面。

Collection 和 Collections 有什麼區別？　＊＊

• Collection 是一個集合介面。它提供了對集合對象進行基本操作的通用介面方法。
• Collections 是一個包裝類。它包含有各種有關集合操作的靜態多態方法，例如常用的sort()方法。此類不能實例化，就像一個工具類，服務於Java的Collection框架。

List集合

遍歷一個 List 有哪些不同的方式？　＊＊

先說一下常見的元素在記憶體中的存儲方式，主要有兩種：

1. 順序存儲（Random Access）：相鄰的數據元素在記憶體中的位置也是相鄰的，可以根據元素的位置（如ArrayList中的下表）讀取元素。
2. 鏈式存儲（Sequential Access）：每個數據元素包含它下一個元素的記憶體地址，在記憶體中不要求相鄰。例如LinkedList。

主要的遍歷方式主要有三種：

1. for循環遍歷：遍歷者自己在集合外部維護一個計數器，依次讀取每一個位置的元素。
2. Iterator遍歷：基於順序存儲集合的Iterator可以直接按位置訪問數據。基於鏈式存儲集合的Iterator，需要保存當前遍歷的位置，然後根據當前位置來向前或者向後移動指針。
3. foreach遍歷：foreach 內部也是採用了Iterator 的方式實現，但使用時不需要顯示地聲明Iterator。

那麼對於以上三種遍歷方式應該如何選取呢？

在Java集合框架中，提供了一個RandomAccess介面，該介面沒有方法，只是一個標記。通常用來標記List的實現是否支援RandomAccess。所以在遍歷時，可以先判斷是否支援RandomAccess（list instanceof RandomAccess），如果支援可用 for 循環遍歷，否則建議用Iterator或 foreach 遍歷。

ArrayList的擴容機制　＊＊＊

先說下結論，一般面試時需要記住，ArrayList的初始容量為10，擴容時對是舊的容量值加上舊的容量數值進行右移一位（位運算，相當於除以2，位運算的效率更高），所以每次擴容都是舊的容量的1.5倍。

具體的實現大家可查看下ArrayList的源碼。

ArrayList 和 LinkedList 的區別是什麼？　＊＊＊

• 是否執行緒安全：ArrayList和LinkedList都是不保證執行緒安全的
• 底層實現：ArrayList的底層實現是數組，LinkedList的底層是雙向鏈表。
• 記憶體佔用：ArrayList會存在一定的空間浪費，因為每次擴容都是之前的1.5倍，而LinkedList中的每個元素要存放直接後繼和直接前驅以及數據，所以對於每個元素的存儲都要比ArrayList花費更多的空間。
• 應用場景：ArrayList的底層數據結構是數組，所以在插入和刪除元素時的時間複雜度都會收到位置的影響，平均時間複雜度為o(n)，在讀取元素的時候可以根據下標直接查找到元素，不受位置的影響，平均時間複雜度為o(1)，所以ArrayList更加適用於多讀，少增刪的場景。LinkedList的底層數據結構是雙向鏈表，所以插入和刪除元素不受位置的影響，平均時間複雜度為o(1)，如果是在指定位置插入則是o(n)，因為在插入之前需要先找到該位置，讀取元素的平均時間複雜度為o(n)。所以LinkedList更加適用於多增刪，少讀寫的場景。

ArrayList 和 Vector 的區別是什麼？　＊＊＊

• 相同點

  1. 都實現了List介面
  2. 底層數據結構都是數組

• 不同點

  1. 執行緒安全：Vector使用了Synchronized來實現執行緒同步，所以是執行緒安全的，而ArrayList是執行緒不安全的。
  2. 性能：由於Vector使用了Synchronized進行加鎖，所以性能不如ArrayList。
  3. 擴容：ArrayList和Vector都會根據需要動態的調整容量，但是ArrayList每次擴容為舊容量的1.5倍，而Vector每次擴容為舊容量的2倍。

簡述 ArrayList、Vector、LinkedList 的存儲性能和特性？　＊＊＊

• ArrayList底層數據結構為數組，對元素的讀取速度快，而增刪數據慢，執行緒不安全。
• LinkedList底層為雙向鏈表，對元素的增刪數據快，讀取慢，執行緒不安全。
• Vector的底層數據結構為數組，用Synchronized來保證執行緒安全，性能較差，但執行緒安全。

Set集合

說一下 HashSet 的實現原理　＊＊＊

HashSet的底層是HashMap，默認構造函數是構建一個初始容量為16，負載因子為0.75 的HashMap。HashSet的值存放於HashMap的key上，HashMap的value統一為PRESENT。

HashSet如何檢查重複？（HashSet是如何保證數據不可重複的？）　＊＊＊

這裡面涉及到了HasCode()和equals()兩個方法。

• equals()

  先看下String類中重寫的equals方法。

      public boolean equals(Object anObject) {
          if (this == anObject) {
              return true;
          }
          if (anObject instanceof String) {
              String anotherString = (String)anObject;
              int n = value.length;
              if (n == anotherString.value.length) {
                  char v1[] = value;
                  char v2[] = anotherString.value;
                  int i = 0;
                  while (n-- != 0) {
                      if (v1[i] != v2[i])
                          return false;
                      i++;
                  }
                  return true;
              }
          }
          return false;
      }
  
  

  從源碼中可以看到：

  1. equals方法首先比較的是記憶體地址，如果記憶體地址相同，直接返回true；如果記憶體地址不同，再比較對象的類型，類型不同直接返回false；類型相同，再比較值是否相同；值相同返回true，值不同返回false。總結一下，equals會比較記憶體地址、對象類型、以及值，記憶體地址相同，equals一定返回true；對象類型和值相同，equals方法一定返回true。
  2. 如果沒有重寫equals方法，那麼equals和==的作用相同，比較的是對象的地址值。

• hashCode

  hashCode方法返回對象的散列碼，返回值是int類型的散列碼。散列碼的作用是確定該對象在哈希表中的索引位置。

  關於hashCode有一些約定：

  1. 兩個對象相等，則hashCode一定相同。
  2. 兩個對象有相同的hashCode值，它們不一定相等。
  3. hashCode()方法默認是對堆上的對象產生獨特值，如果沒有重寫hashCode()方法，則該類的兩個對象的hashCode值肯定不同

介紹完equals()方法和hashCode()方法，繼續說下HashSet是如何檢查重複的。

HashSet的特點是存儲元素時無序且唯一，在向HashSet中添加對象時，首相會計算對象的HashCode值來確定對象的存儲位置，如果該位置沒有其他對象，直接將該對象添加到該位置；如果該存儲位置有存儲其他對象（新添加的對象和該存儲位置的對象的HashCode值相同），調用equals方法判斷兩個對象是否相同，如果相同，則添加對象失敗，如果不相同，則會將該對象重新散列到其他位置。

HashSet與HashMap的區別　＊＊＊

Map集合

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實現　＊＊＊

• JDK1.7的底層數據結構(數組+鏈表)

• JDK1.8的底層數據結構(數組+鏈表)

• JDK1.7的Hash函數

  static final int hash(int h){
  	h ^= (h >>> 20) ^ (h >>>12);
      return h^(h >>> 7) ^ (h >>> 4);
  }
  

• JDK1.8的Hash函數

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

  JDK1.8的函數經過了一次異或一次位運算一共兩次擾動，而JDK1.7經過了四次位運算五次異或一共九次擾動。這裡簡單解釋下JDK1.8的hash函數，面試經常問這個，兩次擾動分別是key.hashCode()與key.hashCode()右移16位進行異或。這樣做的目的是，高16位不變，低16位與高16位進行異或操作，進而減少碰撞的發生，高低Bit都參與到Hash的計算。如何不進行擾動處理，因為hash值有32位，直接對數組的長度求余，起作用只是hash值的幾個低位。

HashMap在JDK1.7和JDK1.8中有哪些不同點：

HashMap 的長度為什麼是2的冪次方　＊＊＊

因為HashMap是通過key的hash值來確定存儲的位置，但Hash值的範圍是-2147483648到2147483647，不可能建立一個這麼大的數組來覆蓋所有hash值。所以在計算完hash值後會對數組的長度進行取余操作，如果數組的長度是2的冪次方，(length - 1)&hash等同於hash%length，可以用(length - 1)&hash這種位運算來代替%取余的操作進而提高性能。

HashMap的put方法的具體流程？　＊＊

HashMap的主要流程可以看下面這個流程圖，邏輯非常清晰。

HashMap的擴容操作是怎麼實現的？　＊＊＊

• 初始值為16，負載因子為0.75，閾值為負載因子*容量

• resize()方法是在hashmap中的鍵值對大於閥值時或者初始化時，就調用resize()方法進行擴容。

• 每次擴容，容量都是之前的兩倍

• 擴容時有個判斷e.hash & oldCap是否為零，也就是相當於hash值對數組長度的取余操作，若等於0，則位置不變，若等於1，位置變為原位置加舊容量。

  源碼如下：

  final Node<K,V>[] resize() {
      Node<K,V>[] oldTab = table;
      int oldCap = (oldTab == null) ? 0 : oldTab.length;
      int oldThr = threshold;
      int newCap, newThr = 0;
      if (oldCap > 0) {
          if (oldCap >= MAXIMUM_CAPACITY) { //如果舊容量已經超過最大值，閾值為整數最大值
              threshold = Integer.MAX_VALUE;
              return oldTab;
          }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
              newThr = oldThr << 1;  //沒有超過最大值就變為原來的2倍
      }
      else if (oldThr > 0) 
          newCap = oldThr;
  
      else {               
          newCap = DEFAULT_INITIAL_CAPACITY;
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
      }
  
      if (newThr == 0) {
          float ft = (float)newCap * loadFactor;
          newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
      }
      threshold = newThr;
      @SuppressWarnings({"rawtypes","unchecked"})
          Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
      table = newTab;
      if (oldTab != null) {
          for (int j = 0; j < oldCap; ++j) {
              Node<K,V> e;
              if ((e = oldTab[j]) != null) {
                  oldTab[j] = null;
                  if (e.next == null)
                      newTab[e.hash & (newCap - 1)] = e;
                  else if (e instanceof TreeNode)
                      ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                  else { 
                      Node<K,V> loHead = null, loTail = null;//loHead,loTail 代表擴容後在原位置
                      Node<K,V> hiHead = null, hiTail = null;//hiHead,hiTail 代表擴容後在原位置+舊容量
                      Node<K,V> next;
                      do {             
                          next = e.next;
                          if ((e.hash & oldCap) == 0) { //判斷是否為零，為零賦值到loHead，不為零賦值到hiHead
                              if (loTail == null)
                                  loHead = e;
                              else                                
                                  loTail.next = e;
                              loTail = e;                           
                          }
                          else {
                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;   //loHead放在原位置
                      }
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;  //hiHead放在原位置+舊容量
                      }
                  }
              }
          }
      }
      return newTab;
  }
  
  

HashMap默認載入因子為什麼選擇0.75？

這個主要是考慮空間利用率和查詢成本的一個折中。如果載入因子過高，空間利用率提高，但是會使得哈希衝突的概率增加；如果載入因子過低，會頻繁擴容，哈希衝突概率降低，但是會使得空間利用率變低。具體為什麼是0.75，不是0.74或0.76，這是一個基於數學分析（泊松分布）和行業規定一起得到的一個結論。

為什麼要將鏈表中轉紅黑樹的閾值設為8？為什麼不一開始直接使用紅黑樹？

可能有很多人會問，既然紅黑樹性能這麼好，為什麼不一開始直接使用紅黑樹，而是先用鏈表，鏈表長度大於8時，才轉換為紅紅黑樹。

• 因為紅黑樹的節點所佔的空間是普通鏈表節點的兩倍，但查找的時間複雜度低，所以只有當節點特別多時，紅黑樹的優點才能體現出來。至於為什麼是8，是通過數據分析統計出來的一個結果，鏈表長度到達8的概率是很低的，綜合鏈表和紅黑樹的性能優缺點考慮將大於8的鏈錶轉化為紅黑樹。
• 鏈錶轉化為紅黑樹除了鏈表長度大於8，還要HashMap中的數組長度大於64。也就是如果HashMap長度小於64，鏈表長度大於8是不會轉化為紅黑樹的，而是直接擴容。

HashMap是怎麼解決哈希衝突的？　＊＊＊

哈希衝突：hashMap在存儲元素時會先計算key的hash值來確定存儲位置，因為key的hash值計算最後有個對數組長度取余的操作，所以即使不同的key也可能計算出相同的hash值，這樣就引起了hash衝突。hashMap的底層結構中的鏈表/紅黑樹就是用來解決這個問題的。

HashMap中的哈希衝突解決方式可以主要從三方面考慮（以JDK1.8為背景）

• 拉鏈法

  HasMap中的數據結構為數組+鏈表/紅黑樹，當不同的key計算出的hash值相同時，就用鏈表的形式將Node結點（衝突的key及key對應的value）掛在數組後面。

• hash函數

  key的hash值經過兩次擾動，key的hashCode值與key的hashCode值的右移16位進行異或，然後對數組的長度取余（實際為了提高性能用的是位運算，但目的和取餘一樣），這樣做可以讓hashCode取值出的高位也參與運算，進一步降低hash衝突的概率，使得數據分布更平均。

• 紅黑樹

  在拉鏈法中，如果hash衝突特別嚴重，則會導致數組上掛的鏈表長度過長，性能變差，因此在鏈表長度大於8時，將鏈錶轉化為紅黑樹，可以提高遍歷鏈表的速度。

HashMap為什麼不直接使用hashCode()處理後的哈希值直接作為table的下標？　＊＊＊

hashCode()處理後的哈希值範圍太大，不可能在記憶體建立這麼大的數組。

能否使用任何類作為 Map 的 key？　＊＊＊

可以，但要注意以下兩點：

• 如果類重寫了 equals() 方法，也應該重寫hashCode()方法。
• 最好定義key類是不可變的，這樣key對應的hashCode() 值可以被快取起來，性能更好，這也是為什麼String特別適合作為HashMap的key。

為什麼HashMap中String、Integer這樣的包裝類適合作為Key？　＊＊＊

• 這些包裝類都是final修飾，是不可變性的， 保證了key的不可更改性，不會出現放入和獲取時哈希值不同的情況。
• 它們內部已經重寫過hashcode(),equal()等方法。

如果使用Object作為HashMap的Key，應該怎麼辦呢？　＊＊

• 重寫hashCode()方法，因為需要計算hash值確定存儲位置
• 重寫equals()方法，因為需要保證key的唯一性。

HashMap 多執行緒導致死循環問題　＊＊＊

由於JDK1.7的hashMap遇到hash衝突採用的是頭插法，在多執行緒情況下會存在死循環問題，但JDK1.8已經改成了尾插法，不存在這個問題了。但需要注意的是JDK1.8中的HashMap仍然是不安全的，在多執行緒情況下使用仍然會出現執行緒安全問題。基本上面試時說到這裡既可以了，具體流程用口述是很難說清的，感興趣的可以看這篇文章。HASHMAP的死循環

ConcurrentHashMap 底層具體實現知道嗎？　＊＊

• JDK1.7

  在JDK1.7中，ConcurrentHashMap採用Segment數組 + HashEntry數組的方式進行實現。Segment實現了ReentrantLock，所以Segment有鎖的性質，HashEntry用於存儲鍵值對。一個ConcurrentHashMap包含著一個Segment數組，一個Segment包含著一個HashEntry數組，HashEntry是一個鏈表結構，如果要獲取HashEntry中的元素，要先獲得Segment的鎖。

• JDK1.8

  在JDK1.8中，不在是Segment+HashEntry的結構了，而是和HashMap類似的結構，Node數組+鏈表/紅黑樹，採用CAS+synchronized來保證執行緒安全。當鏈表長度大於8，鏈錶轉化為紅黑樹。在JDK1.8中synchronized只鎖鏈表或紅黑樹的頭節點，是一種相比於segment更為細粒度的鎖，鎖的競爭變小，所以效率更高。

總結一下：

• JDK1.7底層是ReentrantLock+Segment+HashEntry，JDK1.8底層是synchronized+CAS+鏈表/紅黑樹
• JDK1.7採用的是分段鎖，同時鎖住幾個HashEntry，JDK1.8鎖的是Node節點，只要沒有發生哈希衝突，就不會產生鎖的競爭。所以JDK1.8相比於JDK1.7提供了一種粒度更小的鎖，減少了鎖的競爭，提高了ConcurrentHashMap的並發能力。

HashTable的底層實現知道嗎？

HashTable的底層數據結構是數組+鏈表，鏈表主要是為了解決哈希衝突，並且整個數組都是synchronized修飾的，所以HashTable是執行緒安全的，但鎖的粒度太大，鎖的競爭非常激烈，效率很低。

HashMap、ConcurrentHashMap及Hashtable 的區別　＊＊＊

Java集合的常用方法　＊＊

這些常用方法是需要背下來的，雖然面試用不上，但是筆試或者面試寫演算法題時會經常用到。

Collection常用方法

List特有方法

LinkedList特有方法

Map

Stack

Queue