java集合面試寶典

更多文章請(qǐng)關(guān)注公號(hào)（ID：CodeReading）

簡(jiǎn)介

集合在任何語言都有非常廣泛的應(yīng)用，不同集合底層對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法決定了它的特征，面試中總會(huì)被問到各個(gè)集合之間的區(qū)別和它們的特點(diǎn)，其實(shí)了解底層數(shù)據(jù)結(jié)構(gòu)和算法后這些問題都會(huì)引刃而解，萬變不離其宗。本文嘗試從底層剖析主流集合的底層結(jié)構(gòu)與實(shí)現(xiàn)原理，如無特殊說明，本文源碼出自jdk1.8。

總攬

java集合架構(gòu)圖，來源于網(wǎng)絡(luò)


集合框架.gif

java集合的2個(gè)頂級(jí)接口Collection和Map。


java集合.png

話不多說，接下來我們對(duì)它們作一一介紹。

Map

先對(duì)java.util.Map的4個(gè)常用實(shí)現(xiàn)類做簡(jiǎn)單的介紹及對(duì)比。

HashTable

比較古老，從JDK1.0就開始有了。線程安全，操作時(shí)鎖整個(gè)表，效率低，現(xiàn)在基本被遺棄。

HashMap

毫不謙虛的說，這是最常用的map，也是面試中最常被問到的map。它的特點(diǎn)主要有：

  • 非線程安全，可以用 Collections.synchronizedMap(m)方法使HashMap具有線程安全的能力，或者直接使用ConcurrentHashMap
  • 無序
  • 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹
  • 允許一個(gè)key為null，并把它放在第一個(gè)bucket。允許多個(gè)value為null。
  • 更多內(nèi)容請(qǐng)看之前發(fā)的文章搞定HashMap面試，深入講解HashMap的工作原理
LinkedHashMap

是HashMap子類，同樣是非線程安全，key可以為null，但它有序。LinkedHashMap可以看成是HashMap+LinkedList，使用HashMap操作數(shù)據(jù)結(jié)構(gòu)，用LinkedList維護(hù)插入元素的先后順序。這篇文章對(duì)它講的比較詳細(xì)java集合之LinkedHashMap

TreeMap

有序的map，key不允許是null。其中key必須實(shí)現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator，否則會(huì)在運(yùn)行時(shí)拋出java.lang.ClassCastException類型的異常。數(shù)字類型（Integer、Long、Float、Double、BigDecimal、BigInteger）和String、Date、Boolean等都實(shí)現(xiàn)了Comparable接口。

Set

HashSet
   /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
   
   /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
        // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

從HashSet的構(gòu)造函數(shù)和add() 的源碼可以看出它基于HashMap，值是HashMap的key。這也就不難理解為什么HashSet的值不能重復(fù)，無序了。

LinkedHashSet
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
  
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    
    public LinkedHashSet() {
        super(16, .75f, true);
    }
  
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
}
public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
   HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
}

系HashSet子類，有序。LinkedHashSet所有構(gòu)造方法都調(diào)用父類HashSet(int initialCapacity, float loadFactor, boolean dummy)，初始化了一個(gè)LinkedHashMap，后續(xù)操作也是基于LinkedHashMap。所以它的特點(diǎn)也是基于LinkedHashMap。

TreeSet
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
  
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
  
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

從TreeSet構(gòu)造函數(shù)和add()源碼可以看出，它基于TreeMap，它的值就是TreeMap的key，要求同樣是必須實(shí)現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator，否則會(huì)在運(yùn)行時(shí)拋出java.lang.ClassCastException類型的異常。

List

ArrayList

這是開發(fā)中最常用的數(shù)組，本質(zhì)上就是一個(gè)Object[]。其特點(diǎn)有

  • 有序，可重復(fù)

  • 查詢快，增刪慢

  • 非線程安全

  • 容量，默認(rèn)是10。擴(kuò)容參見源碼grow(int minCapacity)方法。

    （1） public boolean add(E e) {
        //先檢查是否需要擴(kuò)容，再新增元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
  }
（2） private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  }

 （3）private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
  }
 （4）private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        //一般情況下minCapacity =（size+1），size是list.size(),也就是
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 （5）private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新數(shù)組長(zhǎng)度是老數(shù)組長(zhǎng)度+（老數(shù)組長(zhǎng)度除以2）的int值
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
  （6）private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    從源碼中可以清楚的看出擴(kuò)容機(jī)制，很多博主說擴(kuò)容是原來容量的1.5倍，顯然是不嚴(yán)謹(jǐn)?shù)?，甚至是錯(cuò)誤的，比如下面的情況。

    //ArrayList帶初始化容量的構(gòu)造方法，其中elementData是底層Object[]，它的長(zhǎng)度就是ArrayList的容量。而ArrayList.size是ArrayList實(shí)際放了多少個(gè)元素。
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
}

