原文：JavaGuide

2.2 Java 集合

1.List蜂桶、Set荷并、Map 三者的區(qū)別

• List：有序那先、不唯一
• Set: 不允許重復(fù)，無序
• Map：K-V鍵值對渗柿，Key不能重復(fù)

2.ArrayList VS LinkedList

補充： RandomAccess 接口是一個標(biāo)識接口仅炊。標(biāo)識實現(xiàn)這個接口的類具有隨機訪問的功能贿堰。

list 遍歷方式選擇：

• 實現(xiàn)了RandomAccess 接口的list包颁，優(yōu)先選擇普通for循環(huán)，其次是foreach.
• 未實現(xiàn)RandomAccess 接口的list胞枕，優(yōu)先選擇iterator 遍歷杆煞。大size的數(shù)據(jù)，千萬不要使用普通的for循環(huán)腐泻。（foreach 遍歷底層也是通過iterator實現(xiàn)的）

補充：雙向鏈表 VS 雙向循環(huán)鏈表

• 雙向鏈表：包含兩個指針决乎，prev 指向前一個節(jié)點，next指針指向后一個節(jié)點

  
  
  image.png

• 雙向循環(huán)鏈表：在雙向鏈表的基礎(chǔ)上派桩，最后一個節(jié)點的next指向head构诚，而head的prev指向最后一個節(jié)點，構(gòu)成一個環(huán)铆惑。

  
  
  image.png

3.ArrayList VS Vector范嘱， 為什么要用ArrayList 取代 Vector

Vector 類的所有方法都是同步的，線程安全但是不高效员魏。
ArrayList 不是同步的丑蛤，不需要保證線程安全的時候建議使用ArrayList。

4. ArrayList 的擴容機制

ArrayList 三種初始化方式：

   /**
     * 默認(rèn)初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;
    

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *默認(rèn)構(gòu)造函數(shù)撕阎，使用初始容量10構(gòu)造一個空列表(無參數(shù)構(gòu)造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 帶初始容量參數(shù)的構(gòu)造函數(shù)受裹。（用戶自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //創(chuàng)建initialCapacity大小的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //創(chuàng)建空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0，拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *構(gòu)造包含指定collection元素的列表虏束，這些元素利用該集合的迭代器按順序返回
    *如果指定的集合為null棉饶，throws NullPointerException脑慧。 
    */
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

調(diào)用無參構(gòu)造方法來創(chuàng)建ArrayList時，實際上初始化賦值的是一個空數(shù)組砰盐。當(dāng)真正往數(shù)組添加元素時，才真正分配容量坑律，擴展為10.

ArrayList 擴容機制

1.add 方法

    /**
     * 將指定的元素追加到此列表的末尾岩梳。 
     */
    public boolean add(E e) {
   //添加元素之前，先調(diào)用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //這里看到ArrayList添加元素的實質(zhì)就相當(dāng)于為數(shù)組賦值
        elementData[size++] = e;
        return true;
    }

2. ensureCapacityInternal() 方法

   //得到最小擴容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 獲取默認(rèn)的容量和傳入?yún)?shù)的較大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

當(dāng) 要 add 第1個元素時晃择，minCapacity為1冀值，在Math.max()方法比較后，minCapacity 為10宫屠。

3.ensureExplicitCapacity() 方法

  //判斷是否需要擴容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //調(diào)用grow方法進(jìn)行擴容列疗，調(diào)用此方法代表已經(jīng)開始擴容了
            grow(minCapacity);
    }

我們來仔細(xì)分析一下：

• 當(dāng)我們要 add 進(jìn)第1個元素到 ArrayList 時，elementData.length 為0 （因為還是一個空的 list）浪蹂，因為執(zhí)行了 ensureCapacityInternal() 方法 抵栈，所以 minCapacity 此時為10。此時坤次，minCapacity - elementData.length > 0 成立古劲，所以會進(jìn)入 grow(minCapacity) 方法。
• 當(dāng)add第2個元素時缰猴，minCapacity 為2产艾，此時e lementData.length(容量)在添加第一個元素后擴容成 10 了。此時滑绒，minCapacity - elementData.length > 0 不成立闷堡，所以不會進(jìn)入 （執(zhí)行）grow(minCapacity) 方法。
• 添加第3疑故、4···到第10個元素時杠览，依然不會執(zhí)行g(shù)row方法，數(shù)組容量都為10焰扳。
• 直到添加第11個元素倦零，minCapacity(為11)比elementData.length（為10）要大。進(jìn)入grow方法進(jìn)行擴容吨悍。

