Java容器源碼學(xué)習(xí)

1.List,Set,Map三者的區(qū)別

List(對(duì)付順序的好幫手)

List接口存儲(chǔ)一組不唯一（可以有多個(gè)元素引用相同的對(duì)象），有序的對(duì)象

Set(注重獨(dú)一無二的性質(zhì)):

不允許重復(fù)的集合姓建。不會(huì)有多個(gè)元素引用相同的對(duì)象缓溅。

Map(用Key來搜索的專家):

使用鍵值對(duì)存儲(chǔ)蛇损。Map會(huì)維護(hù)與Key有關(guān)聯(lián)的值。兩個(gè)Key可以引用相同的對(duì)象坛怪，但Key不能重復(fù)淤齐，典型的Key是String類型，但也可以是任何對(duì)象袜匿。

2.Arraylist 與 LinkedList 區(qū)別

1）是否保證線程安全

ArrayList 和 LinkedList 都是不同步的更啄，也就是不保證線程安全；

2）底層數(shù)據(jù)結(jié)構(gòu)

Arraylist 底層使用的是 Object 數(shù)組居灯；
LinkedList 底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表祭务，JDK1.7取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別）

補(bǔ)充內(nèi)容:雙向鏈表和雙向循環(huán)鏈表

雙向鏈表： 包含兩個(gè)指針怪嫌，一個(gè)prev指向前一個(gè)節(jié)點(diǎn)义锥，一個(gè)next指向后一個(gè)節(jié)點(diǎn)。



雙向循環(huán)鏈表： 最后一個(gè)節(jié)點(diǎn)的 next 指向head岩灭，而 head 的prev指向最后一個(gè)節(jié)點(diǎn)拌倍，構(gòu)成一個(gè)環(huán)。


3）插入和刪除是否受元素位置的影響

ArrayList 采用數(shù)組存儲(chǔ)噪径，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響柱恤。執(zhí)行add(E e) 方法的時(shí)候， ArrayList 會(huì)默認(rèn)在將指定的元素追加到此列表的末尾找爱，這種情況時(shí)間復(fù)雜度就是O(1)膨更。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element) ）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作缴允。

LinkedList 采用鏈表存儲(chǔ)荚守，所以對(duì)于add(E e)方法的插入珍德，刪除元素時(shí)間復(fù)雜度不受元素位置的影響近似 O（1），如果是要在指定位置i插入和刪除元素的話（add(int index, E element)） 時(shí)間復(fù)雜度近似為o(n)矗漾，因?yàn)樾枰纫苿?dòng)到指定位置再插入锈候。

4）是否支持快速隨機(jī)訪問

LinkedList 不支持高效的隨機(jī)元素訪問，而 ArrayList 支持敞贡”昧眨快速隨機(jī)訪問就是通過元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于get(int index) 方法)。

5）內(nèi)存空間占用

ArrayList的空間浪費(fèi)主要體現(xiàn)在在list列表的結(jié)尾會(huì)預(yù)留一定的容量空間誊役，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）获列。

補(bǔ)充內(nèi)容:RandomAccess接口
public interface RandomAccess {
}

查看源碼我們發(fā)現(xiàn)實(shí)際上 RandomAccess 接口中什么都沒有定義。所以蛔垢，在我看來 RandomAccess 接口不過是一個(gè)標(biāo)識(shí)罷了击孩。標(biāo)識(shí)什么？ 標(biāo)識(shí)實(shí)現(xiàn)這個(gè)接口的類具有隨機(jī)訪問功能鹏漆。

在 Collections工具類的binarySearch（）方法中巩梢，它要判斷傳入的list 是否 RamdomAccess 的實(shí)例，如果是艺玲，調(diào)用indexedBinarySearch（）方法括蝠，如果不是，那么調(diào)用iteratorBinarySearch（）方法

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 實(shí)現(xiàn)了 RandomAccess 接口饭聚， 而 LinkedList 沒有實(shí)現(xiàn)忌警。為什么呢？我覺得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)秒梳！
ArrayList 底層是數(shù)組慨蓝，而 LinkedList 底層是鏈表。數(shù)組天然支持隨機(jī)訪問端幼，時(shí)間復(fù)雜度為 O（1）礼烈，所以稱為快速隨機(jī)訪問。鏈表需要遍歷到特定位置才能訪問特定位置的元素婆跑，時(shí)間復(fù)雜度為 O（n）此熬，所以不支持快速隨機(jī)訪問。
ArrayList 實(shí)現(xiàn)了 RandomAccess 接口滑进，就表明了他具有快速隨機(jī)訪問功能犀忱。 RandomAccess 接口只是標(biāo)識(shí)，并不是說 ArrayList 實(shí)現(xiàn) RandomAccess 接口才具有快速隨機(jī)訪問功能的扶关！

