對java集合相關(guān)的一些基礎(chǔ)總結(jié)定枷，具體每個類可以通過IDE查看源碼，這里會借助一些源碼來說明，但是不進行源碼全面分析

注：源碼基于jdk1.8版本

HashMap
HashMap是平時很常用的，也是各公司面試筆試都會涉及到的
平時使用的時候大概是這樣的

Map myMap = new HashMap();

用的多鸟整，其基本構(gòu)造，我們應(yīng)該了解一下川慌。
下面我們對HashMap結(jié)合源碼進行一個簡單的分析吃嘿，如果不想看分析過程，可以拉到最下面查看總結(jié)梦重。

HashMap類的聲明是這樣的

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap的大致結(jié)構(gòu)是這樣的

HashMap大致結(jié)構(gòu).png

（手繪的兑燥，粗糙了些，見諒）
大致就是這個樣子
縱向的是一個類似于數(shù)組的結(jié)構(gòu)琴拧，橫向的類似于鏈表
縱向的每一個降瞳，1,2,3,4,5等等，這個有個名稱bucket 一般翻譯為桶

HashMap容量和擴容

1. 默認創(chuàng)建的HashMap的大小是16蚓胸，就是說上面那個圖在默認情況下挣饥，縱向有16個格子（16個桶）。在源碼中是這樣定義的

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

其中的1<<4指的是二進制的1沛膳，往左邊移動4位扔枫，移過的地方補0，1就變成了二進制的10000锹安，這個就是十進制的16
如果是1被左移的話短荐，可以理解為2^n倚舀，就是2的多少次方

在創(chuàng)建的時候，我們可以給構(gòu)造函數(shù)傳入一個大小忍宋，來指定HashMap的初始大小

Map myMap = new HashMap(30);

我們這里傳入的是30痕貌，是不是就是有30個桶的HashMap呢?
不是。
跟著源碼過去看看糠排，對傳入的容量大小舵稠，有個計算過程：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

其中的n>>>1表示將n的二進制數(shù)，右移1位入宦，高位補0哺徊，比如 n=5，二進制就是0101, 5>>>1之后是0010
n |= n>>>1 就是 n = n|(n>>>1)
其中的 |乾闰，與運算符唉工，也是二進制層面的，計算規(guī)則就是
1|0 = 1
1|1 = 1
0|0 = 0
依然用n=5舉例汹忠，我們來計算 n |= n>>>1
首先5的二進制數(shù)字是101， 5>>>1=0010
那么101|10是多少呢雹熬，按位與：
101
010
結(jié)果 111
按位與的結(jié)果是 111
好了宽菜，有了這個計算基礎(chǔ)，可以自行舉例通過上面的算法計算出的結(jié)果
這個算法的作用就是找到大于等于傳進去的容量數(shù)值的最小的2的冪
什么意思呢
比如你輸入的是30竿报，那么大于等于30的最小的2的冪是2^5,32
所以铅乡，輸入進去的容量，不一定是最終HashMap的容量
然后烈菌，最大容量：

static final int MAXIMUM_CAPACITY = 1 << 30;

2. 在這類集合類型的類中阵幸，有一個概念，負載因子芽世，HashMap的負載因子默認為0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

意思就是挚赊，16*0.75 = 12，在有12個桶裝了東西之后济瓢，就需要擴容沃粗，這里涉及兩個問題壁榕，第一，擴容的時機，第二督函，擴容的機制

首先，擴容的時機对供，不同的版本逾苫，時機不同，可以從put源碼里看到柬帕，具體代碼不貼了哟忍，有IDE的同學順手就能找到狡门。
在jdk1.8里面，put 調(diào)用的是 putVal魁索，這個方法最后融撞，在將元素添加完成后，有一個操作

        if (++size > threshold)
            resize();

這里的 threshold 不是上面我們計算出來的實際容量粗蔚，是putVal剛開始的resize()方法中乘以負載因子的一個容量
實際意思就是尝偎，每次put執(zhí)行之后，會對當前size增加1鹏控，然后和 容量*負載因子 進行比較致扯，提前進行擴容操作
然后，在jdk1.7里面当辐，擴容是在每次往里put之前執(zhí)行的抖僵，源碼我們下面講解put的時候回分析。
所以缘揪，如果有面試官提問耍群，HashMap的擴容時機，有可能是挖了一個坑找筝，看你對版本變更是否熟悉蹈垢。

然后，擴容的機制袖裕，在resize()中曹抬，主要就是一句

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold

newCap = oldCap << 1 這個就是計算新的容量，<<1急鳄，左移1位谤民，就是乘以2的意思。
新的容量是舊容量的兩倍疾宏。

上面講的都是桶的擴容张足，比如默認是16個桶，負載因子是0.75灾锯，有12個桶裝了東西之后兢榨，就會觸發(fā)擴容，單個桶里裝了多少顺饮，不計算在內(nèi)吵聪。

HashMap添加數(shù)據(jù)
不確定是從哪個版本開始，HashMap的初始化是在第一次put的時候才進行兼雄，在沒有put數(shù)據(jù)的時候吟逝，沒有進行初始化，以此節(jié)約內(nèi)存赦肋。
簡單分析一下添加數(shù)據(jù)的過程

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

我們put了k v之后块攒，實際調(diào)用了putVal(hash(key), key, value, false, true)励稳，第一個參數(shù)就是hash(key)，這個是計算key的hash值

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

整個計算過程囱井，沒有興趣的話不用深究驹尼，但從這里至少可以看出，HashMap是可以接受 key為null 的庞呕，這個是HashMap的特性之一新翎。
如果key為null，那么它的hash值就是0住练，如果key不為null地啰，那么通過后邊的算法給計算一個出來。
接下來就是putVal的源碼讲逛，在1.8里亏吝，這個代碼寫的有點復雜，看著頭疼盏混，我們可以回頭去看看1.7里面的put過程蔚鸥，1.8只是進行了一些優(yōu)化，大致過程沒有變许赃。
下面是jdk1.7里面的put的源碼株茶。

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

這個代碼看著就親切多了。图焰。。
部分同學可能不喜歡加注解的分析方式蹦掐，所以這里我就分開一段一段的解析技羔。

        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

這一段就是判斷整個HashMap是否為空，如果為空卧抗，則初始化

 if (key == null)
            return putForNullKey(value);

HashMap允許key為null藤滥，那么key是null的時候，直接調(diào)用 putForNullKey 處理

private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

從這里可以看出來社裆，key為null的話拙绊，直接存入table[0]，如果已經(jīng)有一個key為null的值存在了泳秀，那么替換掉原來的value标沪，將新的value放進去。

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

這一段是查找是否已經(jīng)有一個相同的key存在了
比較兩個key是否相同的過程嗜傅，可以關(guān)注一下

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 

第一金句，hash值必須相等，hash怎么算出來的吕嘀，可以自己去看看代碼
第二违寞，key值相等贞瞒，或者equal
滿足這兩個條件，就認為是相同的key趁曼，用新的value军浆，替換舊的value。

最后挡闰，對于新的值乒融，使用

 addEntry(hash, key, value, i);

這種方式插入進去，這個方法的源碼

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

可以看到尿这，在jdk1.7版本里簇抵，擴容是在添加新數(shù)據(jù)的時候發(fā)生的，原容量x2進行擴容
然后 createEntry就是創(chuàng)建一個新的節(jié)點

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

從源碼可以看出射众，這個桶原來的第一個值碟摆，被挪到后邊去了，看看Entry的結(jié)構(gòu)

Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

第四個參數(shù) e 叨橱，就是next
所以典蜕，如果當前桶已經(jīng)有值了，新增加的值是添加到開頭的罗洗。

對HashMap的基礎(chǔ)總結(jié)大概就這些愉舔，后邊有新的內(nèi)容在添加。

總結(jié)

HashMap 的默認初識容量為 16伙菜，負載因子為 0.75 轩缤，擴容機制是 當前容量x2
擴容時機，不同版本不一樣贩绕，1.7版本是添加新內(nèi)容是檢測擴容火的，1.8版本是添加完成后檢測
那么，我們在使用的時候淑倾，為了避免頻繁擴容帶來的消耗馏鹤，對HashMap的初始容量就需要結(jié)合實際情況計算一下，比如娇哆，當前應(yīng)用湃累，放入HashMap的成員最多300個，那么碍讨，300/0.75=400,那我們對于HashMap的初始大小治力，至少需要400.
非線程安全，整個源碼里沒有使用同步機制
允許key為null勃黍，允許value為null琴许。
所以，這里有個問題溉躲，如果我們使用get獲取value值時榜田，如果得到的時value益兄，無法確定這個null是因為HashMap里沒有這個key返回的null還是value值就是null，這個時候需要用containsKey先判斷一次箭券。這樣就比較麻煩了净捅，一般我們不往里邊存null。