4.grow()

    /**
     * 要分配的最大數(shù)組大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList擴容的核心方法扫茅。
     */
    private void grow(int minCapacity) {
        // oldCapacity為舊容量，newCapacity為新容量
        int oldCapacity = elementData.length;
        //將oldCapacity 右移一位育瓜，其效果相當(dāng)于oldCapacity /2葫隙，
        //我們知道位運算的速度遠(yuǎn)遠(yuǎn)快于整除運算，整句運算式的結(jié)果就是將新容量更新為舊容量的1.5倍躏仇，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后檢查新容量是否大于最小需要容量恋脚，若還是小于最小需要容量腺办，那么就把最小需要容量當(dāng)作數(shù)組的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE糟描，
       //如果minCapacity大于最大容量怀喉，則新容量則為`Integer.MAX_VALUE`，否則船响，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`躬拢。
        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);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),
所以 ArrayList 每次擴容之后容量都會變?yōu)樵瓉淼?1.5 倍左右（oldCapacity為偶數(shù)就是1.5倍，否則是1.5倍左右）见间！ 奇偶不同聊闯，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇數(shù)的話會丟掉小數(shù).

5.hugeCapacity() 方法米诉。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //對minCapacity和MAX_ARRAY_SIZE進(jìn)行比較
        //若minCapacity大菱蔬，將Integer.MAX_VALUE作為新數(shù)組的大小
        //若MAX_ARRAY_SIZE大，將MAX_ARRAY_SIZE作為新數(shù)組的大小
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

補充

這里補充一點比較重要史侣，但是容易被忽視掉的知識點：

• java 中的 length 屬性是針對數(shù)組說的,比如說你聲明了一個數(shù)組,想知道這個數(shù)組的長度則用到了 length 這個屬性.
• java 中的 length() 方法是針對字符串說的,如果想看這個字符串的長度則用到 length() 這個方法.
• java 中的 size() 方法是針對泛型集合說的,如果想看這個泛型有多少個元素,就調(diào)用此方法來查看!

System.arraycopy() 和 Arrays.copyOf()方法

• add(int index, E element)用到了System.arraycopy()方法

    /**
     * 在此列表中的指定位置插入指定的元素拴泌。 
     *先調(diào)用 rangeCheckForAdd 對index進(jìn)行界限檢查；然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大惊橱；
     *再將從index開始之后的所有成員后移一個位置弛针；將element插入index位置；最后size加1李皇。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法實現(xiàn)數(shù)組自己復(fù)制自己
        //elementData:源數(shù)組;index:源數(shù)組中的起始位置;elementData：目標(biāo)數(shù)組削茁；index + 1：目標(biāo)數(shù)組中的起始位置； size - index：要復(fù)制的數(shù)組元素的數(shù)量掉房；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

• toArray() 方法用到了 Arrays.copyOf()

/**
     以正確的順序返回一個包含此列表中所有元素的數(shù)組（從第一個到最后一個元素）; 返回的數(shù)組的運行時類型是指定數(shù)組的運行時類型茧跋。 
     */
    public Object[] toArray() {
    //elementData：要復(fù)制的數(shù)組；size：要復(fù)制的長度
        return Arrays.copyOf(elementData, size);
    }

ArrayList.copyOf() 內(nèi)部實際調(diào)用的也是 System.arraycopy() 方法卓囚。

ensureCapacity方法

ensureCapacity方法沒有在ArrayList 內(nèi)部調(diào)用過瘾杭，是提供給用戶調(diào)用的，這樣就可以提前根據(jù)用戶所需數(shù)組的大小初始化哪亿，以減少增量重新分配的次數(shù)粥烁。

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}

向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，以減少增量重新分配的次數(shù)蝇棉。

5. HashMap VS HashTable

6. HashMap VS HashSet

HashSet 底層是基于HashMap實現(xiàn)的耳标。

7. HashSet 如何檢查重復(fù)

當(dāng)把對象加入HashSet時次坡，會先計算對象的hashcode來判斷對象加入的位置纲仍，同時也會和其他已加入的對象的hashcode做比較，如果沒有相符的hashcode贸毕，則說明沒有重復(fù)對象。如果發(fā)現(xiàn)相同的hashcode夜赵，就會調(diào)用equals()判斷對象是否真的相等明棍。

hashCode() 和 equals() 的規(guī)定：