list 的遍歷方式選擇

實(shí)現(xiàn)了 RandomAccess 接口的list阴汇，優(yōu)先選擇普通 for 循環(huán) ，其次 foreach节槐。
未實(shí)現(xiàn) RandomAccess接口的list搀庶，優(yōu)先選擇iterator（迭代器）遍歷（foreach遍歷底層也是通過iterator實(shí)現(xiàn)的,）拐纱，大size的數(shù)據(jù)，千萬不要使用普通for循環(huán)哥倔。

3.ArrayList 與 Vector 區(qū)別

Vector類的所有方法都是同步的秸架。可以由兩個(gè)線程安全地訪問一個(gè)Vector對(duì)象咆蒿、但是一個(gè)線程訪問Vector的話代碼要在同步操作上耗費(fèi)大量的時(shí)間东抹。

Arraylist不是同步的，所以在不需要保證線程安全時(shí)建議使用Arraylist沃测。

4.ArrayList 的擴(kuò)容機(jī)制

1)ArrayList 的構(gòu)造函數(shù)

ArrayList有三種方式來初始化缭黔，構(gòu)造方法源碼如下：

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

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *默認(rèn)構(gòu)造函數(shù)，使用初始容量10構(gòu)造一個(gè)空列表(無參數(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 = DEFAULTCAPACITY_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 = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;
        }
    }
以無參數(shù)構(gòu)造方法創(chuàng)建 ArrayList 時(shí)钠糊，實(shí)際上初始化賦值的是一個(gè)空數(shù)組挟秤。當(dāng)真正對(duì)數(shù)組進(jìn)行添加元素操作時(shí)，才真正分配容量抄伍。即向數(shù)組中添加第一個(gè)元素時(shí)艘刚，數(shù)組容量擴(kuò)為10。

2)以無參構(gòu)造函數(shù)創(chuàng)建的 ArrayList 為例分析ArrayList 擴(kuò)容機(jī)制

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

可以看到 add 方法 首先調(diào)用了ensureCapacityInternal(size + 1)
//得到最小擴(kuò)容量

    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 進(jìn)第1個(gè)元素時(shí)，minCapacity為1岗喉，在Math.max()方法比較后秋度，minCapacity 為10曲秉。

ensureExplicitCapacity() 方法

如果調(diào)用 ensureCapacityInternal() 方法就一定會(huì)進(jìn)過（執(zhí)行）這個(gè)方法

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

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

-當(dāng)我們要 add 進(jìn)第1個(gè)元素到 ArrayList 時(shí)，elementData.length 為0 （因?yàn)檫€是一個(gè)空的 list）霉颠，因?yàn)閳?zhí)行了 ensureCapacityInternal() 方法 查牌，所以 minCapacity 此時(shí)為10事期。此時(shí)，minCapacity - elementData.length > 0 成立纸颜，所以會(huì)進(jìn)入 grow(minCapacity) 方法兽泣。

-當(dāng)add第2個(gè)元素時(shí)，minCapacity 為2胁孙，此時(shí)e lementData.length(容量)在添加第一個(gè)元素后擴(kuò)容成 10 了唠倦。此時(shí)称鳞，minCapacity - elementData.length > 0 不成立，所以不會(huì)進(jìn)入 （執(zhí)行）grow(minCapacity) 方法牵敷。

-添加第3胡岔、4···到第10個(gè)元素時(shí)，依然不會(huì)執(zhí)行g(shù)row方法枷餐，數(shù)組容量都為10靶瘸。