//測(cè)試類
public static void main(String[] args) {
              //ArrayList初始化容量是1
        ArrayList list = new ArrayList(1);
       
        list.add(1);
              //新增第二個(gè)元素的時(shí)候需要擴(kuò)容
        list.add(2);
        Class clazz = list.getClass();
        try {
            Field field = clazz.getDeclaredField("elementData");
            field.setAccessible(true);
            //獲取并打印elementData.length也就是ArrayList容量
            Object[] value = (Object[])field.get(list);
            System.out.println(value.length);
        } catch (Exception e) {
            e.printStackTrace();
        }
  }      
// 最終輸出ArrayList數(shù)組的容量是2，并非1*1.5=3。
// 小紅還測(cè)試了初始容量是2

  • ArrayList批量remove的問題

    public static void main(String[] args) {

        ArrayList<String> list = new ArrayList(Arrays.asList("0","1","2","3","4","5"));
        System.out.println("list:" + list); 
        for (int i = 0; i < list.size(); i++) {
            list.remove(i);
        }
        System.out.println("刪除后list：" + list);
 }       
/**打印結(jié)果
  list:[0, 1, 2, 3, 4, 5]
  刪除后list：[1, 3, 5]
  開始設(shè)想是remove所有元素，但是結(jié)果讓人意外，出現(xiàn)漏刪情況
 */
 //list.remove(i)源碼
 public E remove(int index) {
          //檢查index是否合法
          rangeCheck(index);
          modCount++;
          //要?jiǎng)h除的元素值
          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;
      }
  /**
   上面的for循環(huán)。當(dāng)i=0時(shí)能正常刪除index=0的元素。數(shù)組變?yōu)閇1, 2, 3, 4, 5]
  當(dāng)i=1時(shí)，刪除的是新數(shù)組[1, 2, 3, 4, 5]中index=1的元素，也就是2，所以元素1就被漏掉了。同理[1, 3, 5]都沒被刪除掉。
  這種情況可以用倒敘刪除解決，如下代碼：*/
  
    for (int i = list.size()-1; i>= 0; i--) {
        list.remove(i);
    }

    用傳統(tǒng)的for刪除元素會(huì)出現(xiàn)漏刪，那用foreach呢？

    public static void main(String[] args) {

        ArrayList<String> list = new ArrayList(Arrays.asList("0","1","2","3","4","5"));

        System.out.println("list:" + list);

        for (String s:list) {
            list.remove(s);
        }

        System.out.println("刪除后list：" + list);
    }
//結(jié)果更糟糕，直接拋異常：Exception in thread "main" java.util.ConcurrentModificationException

    foreach，內(nèi)部是用Iterator實(shí)現(xiàn)的，一次循環(huán)完了會(huì)調(diào)用ArrayList內(nèi)部實(shí)現(xiàn)類Itr的next()方法，移至下一個(gè)元素，異常也是出現(xiàn)在這個(gè)地方。

    public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  {
       public boolean remove(Object o) {
          if (o == null) {
              for (int index = 0; index < size; index++)
                  if (elementData[index] == null) {
                      fastRemove(index);
                      return true;
                  }
          } else {
              for (int index = 0; index < size; index++)
                  if (o.equals(elementData[index])) {
                      fastRemove(index);
                      return true;
                  }
          }
          return false;
      }
  
  private void fastRemove(int index) {
          //modCount++ 值已經(jīng)修改
          modCount++;
          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
  }
  //在arraylist內(nèi)部類Itr.next()首先檢查 checkForComodification(),也就是modCount和expectedModCount是否相等。
  //最開始expectedModCount值就是modCount，但在#fastRemove方法中modCount已經(jīng)改變，所以此刻它倆并不相等，所以會(huì)拋出異常     ConcurrentModificationException
    //而用Itr的remove()把expectedModCount = modCount，所以不拋異常。并且會(huì)把刪除的節(jié)點(diǎn)賦值給cursor，當(dāng)遍歷的時(shí)候，也就不會(huì)發(fā)生漏掉的情況。
     private class Itr implements Iterator<E> {
          int cursor;       // index of next element to return
          int lastRet = -1; // index of last element returned; -1 if no such
          int expectedModCount = modCount;
  
          Itr() {}
  
          public boolean hasNext() {
              return cursor != size;
          }
  
          @SuppressWarnings("unchecked")
          public E next() {
              checkForComodification();
              int i = cursor;
              if (i >= size)
                  throw new NoSuchElementException();
              Object[] elementData = ArrayList.this.elementData;
              if (i >= elementData.length)
                  throw new ConcurrentModificationException();
              cursor = i + 1;
              return (E) elementData[lastRet = i];
          }
              final void checkForComodification() {
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
          }
          //Iterator的remove()
          public void remove() {
              if (lastRet < 0)
                  throw new IllegalStateException();
              checkForComodification();
  
              try {
                  ArrayList.this.remove(lastRet);
                  cursor = lastRet;
                  lastRet = -1;
                  //關(guān)鍵步驟設(shè)置expectedModCount = modCount
                  expectedModCount = modCount;
              } catch (IndexOutOfBoundsException ex) {
                  throw new ConcurrentModificationException();
              }
          }
     }
  }

    總結(jié)：

    1. 普通for循環(huán)i++方式remove元素會(huì)出現(xiàn)漏刪，修改為i--的方式
    2. 用foreach操作remove，add都會(huì)拋 java.util.ConcurrentModificationException。修改為用Iterator方式刪除。