• 1.如果兩個對象相等，則hashcode一定也是相同的寇僧；
• 2.如果兩個對象相等摊腋，則equals() 比較結(jié)果為true；
• 3.如果兩個對象的hashcode相等嘁傀，但這兩個對象不一定是相等的兴蒸；
• 4.綜上，equals() 方法被重寫细办，則 hashCode() 也必須被重寫橙凳；
• 5. hashCode() 默認(rèn)是對堆上的對象產(chǎn)生獨特值。如果沒有重寫hashCode(), 即使兩個對象的內(nèi)容一樣笑撞，也不會相等岛啸。

8. HashMap 底層實現(xiàn)

JDK 1.8 之前

JDK1.8之前，HashMap的底層是數(shù)組+鏈表茴肥，也就是鏈表散列坚踩。HashMap通過key的hashcode 經(jīng)過擾動函數(shù)處理過后得到hash值，然后通過(n-1)&hash判斷當(dāng)前元素存放的位置瓤狐。如果當(dāng)前位置存在元素瞬铸，就比較hash值和key是否相同，如果相同础锐，直接覆蓋嗓节；如果不相同，通過拉鏈法解決沖突皆警。
擾動函數(shù)可以減少沖突的發(fā)生赦政。
JDK1.8 的hash方法：

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

JDK1.7 的hash方法：

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

相比于JDK1.8的hash方法，JDK1.7的hash方法性能稍差一點，畢竟擾動了4次恢着。

JDK 1.8 之后

當(dāng)鏈表長度大于閾值（默認(rèn)是8）時桐愉，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間掰派。

image.png

TreeMap从诲、TreeSet 以及 JDK1.8 之后的HashMap 底層都用到了紅黑樹。主要是為了解決二叉查找樹某些情況會退化成一個線性結(jié)構(gòu)靡羡。

9. HashMap 的長度為什么是 2 的冪次方

讓HashMap 存取高效系洛，盡量減少碰撞，把數(shù)據(jù)分配均勻略步。
Hash 值的范圍是 -2147483684~2147483647描扯，總共40億個映射空間。內(nèi)存是放不下一個40億長度的數(shù)組的趟薄，所有需要對長度取模運算绽诚。取模的% 方法太慢，并且當(dāng)除數(shù)是2的冪次方時杭煎，滿足 hash%length==hash&(length-1)恩够，所以快速方法是：(n - 1) & hash,所以長度要求是2的冪次方。

10. HashMap 多線程操作導(dǎo)致死循環(huán)

主要原因是并發(fā)下 ReHash 會造成元素之間形成一個循環(huán)鏈表羡铲。JDK1.8 已修復(fù)蜂桶，但并發(fā)下還是會存在其他問題，例如數(shù)據(jù)丟失也切，所以并發(fā)環(huán)境下推薦使用 ConcurrentHashMap扑媚。
參考:https://coolshell.cn/articles/9606.html

11. ConcurrentHashMap VS HashTable

ConcurrentHashMap 和 HashTable 的區(qū)別主要體現(xiàn)在實現(xiàn)線程安全的方式上不同。

• 底層數(shù)據(jù)結(jié)構(gòu)：JDK1.7的ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表雷恃。 JDK1.8 采用 數(shù)組+鏈表/紅黑樹钦购。
• 實現(xiàn)線程安全的方式：JDK1.7 ConcurrentHashMap（分段鎖）對整個桶數(shù)組進(jìn)行了分割分段，每一把鎖只鎖容器中其中一部分?jǐn)?shù)據(jù)褂萧。多線程訪問容器里不同數(shù)據(jù)段就不會產(chǎn)生鎖競爭押桃，提高并發(fā)訪問率。 JDK1.7 時ConcurrentHashMap 摒棄分段鎖Segment概念导犹，而是直接用Node數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)唱凯，并發(fā)控制使用synchronized和 CAS 來操作。（JDK1.6 以后對 synchronized鎖做了很多優(yōu)化）整個看起來就像是優(yōu)化過且線程安全的HashMap谎痢， 雖然在JDK1.8 還能看到Segment的數(shù)據(jù)結(jié)構(gòu)磕昼，但是已經(jīng)簡化了屬性，只是為了兼容舊版本节猿。 HashTable(同一把鎖)： 使用synchronized來保證線程安全票从，效率非常低下漫雕。但多個線程訪問同步方法時，會進(jìn)入阻塞或輪詢狀態(tài)峰鄙，如果一個線程使用put添加元素浸间，另一個線程不能使用put，也不能使用get吟榴。