-直到添加第11個(gè)元素，minCapacity(為11)比elementData.length（為10）要大毛肋。進(jìn)入grow方法進(jìn)行擴(kuò)容怨咪。

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

    /**
     * ArrayList擴(kuò)容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity為舊容量润匙，newCapacity為新容量
        int oldCapacity = elementData.length;
        //將oldCapacity 右移一位诗眨，其效果相當(dāng)于oldCapacity /2，
        //我們知道位運(yùn)算的速度遠(yuǎn)遠(yuǎn)快于整除運(yùn)算孕讳，整句運(yù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 每次擴(kuò)容之后容量都會(huì)變?yōu)樵瓉淼?1.5 倍Ａ么（JDK1.6版本以后） JDk1.6版本時(shí)，擴(kuò)容之后容量為 1.5 倍+1谒撼！

">>"（移位運(yùn)算符）：>>1 右移一位相當(dāng)于除2食寡，右移n位相當(dāng)于除以 2 的 n 次方。這里 oldCapacity 明顯右移了1位所以相當(dāng)于oldCapacity /2廓潜。對(duì)于大數(shù)據(jù)的2進(jìn)制運(yùn)算,位移運(yùn)算符比那些普通運(yùn)算符的運(yùn)算要快很多,因?yàn)槌绦騼H僅移動(dòng)一下而已,不去計(jì)算,這樣提高了效率,節(jié)省了資源

當(dāng)add第1個(gè)元素時(shí)抵皱，oldCapacity 為0，經(jīng)比較后第一個(gè)if判斷成立茉帅，newCapacity = minCapacity(為10)叨叙。但是第二個(gè)if判斷不會(huì)成立，即newCapacity 不比 MAX_ARRAY_SIZE大堪澎，則不會(huì)進(jìn)入 hugeCapacity 方法擂错。數(shù)組容量為10，add方法中 return true,size增為1樱蛤。

當(dāng)add第11個(gè)元素進(jìn)入grow方法時(shí)钮呀，newCapacity為15剑鞍，比minCapacity（為11）大，第一個(gè)if判斷不成立爽醋。新容量沒有大于數(shù)組最大size蚁署，不會(huì)進(jìn)入hugeCapacity方法。數(shù)組容量擴(kuò)為15蚂四，add方法中return true,size增為11光戈。以此類推······

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

從上面 grow() 方法源碼我們知道： 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) hugeCapacity() 方法來比較 minCapacity 和 MAX_ARRAY_SIZE遂赠，如果minCapacity大于最大容量久妆，則新容量則為Integer.MAX_VALUE，否則跷睦，新容量大小則為 MAX_ARRAY_SIZE 即為 Integer.MAX_VALUE - 8筷弦。

 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //對(duì)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;
    }

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

ArrayList 中大量調(diào)用了這兩個(gè)方法烂琴。比如：我們上面講的擴(kuò)容操作以及add(int index, E element)、toArray() 等方法中都用到了該方法蜕乡！

System.arraycopy() 方法
/**
     * 在此列表中的指定位置插入指定的元素奸绷。 
     *先調(diào)用 rangeCheckForAdd 對(duì)index進(jìn)行界限檢查；然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大异希；
     *再將從index開始之后的所有成員后移一個(gè)位置健盒；將element插入index位置绒瘦；最后size加1称簿。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法實(shí)現(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++;
    }

測試如下：

public class ArraycopyTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

}

結(jié)果：0 1 99 2 3 0 0 0 0 0

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

Arrays.copyOf()方法主要是為了給原有數(shù)組擴(kuò)容,測試代碼如下：

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length :"+b.length);
    }
}

結(jié)果：b.length :10

兩者聯(lián)系和區(qū)別

聯(lián)系：
看兩者源代碼可以發(fā)現(xiàn) copyOf() 內(nèi)部實(shí)際調(diào)用了 System.arraycopy() 方法

區(qū)別：
arraycopy() 需要目標(biāo)數(shù)組授药，將原數(shù)組拷貝到你自己定義的數(shù)組里或者原數(shù)組，而且可以選擇拷貝的起點(diǎn)和長度以及放入新數(shù)組中的位置
copyOf() 是系統(tǒng)自動(dòng)在內(nèi)部新建一個(gè)數(shù)組呜魄，并返回該數(shù)組悔叽。

4) ensureCapacity方法

 /**
    如有必要，增加此 ArrayList 實(shí)例的容量爵嗅，以確保它至少可以容納由minimum capacity參數(shù)指定的元素?cái)?shù)娇澎。
     *
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
最好在 add 大量元素之前用 ensureCapacity 方法，以減少增量重新分配的次數(shù)

我們通過下面的代碼實(shí)際測試以下這個(gè)方法的效果：

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

        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));
    }
}

運(yùn)行結(jié)果：
使用ensureCapacity方法前：4637
使用ensureCapacity方法后：241

通過運(yùn)行結(jié)果睹晒，我們可以很明顯的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法趟庄，以減少增量重新分配的次數(shù)

5. HashMap 和 Hashtable 的區(qū)別

線程是否安全

HashMap 是非線程安全的括细，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過synchronized 修飾戚啥。（保證線程安全使用 ConcurrentHashMap）

效率

因?yàn)榫€程安全的問題奋单，HashMap 要比 HashTable 效率高一點(diǎn)。另外猫十，HashTable 基本被淘汰览濒，不要在代碼中使用它

對(duì)Null key 和Null value的支持

HashMap 中，null 可以作為鍵拖云，這樣的鍵只有一個(gè)匾七，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為 null。但是在 HashTable 中 put 進(jìn)的鍵值只要有一個(gè) null江兢，直接拋出 NullPointerException昨忆。

初始容量大小和每次擴(kuò)充容量大小的不同

1)創(chuàng)建時(shí)如果不指定容量初始值，Hashtable 默認(rèn)的初始大小為11杉允，之后每次擴(kuò)充邑贴，容量變?yōu)樵瓉淼?n+1。HashMap 默認(rèn)的初始化大小為16叔磷。之后每次擴(kuò)充拢驾，容量變?yōu)樵瓉淼?倍。
2)創(chuàng)建時(shí)如果給定了容量初始值改基，那么 Hashtable 會(huì)直接使用你給定的大小繁疤，而 HashMap 會(huì)將其擴(kuò)充為2的冪次方大小（HashMap 中的tableSizeFor()方法保證秕狰，下面給出了源代碼）稠腊。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會(huì)介紹到為什么是2的冪次方
HashMap 中帶有初始容量的構(gòu)造函數(shù)：
 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面這個(gè)方法保證了 HashMap 總是使用2的冪作為哈希表的大小。

 /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

6. HashMap 和 HashSet區(qū)別

HashSet 底層就是基于 HashMap 實(shí)現(xiàn)的鸣哀。（HashSet 的源碼非常非常少架忌，因?yàn)槌?clone() 、writeObject()我衬、readObject()是 HashSet 自己不得不實(shí)現(xiàn)之外叹放，其他方法都是直接調(diào)用 HashMap 中的方法。

HashMap HashSet
實(shí)現(xiàn)了Map接口 實(shí)現(xiàn)Set接口
存儲(chǔ)鍵值對(duì) 僅存儲(chǔ)對(duì)象
調(diào)用 put（）向map中添加元素 調(diào)用 add（）方法向Set中添加元素
HashMap使用鍵（Key）計(jì)算Hashcode HashSet使用成員對(duì)象來計(jì)算hashcode值挠羔，對(duì)于兩個(gè)對(duì)象來說hashcode可能相同井仰，所以equals()方法用來判斷對(duì)象的相等性，

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

當(dāng)你把對(duì)象加入HashSet時(shí)破加，HashSet會(huì)先計(jì)算對(duì)象的hashcode值來判斷對(duì)象加入的位置俱恶，同時(shí)也會(huì)與其他加入的對(duì)象的hashcode值作比較，如果沒有相符的hashcode，HashSet會(huì)假設(shè)對(duì)象沒有重復(fù)出現(xiàn)速那。但是如果發(fā)現(xiàn)有相同hashcode值的對(duì)象俐银，這時(shí)會(huì)調(diào)用equals（）方法來檢查hashcode相等的對(duì)象是否真的相同。如果兩者相同端仰，HashSet就不會(huì)讓加入操作成功捶惜。

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

JDK1.8之前

JDK1.8 之前 HashMap 底層是 數(shù)組和鏈表 結(jié)合在一起使用也就是 鏈表散列。HashMap 通過 key 的 hashCode 經(jīng)過擾動(dòng)函數(shù)處理過后得到 hash 值荔烧，然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長度）吱七，如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同鹤竭，如果相同的話踊餐，直接覆蓋，不相同就通過拉鏈法解決沖突臀稚。

所謂擾動(dòng)函數(shù)指的就是 HashMap 的 hash 方法吝岭。使用 hash 方法也就是擾動(dòng)函數(shù)是為了防止一些實(shí)現(xiàn)比較差的 hashCode() 方法 換句話說使用擾動(dòng)函數(shù)之后可以減少碰撞。

JDK 1.8 HashMap 的 hash 方法源碼:

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化吧寺，但是原理不變窜管。

static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位異或
      // >>>:無符號(hào)右移，忽略符號(hào)位稚机，空位都以0補(bǔ)齊
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

對(duì)比一下JDK1.7的 HashMap 的 hash 方法源碼

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 幕帆，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了 4 次赖条。

所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合失乾。也就是說創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表纬乍。若遇到哈希沖突碱茁，則將沖突的值加到鏈表中即可。


JDK1.8之后

相比于之前的版本蕾额， JDK1.8之后在解決哈希沖突時(shí)有了較大的變化早芭，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時(shí)彼城，將鏈表轉(zhuǎn)化為紅黑樹诅蝶，以減少搜索時(shí)間。



TreeMap募壕、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹调炬。紅黑樹就是為了解決二叉查找樹的缺陷，因?yàn)槎娌檎覙湓谀承┣闆r下會(huì)退化成一個(gè)線性結(jié)構(gòu)舱馅。

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

為了能讓 HashMap 存取高效缰泡，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻。
我們上面也講到了過了棘钞，Hash 值的范圍值-2147483648到2147483647缠借，前后加起來大概40億的映射空間，只要哈希函數(shù)映射得比較均勻松散宜猜，一般應(yīng)用是很難出現(xiàn)碰撞的泼返。但問題是一個(gè)40億長度的數(shù)組，內(nèi)存是放不下的姨拥。所以這個(gè)散列值是不能直接拿來用的绅喉。用之前還要先做對(duì)數(shù)組的長度取模運(yùn)算，得到的余數(shù)才能用來要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)叫乌。
這個(gè)數(shù)組下標(biāo)的計(jì)算方法是“ (n - 1) & hash”柴罐。（n代表數(shù)組長度）。這也就解釋了 HashMap 的長度為什么是2的冪次方憨奸。

這個(gè)算法應(yīng)該如何設(shè)計(jì)呢革屠？

我們首先可能會(huì)想到采用%取余的操作來實(shí)現(xiàn)。但是排宰，重點(diǎn)來了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方屠阻；）《罡鳎” 并且 采用二進(jìn)制位操作 &国觉，相對(duì)于%能夠提高運(yùn)算效率，這就解釋了 HashMap 的長度為什么是2的冪次方虾啦。

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

主要原因在于 并發(fā)下的Rehash 會(huì)造成元素之間會(huì)形成一個(gè)循環(huán)鏈表麻诀。不過，jdk 1.8 后解決了這個(gè)問題傲醉，但是還是不建議在多線程下使用 HashMap,因?yàn)槎嗑€程下使用 HashMap 還是會(huì)存在其他問題比如數(shù)據(jù)丟失蝇闭。并發(fā)環(huán)境下推薦使用 ConcurrentHashMap 。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末硬毕，一起剝皮案震驚了整個(gè)濱河市呻引，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌吐咳，老刑警劉巖逻悠，帶你破解...
    沈念sama閱讀 212,718評(píng)論 6贊 492
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異韭脊，居然都是意外死亡童谒，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,683評(píng)論 3贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門沪羔，熙熙樓的掌柜王于貴愁眉苦臉地迎上來饥伊，“玉大人，你說我怎么就攤上這事±哦梗” “怎么了愉豺？”我有些...
    開封第一講書人閱讀 158,207評(píng)論 0贊 348
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長茫因。 經(jīng)常有香客問我粒氧，道長，這世上最難降的妖魔是什么节腐？ 我笑而不...
    開封第一講書人閱讀 56,755評(píng)論 1贊 284
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任外盯，我火速辦了婚禮，結(jié)果婚禮上翼雀，老公的妹妹穿的比我還像新娘饱苟。我一直安慰自己，他們只是感情好狼渊，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,862評(píng)論 6贊 386
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布箱熬。 她就那樣靜靜地躺著，像睡著了一般狈邑。 火紅的嫁衣襯著肌膚如雪城须。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 50,050評(píng)論 1贊 291
  • 城市分裂傳說
    那天米苹，我揣著相機(jī)與錄音糕伐，去河邊找鬼。 笑死蘸嘶，一個(gè)胖子當(dāng)著我的面吹牛良瞧，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播训唱，決...
    沈念sama閱讀 39,136評(píng)論 3贊 410
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼褥蚯，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了况增？” 一聲冷哼從身側(cè)響起赞庶，我...
    開封第一講書人閱讀 37,882評(píng)論 0贊 268
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎澳骤，沒想到半個(gè)月后歧强，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 44,330評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡宴凉，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,651評(píng)論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年誊锭，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片弥锄。...
    茶點(diǎn)故事閱讀 38,789評(píng)論 1贊 341
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出籽暇，到底是詐尸還是另有隱情温治，我是刑警寧澤，帶...
    沈念sama閱讀 34,477評(píng)論 4贊 333
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布戒悠，位于F島的核電站熬荆，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏绸狐。R本人自食惡果不足惜卤恳，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,135評(píng)論 3贊 317
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望寒矿。 院中可真熱鬧突琳，春花似錦、人聲如沸符相。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,864評(píng)論 0贊 21
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽啊终。三九已至镜豹，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間蓝牲，已是汗流浹背趟脂。 一陣腳步聲響...
    開封第一講書人閱讀 32,099評(píng)論 1贊 267
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留例衍，地道東北人散怖。 一個(gè)月前我還...
    沈念sama閱讀 46,598評(píng)論 2贊 362
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像肄渗，于是被迫代替她去往敵國和親镇眷。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,697評(píng)論 2贊 351