Vector

底層也是Object[]，特點(diǎn)有

  • 有序，可重復(fù)

  • 查詢快，增刪慢

  • 線程安全

  • 擴(kuò)容 , 同樣說Vector擴(kuò)容是原來的2倍并不嚴(yán)謹(jǐn)。

        /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.
     * 初始化容量是10，capacity increment 數(shù)組容量的增量是0。
     */
    public Vector() {
        this(10);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //如果是通過不帶參數(shù)的構(gòu)造方法構(gòu)造的Vector，capacityIncrement=0
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
LinkedList

ArrayList和Vector底層結(jié)構(gòu)是數(shù)組，LinkedList是雙向鏈表，其主要特點(diǎn)是

  • 有序
  • 查詢相對(duì)慢，新增相對(duì)快
  • 非線程安全

集合排序

集合實(shí)現(xiàn)排序除了本身具有順序（如LinkedList）的集合外，還有輔助工具可以實(shí)現(xiàn)集合排序。

Comparable & Comparator

java集合要實(shí)現(xiàn)自定義排序的2個(gè)途徑

  1. 一般要實(shí)現(xiàn)java.lang.Comparable接口，重寫compareTo(o)方法。適用于本實(shí)例和其他對(duì)象比較，內(nèi)置比較/排序功能。支持排序的集合中的元素必須實(shí)現(xiàn)它。
  2. 使用java.util.Comparator接口，既然在util包里，本質(zhì)是一個(gè)工具類，里面提供了很多排序的方法。當(dāng)集合中元素沒實(shí)現(xiàn)Comparable接口或者Comparable接口不能滿足需求時(shí)，可以用Comparator實(shí)現(xiàn)排序。
排序工具

  • Collections

    通過Collections進(jìn)行自動(dòng)排序，正序、倒序、亂序。

Collections#
//正序 實(shí)現(xiàn)Comparable接口的排序
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }
//使用Comparator實(shí)現(xiàn)排序
public static <T> void sort(List<T> list, Comparator<? super T> c) {
        list.sort(c);
}    
//倒序
public static void reverse(List<?> list){...}
//亂序,每次執(zhí)行的順序不一樣
public static void shuffle(List<?> list){...}
  • java8 Stream 排序
List<User> list = new ArrayList();
list.stream().sorted(Comparator.comparing(User::getName));
  • list.sort
List<User> list = new ArrayList();
list.sort(Comparator.comparing(User::getName));
//注意list.sort是interface List的方法實(shí)現(xiàn)。java8開始運(yùn)行接口方法可以有方法體。

  • Arrays

    //Arrays排序
public static <T> void sort(T[] a, Comparator<? super T> c){...}

集合里為什么設(shè)計(jì)出迭代器

集合遍歷是比較常用的操作，每類集合遍歷的方式各不相同，list和set的遍歷顯然不同，但它們又都屬于集合。有沒有一種不關(guān)心具體集合類型就可以遍歷的方式呢？答案就是迭代器。只要實(shí)現(xiàn)了Iterator接口就可以用統(tǒng)一的遍歷方式?？偨Y(jié)一下用Iterator的優(yōu)點(diǎn)

  1. 不了解集合內(nèi)部結(jié)構(gòu)也可以遍歷
  2. 適用性強(qiáng)，實(shí)現(xiàn)了Iterator接口的類都可以用統(tǒng)一的遍歷方式
  3. 符合開閉原則，當(dāng)集合類型變更時(shí)不需要重寫遍歷方式
  4. Iterator的remove方法是安全的，在上文的Arraylist#remove有詳細(xì)說明。

總結(jié)

本文從集合的源碼級(jí)別分析了它們各自特點(diǎn)和彼此之間的區(qū)別。個(gè)人能力有限，水平一般，難免會(huì)有一些謬誤，還請(qǐng)各位體諒。原創(chuàng)不易，歡迎點(diǎn)贊轉(zhuǎn)發(fā)。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容