參考:ConcurrentHashMap實現(xiàn)原理及源碼分析

image.png

JDK1.7?ConcurrentHashMap?A

12. ConcurrentHashMap 線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)

• JDK1.7 ConcurrentHashMap
  首先將數(shù)據(jù)分為一段一段的存儲魁蒜，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)時吩翻，其他段的數(shù)據(jù)也能被其他線程訪問兜看。

static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
        // 數(shù)據(jù)節(jié)點存儲在這里(基礎(chǔ)單元是數(shù)組)
        transient volatile HashEntry<K,V>[] table;
        transient int count;
        transient int modCount;
        transient int threshold;
        final float loadFactor;
}

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
}

image.png

• JDK1.8 ConcurrentHashMap
  ConcurrentHashMap 取消了分段鎖 Segment，采用了CAS 和 synchronized 來保證并發(fā)安全狭瞎。數(shù)據(jù)結(jié)構(gòu)與HashMap 1.8 結(jié)構(gòu)類似细移，數(shù)組+鏈表/紅黑樹。 Java 8 在鏈表長度超過一定閾值（8）時熊锭，將鏈表(尋址時間復(fù)雜度O(N))轉(zhuǎn)換為紅黑樹(O(log(N))）
  synchronized 只鎖定當(dāng)前鏈表或紅黑樹的首節(jié)點弧轧，這樣只要hash不沖突，就不會阻塞球涛，效率提高N倍。

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246763182397L;

//...

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        // ...
    }

    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

 public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
}

13. comparable VS comparator

• comparable：接口實際上是出自java.lang包校镐，它有一個compareTo(Object obj) 的方法用來排序
• comparator：接口實際是出自java.util包亿扁，它有一個compare(Object obj1, Object obj2) 方法用來排序。

Collections.sort(arrayList, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
          return o2.compareTo(o1);
      }
});

public class Person implements Comparable<Person> {
      // ...
     @Override
     public int compareTo(Person o) {
          if(this.age > o.getAge()) {
              return 1;
          } else if (this.age < o.getAge()) {
              return -1;
          }
          return age;
     } 
}

14. 集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

Collection

1.List

• ArrayList：Object 數(shù)組
• Vector： Object 數(shù)組
• LinkedList：雙向鏈表（JDK1.6為循環(huán)鏈表鸟廓，JDK1.7取消循環(huán)）

2.Set

• HashSet（無序从祝，唯一）：基于HashMap 實現(xiàn)，底層采用HashMap來保存元素
• LinkedHashSet： LinkedHashSet 繼承于HashSet引谜，內(nèi)部是通過LinkedHashMap來實現(xiàn)的牍陌。
• TreeSet（有序，唯一）：紅黑樹

3.Map

• HashMap：JDK1.7 數(shù)組+鏈表员咽， JDK1.8 數(shù)組+鏈表/紅黑樹(8)
• LinkedHashMap：LinkedHashMap 繼承自HashMap毒涧，在數(shù)組+鏈表/紅黑樹的基礎(chǔ)上，增加了一條雙向鏈表贝室。
• HashTable：數(shù)組+鏈表
• TreeMap：紅黑樹

15. 如何選用集合

• 鍵值對 => Map 接口
  • 排序 => TreeMap
  • 不需要排序 => HashMap
  • 線程安全 => ConcurrentHashMap
• 存放 => Collection
  • 唯一 => Set(TreeSet/HashSet)
  • 不唯一 => ArrayList/LinkedList

16. 補充：Collection 和 Collections 的區(qū)別

Collection 接口

java.util.Colletion
是集合框架的父接口契讲，提供了集合對象基本操作的通用接口方法。Collection 存在的意義就是為各種具體的集合提供了最大化的統(tǒng)一操作方式滑频。

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

Collections 工具類

java.util.Collections
是一個包裝類捡偏，包含各種有關(guān)集合操作的靜態(tài)多態(tài)方法。此類不能實例化峡迷，就像一個工具類银伟，服務(wù)于Java的Colletion 框架。提供一系列靜態(tài)方法實現(xiàn)對各種集合的搜索、排序彤避、線程安全化等操作傅物。

• 1. 排序 Collections.sort(list)

        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.sort(list);
        // [1, 3, 3, 4, 4, 5, 6, 7, 33, 544]
        System.out.println(list.toString());

