概念：對象的容器鼻疮，定義了對多個(gè)對象進(jìn)行操作的常用方法怒坯】眨可實(shí)現(xiàn)數(shù)組的功能。

整體結(jié)構(gòu)圖

List集合

ArrayList擴(kuò)容機(jī)制

• 當(dāng)new一個(gè)ArrayList時(shí)却邓，實(shí)際是調(diào)用了ArrayList的無參構(gòu)造硕糊，這時(shí)其初始容量為0
• 在添加第一個(gè)元素時(shí)，會將 DEFAULT_CAPACITY 的值作為第一次擴(kuò)容的容量 為10
• 如果再添加元素腊徙，超過了所擴(kuò)容的容量简十，則會進(jìn)入grow()方法 int newCapacity = oldCapacity + (oldCapacity >> 1); 這句代碼進(jìn)行擴(kuò)容，每次都是原來數(shù)組長度的1.5倍 也就是說撬腾，第二次擴(kuò)容后長度為15

//源碼分析：
package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;


public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

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

    /**
     * 空數(shù)組（用于空實(shí)例）螟蝙。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

     //用于默認(rèn)大小空實(shí)例的共享空數(shù)組實(shí)例。
      //我們把它從EMPTY_ELEMENTDATA數(shù)組中區(qū)分出來民傻，以知道在添加第一個(gè)元素時(shí)容量需要增加多少胶逢。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 保存ArrayList數(shù)據(jù)的數(shù)組
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList 所包含的元素個(gè)數(shù)
     */
    private int size;

    /**
     * 帶初始容量參數(shù)的構(gòu)造函數(shù)（用戶可以在創(chuàng)建ArrayList對象時(shí)自己指定集合的初始大小）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //如果傳入的參數(shù)大于0饰潜，創(chuàng)建initialCapacity大小的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果傳入的參數(shù)等于0初坠，創(chuàng)建空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //其他情況，拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     *默認(rèn)無參構(gòu)造函數(shù)
     *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為0.初始化為10彭雾，也就是說初始其實(shí)是空數(shù)組 當(dāng)添加第一個(gè)元素的時(shí)候數(shù)組容量才變成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

Set

image.png

HashSet 如何檢查重復(fù)

• 當(dāng)你把對象加入HashSet時(shí)碟刺，HashSet 會先計(jì)算對象的hashcode值來判斷對象加入的位置，同時(shí)也會與其他加入的對象的 hashcode 值作比較
• 如果沒有相符的 hashcode薯酝，HashSet 會假設(shè)對象沒有重復(fù)出現(xiàn)半沽。
• 但是如果發(fā)現(xiàn)有相同 hashcode 值的對象，這時(shí)會調(diào)用equals()方法來檢查 hashcode 相等的對象是否真的相同吴菠。
• 如果equals()返回true者填，則HashSet 就不會讓加入操作成功。
• 如果equals()返回false做葵，則形成鏈表

Map

image.png

HashMap

類的屬性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列號
    private static final long serialVersionUID = 362498820763181265L;
    // 默認(rèn)的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默認(rèn)的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會轉(zhuǎn)成紅黑樹
    static final int TREEIFY_THRESHOLD = 8;
    // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對應(yīng)的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲元素的數(shù)組占哟，總是2的冪次倍
    transient Node<k,v>[] table;
    // 存放具體元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的個(gè)數(shù)，注意這個(gè)不等于數(shù)組的長度。
    transient int size;
    // 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器
    transient int modCount;
    // 臨界值 當(dāng)實(shí)際大小(容量*填充因子)超過臨界值時(shí)榨乎，會進(jìn)行擴(kuò)容
    int threshold;
    // 加載因子
    final float loadFactor;
}

HashMap的創(chuàng)建過程

• HashMap剛創(chuàng)建時(shí)怎燥，table為null（為了節(jié)省空間），當(dāng)添加第一個(gè)元素的時(shí)候蜜暑，table容量調(diào)整為16
• 當(dāng)元素的個(gè)數(shù)大于閾值（16*0.75=12）時(shí)铐姚，會進(jìn)行擴(kuò)容，擴(kuò)容大小為原來的2倍肛捍。目的是減少調(diào)整元素的個(gè)數(shù)隐绵。
• jdk1.8 當(dāng)鏈表的長度大于8（將鏈表轉(zhuǎn)換成紅黑樹前會判斷，如果當(dāng)前數(shù)組的長度小于 64拙毫，那么會選擇先進(jìn)行數(shù)組擴(kuò)容依许，而不是轉(zhuǎn)換為紅黑樹）時(shí)，會將鏈表轉(zhuǎn)化為紅黑樹恬偷，以減少搜索時(shí)間。
• jdk1.8 當(dāng)鏈表長度小于6時(shí)帘睦，調(diào)整為鏈表
• jdk1.8之前袍患，鏈表為頭插入；jdk1.8之后竣付，鏈表為尾插入

HashMap 和 Hashtable 的區(qū)別

• 線程是否安全： HashMap 是非線程安全的诡延，HashTable 是線程安全的,因?yàn)?HashTable 內(nèi)部的方法基本都經(jīng)過synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧９诺ā）肆良；
• 效率： 因?yàn)榫€程安全的問題，HashMap 要比 HashTable 效率高一點(diǎn)逸绎。另外惹恃，HashTable 基本被淘汰，不要在代碼中使用它棺牧；
• 對 Null key 和 Null value 的支持： HashMap 可以存儲 null 的 key 和 value巫糙，但 null 作為鍵只能有一個(gè)，null 作為值可以有多個(gè)颊乘；HashTable 不允許有 null 鍵和 null 值参淹，否則會拋出 NullPointerException。
• 初始容量大小和每次擴(kuò)充容量大小的不同 ：
  ① 創(chuàng)建時(shí)如果不指定容量初始值乏悄，Hashtable 默認(rèn)的初始大小為 11浙值，之后每次擴(kuò)充，容量變?yōu)樵瓉淼?2n+1檩小。HashMap 默認(rèn)的初始化大小為 16开呐。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?2 倍。
  ② 創(chuàng)建時(shí)如果給定了容量初始值负蚊，那么 Hashtable 會直接使用你給定的大小神妹，而 HashMap 會將其擴(kuò)充為 2 的冪次方大小（HashMap 中的tableSizeFor()方法保證家妆，下面給出了源代碼）鸵荠。也就是說 HashMap 總是使用 2 的冪作為哈希表的大小,后面會介紹到為什么是 2 的冪次方。
• 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較大的變化伤极，當(dāng)鏈表長度大于閾值（默認(rèn)為 8）（將鏈表轉(zhuǎn)換成紅黑樹前會判斷蛹找，如果當(dāng)前數(shù)組的長度小于 64，那么會選擇先進(jìn)行數(shù)組擴(kuò)容哨坪，而不是轉(zhuǎn)換為紅黑樹）時(shí)庸疾，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間当编。Hashtable 沒有這樣的機(jī)制

hashCode()與 equals() 的相關(guān)規(guī)定：

• 如果兩個(gè)對象相等届慈，則 hashcode 一定也是相同的
• 兩個(gè)對象相等,對兩個(gè) equals() 方法返回 true
• 兩個(gè)對象有相同的 hashcode 值，它們也不一定是相等的
• 綜上忿偷，equals() 方法被覆蓋過金顿，則 hashCode() 方法也必須被覆蓋
  hashCode()的默認(rèn)行為是對堆上的對象產(chǎn)生獨(dú)特值。如果沒有重寫 hashCode()鲤桥，則該 class 的兩個(gè)對象無論如何都不會相等（即使這兩個(gè)對象指向相同的數(shù)據(jù)）揍拆。

• 參考文章
  ArrayList 到底是如何進(jìn)行擴(kuò)容的