• 2.隨機排序 Collections.shuffle(list)

    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.shuffle(list);
        // [6, 3, 3, 7, 4, 5, 544, 1, 4, 33]
        System.out.println(list.toString());
    }

• 3. 反轉(zhuǎn) Collections.reverse(list)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.sort(list);
        // [1, 3, 3, 4, 4, 5, 6, 7, 33, 544]
        System.out.println(list.toString());
        Collections.reverse(list);
        [544, 33, 7, 6, 5, 4, 4, 3, 3, 1]
        System.out.println(list.toString());
    }
}

• 4. 替換所有元素 Collections.fill(list, 0)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.fill(list, 3);
        // [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
        System.out.println(list.toString());
    }
}

• 5. 拷貝 Collections.copy(newList, list)

public class Test {
    public static void main(String[] args) {
        List<Integer> list =  new ArrayList();
        list.add(1);
        list.add(3);
        List<Integer> newList = new ArrayList();
        newList.add(4);
        newList.add(5);
        //newList 長度要求大于等于 list
        Collections.copy(newList, list);
        System.out.println(list.toString());  //[1, 3]
        System.out.println(newList.toString()); //[1, 3]
    }
}

• 6. 最大/小元素 Collections.min(list) / Collections.max(list)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List<Integer> list =  Arrays.asList(nums);
        System.out.println(Collections.min(list));  // 1
        System.out.println(Collections.max(list)); // 544
    }
}

• 7. 源列表中第一次/最后一次出現(xiàn)目標(biāo)列表的起始位置

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,3,6,544,33};
        Integer temp[] = {3,6};
        List<Integer> list = Arrays.asList(nums);
        List<Integer> dest = Arrays.asList(temp);
        System.out.println(Collections.indexOfSubList(list,dest));  // 4
        System.out.println(Collections.lastIndexOfSubList(list, dest)); // 8
    }
}

• 8. 循環(huán)移動列表中的元素 Collections.rotate(list,4)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        Collections.rotate(list,4); // 右移 4 位
        System.out.println(list.toString()); // [3, 6, 544, 33, 1, 4, 5, 7, 3, 6, 3, 4]
        Collections.rotate(list,-2); // 左移 2 位
        System.out.println(list.toString()); // [544, 33, 1, 4, 5, 7, 3, 6, 3, 4, 3, 6]
    }
}

17. 補充：5 種方法輸出 List

• 1. 直接輸出list（要求是Java 已有的類）

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List list = Arrays.asList(nums);
        System.out.println(list.toString()); // [1, 4, 5, 7, 3, 6, 544, 33]
    }
}

• 2. 增強for循環(huán)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        for(Integer i : list) {
            System.out.println(i);
        }
    }
}

• 3. 下標(biāo)for 循環(huán)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

• 4. iterator 遍歷

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        Iterator iterator = list.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

• 5. Java 8 Lambda 表達(dá)式

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        list.forEach(item -> System.out.println(item));
    }
}

• 6. Java 8 ForEach

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        list.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });
    }
}

18. 補充：3種方法打印一維數(shù)組

定義一個數(shù)組：

int[] nums = {1,2,3,4}

• 1. 下標(biāo)for循環(huán)

for(int i = 0; i < nums.length; i++) {
    System.out.println(nums[i]);
}

• 2. 增強for循環(huán)

for(int a : nums){
    System.out.println(a);
}

• 3. Arrays.toString(int[] nums)

System.out.println(Arrays.toString(nums)); // [1,2,3,4]
System.out.println(nums); // 這樣打印出來的是數(shù)組的首地址

19. 補充：3種方法打印二維數(shù)組

Java 實際沒有二維數(shù)組的概念，只有一維數(shù)組忠藤。多維數(shù)組被解讀為“數(shù)組的數(shù)組”挟伙。所以對二維數(shù)組的操作也是將多維拆解為一維數(shù)組，然后進(jìn)行操作模孩。

int[][] matrix = {
  {1,2,3},
  {4,5,6}
};

這里 matrix.length = 2; matrix[0].length = 3;

• 1.下標(biāo)for循環(huán)

for(int i =0; i < matrix.length; i++) {
    for(int j = 0; j < matrix[i].length; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

• 2.增強for循環(huán)

for(int[] arr : matrix) {
    for(int num : arr) {
        System.out.print(num + " ");
    }
    System.out.println();
}

• 3.Arrays.toString()

for(int i = 0; i < matrix.length; i++) {
    Systen.out.println(Arrays.toString(matrix[i]));
}