本文取自工匠若水的qq群里的Java基礎(chǔ)題目审胸，把里面有關(guān)Java集合放在一起。
全文github地址

35.Arraylist 的動(dòng)態(tài)擴(kuò)容機(jī)制是如何自動(dòng)增加的利凑？簡(jiǎn)單說(shuō)說(shuō)你理解的增加流程浆劲！

解析：

當(dāng)在 ArrayList 中增加一個(gè)對(duì)象時(shí) Java 會(huì)去檢查 Arraylist 以確保已存在的數(shù)組中有足夠的容量來(lái)存儲(chǔ)這個(gè)新對(duì)象，如果沒(méi)有足夠容量就新建一個(gè)長(zhǎng)度更長(zhǎng)的數(shù)組（原來(lái)的1.5倍）哀澈，舊的數(shù)組就會(huì)使用 Arrays.copyOf 方法被復(fù)制到新的數(shù)組中去梳侨，現(xiàn)有的數(shù)組引用指向了新的數(shù)組。下面代碼展示為 Java 1.8 中通過(guò) ArrayList.add 方法添加元素時(shí)日丹，內(nèi)部會(huì)自動(dòng)擴(kuò)容，擴(kuò)容流程如下：

//確保容量夠用蚯嫌，內(nèi)部會(huì)嘗試擴(kuò)容哲虾，如果需要
ensureCapacityInternal(size + 1)

//在未指定容量的情況下，容量為DEFAULT_CAPACITY = 10
//并且在第一次使用時(shí)創(chuàng)建容器數(shù)組择示，在存儲(chǔ)過(guò)一次數(shù)據(jù)后束凑，數(shù)組的真實(shí)容量至少DEFAULT_CAPACITY
 private void ensureCapacityInternal(int minCapacity) {
    //判斷當(dāng)前的元素容器是否是初始的空數(shù)組
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //如果是默認(rèn)的空數(shù)組，則 minCapacity 至少為DEFAULT_CAPACITY
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

//通過(guò)該方法進(jìn)行真實(shí)準(zhǔn)確擴(kuò)容嘗試的操作
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//記錄List的結(jié)構(gòu)修改的次數(shù)

        //需要擴(kuò)容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

//擴(kuò)容操作
 private void grow(int minCapacity) {
    //原來(lái)的容量
    int oldCapacity = elementData.length;
    
    //新的容量 = 原來(lái)的容量 + （原來(lái)的容量的一半）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //如果計(jì)算的新的容量比指定的擴(kuò)容容量小栅盲，那么就使用指定的容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    //如果新的容量大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)
    //那么就使用hugeCapacity進(jìn)行容量分配
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    
    //創(chuàng)建長(zhǎng)度為newCapacity的數(shù)組汪诉，并復(fù)制原來(lái)的元素到新的容器，完成ArrayList的內(nèi)部擴(kuò)容
    elementData = Arrays.copyOf(elementData, newCapacity);
 }

36.下面這些方法可以正常運(yùn)行嗎谈秫？為什么扒寄？

public void remove1(ArrayList<Integer> list) {
    for(Integer a : list){
        if(a <= 10){
            list.remove(a);
        }
    }
}

public static void remove2(ArrayList<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        if(it.next() <= 10) {
            it.remove();
        }
    }
}

public static void remove3(ArrayList<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()) {
        it.remove();    
    }
}

public static void remove4(ArrayList<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()) {
        it.next();
        it.remove();
        it.remove();
    }
}

解析：

remove1 方法會(huì)拋出 ConcurrentModificationException 異常，這是迭代器的一個(gè)陷阱拟烫，foreach 遍歷編譯后實(shí)質(zhì)會(huì)替換為迭代器實(shí)現(xiàn)（普通for循環(huán)不會(huì)拋這個(gè)異常该编，因?yàn)閘ist.size方法一般不會(huì)變，所以只會(huì)漏刪除）硕淑，因?yàn)榈鲀?nèi)部會(huì)維護(hù)一些索引位置數(shù)據(jù)课竣，要求在迭代過(guò)程中容器不能發(fā)生結(jié)構(gòu)性變化（添加嘉赎、插入、刪除于樟，修改數(shù)據(jù)不算）公条，否則這些索引位置數(shù)據(jù)就失效了，避免的方式就是使用迭代器的 remove 方法迂曲。

remove2 方法可以正常運(yùn)行靶橱，無(wú)任何錯(cuò)誤。

remove3 方法會(huì)拋出 IllegalStateException 異常奢米，因?yàn)槭褂玫鞯?remove 方法前必須先調(diào)用 next 方法抓韩，next 方法會(huì)檢測(cè)容器是否發(fā)生了結(jié)構(gòu)性變化，然后更新 cursor 和 lastRet 值鬓长，直接不調(diào)用 next 而 remove 會(huì)導(dǎo)致相關(guān)值不正確谒拴。

remove4 方法會(huì)拋出 IllegalStateException 異常，理由同 remove3涉波，remove 調(diào)用一次后 lastRet 值會(huì)重置為 -1英上，沒(méi)有調(diào)用 next 去設(shè)置 lastRet 的情況下再直接調(diào)一次 remove 自然就狀態(tài)異常了。

當(dāng)然了啤覆，上面四個(gè)寫法的具體官方解答可參見(jiàn) ArrayList 中迭代器部分源碼苍日，如下：

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;

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

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

37.簡(jiǎn)要解釋下面程序的執(zhí)行現(xiàn)象和結(jié)果？

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
Integer[] array1 = new Integer[3];
list.toArray(array1);
Integer[] array2 = list.toArray(new Integer[0]);
System.out.println(Arrays.equals(array1, array2));  //1 結(jié)果是什么窗声？為什么相恃？

Integer[] array = {1, 2, 3};
List<Integer> list = Arrays.asList(array);
list.add(4);    //2 結(jié)果是什么？為什么笨觅？

Integer[] array = {1, 2, 3};
List<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
list.add(4);    //3 結(jié)果是什么拦耐？為什么？

解析：

1 輸出為 true见剩，因?yàn)?ArrayList 有兩個(gè)方法可以返回?cái)?shù)組Object[] toArray()和<T> T[] toArray(T[] a)杀糯，第一個(gè)方法返回的數(shù)組是通過(guò) Arrays.copyOf 實(shí)現(xiàn)的，第二個(gè)方法如果參數(shù)數(shù)組長(zhǎng)度足以容納所有元素就使用參數(shù)數(shù)組苍苞，否則新建一個(gè)數(shù)組返回固翰，所以結(jié)果為 true。

2 會(huì)拋出 UnsupportedOperationException 異常羹呵，因?yàn)?Arrays 的 asList 方法返回的是一個(gè) Arrays 內(nèi)部類的 ArrayList 對(duì)象骂际，這個(gè)對(duì)象沒(méi)有實(shí)現(xiàn) add、remove 等方法冈欢，只實(shí)現(xiàn)了 set 等方法方援，所以通過(guò) Arrays.asList 轉(zhuǎn)換的列表不具備結(jié)構(gòu)可變性。

3 當(dāng)然可以正常運(yùn)行咯涛癌，不可變結(jié)構(gòu)的 Arrays 的 ArrayList 通過(guò)構(gòu)造放入了真正的萬(wàn)能 ArrayList犯戏，自然就可以操作咯送火。

38.簡(jiǎn)單解釋一下 Collection 和 Collections 的區(qū)別？

解析：

java.util.Collection 是一個(gè)集合接口先匪，它提供了對(duì)集合對(duì)象進(jìn)行基本操作的通用接口方法种吸，在 Java 類庫(kù)中有很多具體的實(shí)現(xiàn)，意義是為各種具體的集合提供最大化的統(tǒng)一操作方式呀非。
譬如 Collection 的實(shí)現(xiàn)類有 List坚俗、Set 等，List 的實(shí)現(xiàn)類有 LinkedList岸裙、ArrayList猖败、Vector 等，Vector 的實(shí)現(xiàn)類有 Stack 等降允，不過(guò)切記 Map 是自立門戶的恩闻，其提供了轉(zhuǎn)換為 Collection 的方法，但是自己不是 Collection 的子類剧董。

java.util.Collections 是一個(gè)包裝類幢尚，它包含有各種有關(guān)集合操作的靜態(tài)多態(tài)方法，此類構(gòu)造 private 不能實(shí)例化翅楼，就像一個(gè)工具類尉剩，服務(wù)于 Java 的 Collection 框架，其提供的方法大概可以分為對(duì)容器接口對(duì)象進(jìn)行操作類（查找和替換毅臊、排序和調(diào)整順序理茎、添加和修改）和返回一個(gè)容器接口對(duì)象類（適配器將其他類型的數(shù)據(jù)轉(zhuǎn)換為容器接口對(duì)象、裝飾器修飾一個(gè)給定容器接口對(duì)象增加某種性質(zhì)）管嬉。

39.解釋一下 ArrayList功蜓、Vector、Stack宠蚂、LinkedList 的實(shí)現(xiàn)和區(qū)別及特點(diǎn)和適用場(chǎng)景？

解析：

首先他們都是 List 家族的兒子童社，List 又是 Collection 的子接口求厕，Collection 又是 Iterable 的子接口，所以他們都具備 Iterable 和 Collection 和 List 的基本特性扰楼。

ArrayList 是一個(gè)動(dòng)態(tài)數(shù)組隊(duì)列呀癣，隨機(jī)訪問(wèn)效率高，隨機(jī)插入弦赖、刪除效率低项栏。LinkedList 是一個(gè)雙向鏈表，它也可以被當(dāng)作堆棧蹬竖、隊(duì)列或雙端隊(duì)列進(jìn)行操作沼沈，隨機(jī)訪問(wèn)效率低流酬，但隨機(jī)插入、隨機(jī)刪除效率略好列另。Vector 是矢量隊(duì)列芽腾，和 ArrayList 一樣是一個(gè)動(dòng)態(tài)數(shù)組，但是 Vector 是線程安全的页衙。Stack 繼承于 Vector摊滔，特性是先進(jìn)后出(FILO, FirstIn Last Out)。

從線程安全角度看 Vector店乐、Stack 是線程安全的艰躺，ArrayList、LinkedList 是非線程安全的眨八。

從實(shí)現(xiàn)角度看 LinkedList 是雙向鏈表結(jié)構(gòu)腺兴，ArrayList、Vector踪古、Stack 是內(nèi)存數(shù)組結(jié)構(gòu)含长。

從動(dòng)態(tài)擴(kuò)容角度看由于 ArrayList 和 Vector（Stack 繼承自 Vector，只在 Vector 的基礎(chǔ)上添加了幾個(gè) Stack 相關(guān)的方法伏穆，故之后不再對(duì) Stack 做特別的說(shuō)明）使用數(shù)組實(shí)現(xiàn)拘泞，當(dāng)數(shù)組長(zhǎng)度不夠時(shí)，其內(nèi)部會(huì)創(chuàng)建一個(gè)更大的數(shù)組枕扫，然后將原數(shù)組中的數(shù)據(jù)拷貝至新數(shù)組中陪腌，而 LinkedList 是雙向鏈表結(jié)構(gòu)，內(nèi)存不用連續(xù)烟瞧，所以用多少申請(qǐng)多少诗鸭。

從效率方面來(lái)說(shuō) Vector、ArrayList参滴、Stack 是基于數(shù)組實(shí)現(xiàn)的强岸，是根據(jù)索引來(lái)訪問(wèn)元素，Vector（Stack）和 ArrayList 最大的區(qū)別就是 synchronization 同步的使用砾赔，拋開(kāi)兩個(gè)只在序列化過(guò)程中使用的方法不說(shuō)蝌箍，沒(méi)有一個(gè) ArrayList 的方法是同步的，相反暴心，絕大多數(shù) Vector（Stack）的方法法都是直接或者間接的同步的妓盲，因此就造成 ArrayList 比 Vector（Stack）更快些，不過(guò)在最新的 JVM 中专普，這兩個(gè)類的速度差別是很小的悯衬，幾乎可以忽略不計(jì)；而 LinkedList 是雙向鏈表實(shí)現(xiàn)檀夹，根據(jù)索引訪問(wèn)元素時(shí)需要遍歷尋找筋粗，性能略差策橘。所以 ArrayList 適合大量隨機(jī)訪問(wèn)，LinkList 適合頻繁刪除插入操作亏狰。

從差異角度看 LinkedList 還具備 Deque 雙端隊(duì)列的特性役纹，其實(shí)現(xiàn)了 Deque 接口，Deque 繼承自 Queue 隊(duì)列接口暇唾，其實(shí)也挺好理解促脉，因?yàn)?LinkedList 是的實(shí)現(xiàn)是雙向鏈表結(jié)構(gòu)，所以實(shí)現(xiàn)隊(duì)列特性實(shí)在是太容易了策州。

40.簡(jiǎn)單介紹下 List 瘸味、Map、Set够挂、Queue 的區(qū)別和關(guān)系旁仿？

解析：

List、Set孽糖、Queue 都繼承自 Collection 接口枯冈，而 Map 則不是（繼承自 Object），所以容器類有兩個(gè)根接口办悟，分別是 Collection 和 Map尘奏，Collection 表示單個(gè)元素的集合，Map 表示鍵值對(duì)的集合病蛉。

List 的主要特點(diǎn)就是有序性和元素可空性炫加，他維護(hù)了元素的特定順序，其主要實(shí)現(xiàn)類有 ArrayList 和 LinkList铺然。ArrayList 底層由數(shù)組實(shí)現(xiàn)俗孝，允許元素隨機(jī)訪問(wèn)，但是向 ArrayList 列表中間插入刪除元素需要移位復(fù)制速度略慢魄健；LinkList 底層由雙向鏈表實(shí)現(xiàn)赋铝，適合頻繁向列表中插入刪除元素，隨機(jī)訪問(wèn)需要遍歷所以速度略慢沽瘦，適合當(dāng)做堆棧革骨、隊(duì)列、雙向隊(duì)列使用其垄。

Set 的主要特性就是唯一性和元素可空性，存入 Set 的每個(gè)元素都必須唯一卤橄，加入 Set 的元素都必須確保對(duì)象的唯一性绿满，Set 不保證維護(hù)元素的有序性，其主要實(shí)現(xiàn)類有 HashSet窟扑、LinkHashSet喇颁、TreeSet漏健。HashSet 是為快速查找元素而設(shè)計(jì)，存入 HashSet 的元素必須定義 hashCode 方法橘霎，其實(shí)質(zhì)可以理解為是 HashMap 的包裝類蔫浆，所以 HashSet 的值還具備可 null 性；LinkHashSet 具備 HashSet 的查找速度且通過(guò)鏈表保證了元素的插入順序（實(shí)質(zhì)為 HashSet 的子類）姐叁，迭代時(shí)是有序的瓦盛，同理存入 LinkHashSet 的元素必須定義 hashCode 方法；TreeSet 實(shí)質(zhì)是 TreeMap 的包裝類外潜，所以 TreeSet 的值不備可 null 性原环，其保證了元素的有序性，底層為紅黑樹(shù)結(jié)構(gòu)处窥，存入 TreeSet 的元素必須實(shí)現(xiàn) Comparable 接口嘱吗；不過(guò)特別注意 EnumSet 的實(shí)現(xiàn)和 EnumMap 沒(méi)有一點(diǎn)關(guān)系。

Queue 的主要特性就是隊(duì)列和元素不可空性滔驾，其主要的實(shí)現(xiàn)類有 LinkedList谒麦、PriorityQueue。LinkedList 保證了按照元素的插入順序進(jìn)行操作哆致；PriorityQueue 按照優(yōu)先級(jí)進(jìn)行插入抽取操作绕德，元素可以通過(guò)實(shí)現(xiàn) Comparable 接口來(lái)保證優(yōu)先順序。Deque 是 Queue 的子接口沽瞭，表示更為通用的雙端隊(duì)列迁匠，有明確的在頭或尾進(jìn)行查看、添加和刪除的方法驹溃，ArrayDeque 基于循環(huán)數(shù)組實(shí)現(xiàn)城丧，效率更高一些。

Map 自立門戶豌鹤，但是也提供了嫁接到 Collection 相關(guān)方法亡哄，其主要特性就是維護(hù)鍵值對(duì)關(guān)聯(lián)和查找特性，其主要實(shí)現(xiàn)類有 HashTab布疙、HashMap蚊惯、LinkedHashMap、TreeMap灵临。HashTab 類似 HashMap截型，但是不允許鍵為 null 和值為 null，比 HashMap 慢儒溉，因?yàn)闉橥讲僮骰陆梗籋ashMap 是基于散列列表的實(shí)現(xiàn)，其鍵和值都可以為 null；LinkedHashMap 類似 HashMap波闹，其鍵和值都可以為 null酝豪，其有序性為插入順序或者最近最少使用的次序（LRU 算法的核心就是這個(gè)），之所以能有序精堕，是因?yàn)槊總€(gè)元素還加入到了一個(gè)雙向鏈表中孵淘；TreeMap 是基于紅黑樹(shù)算法實(shí)現(xiàn)的，查看鍵值對(duì)時(shí)會(huì)被排序歹篓，存入的元素必須實(shí)現(xiàn) Comparable 接口瘫证，但是不允許鍵為 null，值可以為 null滋捶；如果鍵為枚舉類型可以使用專門的實(shí)現(xiàn)類 EnumMap痛悯，它使用效率更高的數(shù)組實(shí)現(xiàn)。

從數(shù)據(jù)結(jié)構(gòu)角度看集合的區(qū)別有如下：

動(dòng)態(tài)數(shù)組：ArrayList 內(nèi)部是動(dòng)態(tài)數(shù)組重窟，HashMap 內(nèi)部的鏈表數(shù)組也是動(dòng)態(tài)擴(kuò)展的载萌，ArrayDeque 和 PriorityQueue 內(nèi)部也都是動(dòng)態(tài)擴(kuò)展的數(shù)組。

鏈表：LinkedList 是用雙向鏈表實(shí)現(xiàn)的巡扇，HashMap 中映射到同一個(gè)鏈表數(shù)組的鍵值對(duì)是通過(guò)單向鏈表鏈接起來(lái)的扭仁，LinkedHashMap 中每個(gè)元素還加入到了一個(gè)雙向鏈表中以維護(hù)插入或訪問(wèn)順序。

哈希表：HashMap 是用哈希表實(shí)現(xiàn)的厅翔，HashSet, LinkedHashSet 和 LinkedHashMap 基于 HashMap乖坠，內(nèi)部當(dāng)然也是哈希表。

排序二叉樹(shù)：TreeMap 是用紅黑樹(shù)(基于排序二叉樹(shù))實(shí)現(xiàn)的刀闷，TreeSet 內(nèi)部使用 TreeMap熊泵，當(dāng)然也是紅黑樹(shù)，紅黑樹(shù)能保持元素的順序且綜合性能很高甸昏。

堆：PriorityQueue 是用堆實(shí)現(xiàn)的顽分，堆邏輯上是樹(shù)，物理上是動(dòng)態(tài)數(shù)組施蜜，堆可以高效地解決一些其他數(shù)據(jù)結(jié)構(gòu)難以解決的問(wèn)題卒蘸。

循環(huán)數(shù)組：ArrayDeque 是用循環(huán)數(shù)組實(shí)現(xiàn)的，通過(guò)對(duì)頭尾變量的維護(hù)翻默，實(shí)現(xiàn)了高效的隊(duì)列操作缸沃。

位向量：EnumSet 是用位向量實(shí)現(xiàn)的，對(duì)于只有兩種狀態(tài)且需要進(jìn)行集合運(yùn)算的數(shù)據(jù)使用位向量進(jìn)行表示修械、位運(yùn)算進(jìn)行處理趾牧，精簡(jiǎn)且高效。

41.簡(jiǎn)單說(shuō)說(shuō) HashMap 的底層原理肯污？

答案：

當(dāng)我們往 HashMap 中 put 元素時(shí)翘单，先根據(jù) key 的 hash 值得到這個(gè)元素在數(shù)組中的位置（即下標(biāo)）梯皿，然后把這個(gè)元素放到對(duì)應(yīng)的位置中，如果這個(gè)元素所在的位子上已經(jīng)存放有其他元素就在同一個(gè)位子上的元素以鏈表的形式存放县恕，新加入的放在鏈頭，從 HashMap 中 get 元素時(shí)先計(jì)算 key 的 hashcode剂桥，找到數(shù)組中對(duì)應(yīng)位置的某一元素忠烛，然后通過(guò) key 的 equals 方法在對(duì)應(yīng)位置的鏈表中找到需要的元素，所以 HashMap 的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合权逗。

解析：

HashMap 底層是基于哈希表的 Map 接口的非同步實(shí)現(xiàn)美尸，實(shí)際是一個(gè)鏈表散列數(shù)據(jù)結(jié)構(gòu)（即數(shù)組和鏈表的結(jié)合體）。
首先由于數(shù)組存儲(chǔ)區(qū)間是連續(xù)的斟薇，占用內(nèi)存嚴(yán)重师坎，故空間復(fù)雜度大，但二分查找時(shí)間復(fù)雜度锌氨酢（O(1)）胯陋，所以尋址容易，插入和刪除困難袱箱。而鏈表存儲(chǔ)區(qū)間離散遏乔，占用內(nèi)存比較寬松，故空間復(fù)雜度小发笔，但時(shí)間復(fù)雜度大（O(N)）盟萨，所以尋址困難，插入和刪除容易了讨。
所以就產(chǎn)生了一種新的數(shù)據(jù)結(jié)構(gòu)------哈希表捻激，哈希表既滿足了數(shù)據(jù)的查找方便，同時(shí)不占用太多的內(nèi)容空間前计，使用也十分方便胞谭，哈希表有多種不同的實(shí)現(xiàn)方法，HashMap 采用的是鏈表的數(shù)組實(shí)現(xiàn)方式残炮，具體如下：

首先 HashMap 里面實(shí)現(xiàn)了一個(gè)靜態(tài)內(nèi)部類 Entry(key韭赘、value、next)势就，HashMap 的基礎(chǔ)就是一個(gè) Entry[] 線性數(shù)組泉瞻，Map 的內(nèi)容都保存在 Entry[] 里面，而 HashMap 用的線性數(shù)組卻是隨機(jī)存儲(chǔ)的原因如下：

// 存儲(chǔ)時(shí)
int hash = key.hashCode(); //每個(gè) key 的 hash 是一個(gè)固定的 int 值 
int index = hash % Entry[].length; 
Entry[index] = value;

// 取值時(shí)
int hash = key.hashCode(); 
int index = hash % Entry[].length; 
return Entry[index];

當(dāng)我們通過(guò) put 向 HashMap 添加多個(gè)元素時(shí)會(huì)遇到兩個(gè) key 通過(guò)hash % Entry[].length計(jì)算得到相同 index 的情況苞冯，這時(shí)具有相同 index 的元素就會(huì)被放在線性數(shù)組 index 位置涛目，然后其 next 屬性指向上個(gè)同 index 的 Entry 元素形成鏈表結(jié)構(gòu)（譬如第一個(gè)鍵值對(duì) A 進(jìn)來(lái)，通過(guò)計(jì)算其 key 的 hash 得到的 index = 0翰守，記做 Entry[0] = A则吟，接著第二個(gè)鍵值對(duì) B 進(jìn)來(lái)，通過(guò)計(jì)算其 index 也等于 0，這時(shí)候 B.next = A, Entry[0] = B畴蹭，如果又進(jìn)來(lái) C 且 index 也等于 0 則 C.next = B, Entry[0] = C）坦仍。
當(dāng)我們通過(guò) get 從 HashMap 獲取元素時(shí)首先會(huì)定位到數(shù)組元素，接著再遍歷該元素處的鏈表獲取真實(shí)元素叨襟。
當(dāng) key 為 null 時(shí) HashMap 特殊處理總是放在 Entry[] 數(shù)組的第一個(gè)元素繁扎。
HashMap 使用 Key 對(duì)象的 hashCode() 和 equals() 方法去決定 key-value 對(duì)的索引，當(dāng)我們?cè)囍鴱?HashMap 中獲取值的時(shí)候糊闽，這些方法也會(huì)被用到梳玫，所以 equals() 和 hashCode() 的實(shí)現(xiàn)應(yīng)該遵循以下規(guī)則：
如果o1.equals(o2)則o1.hashCode() == o2.hashCode()必須為 true，或者如果o1.hashCode() == o2.hashCode()則不意味著o1.equals(o2)會(huì)為true右犹。

關(guān)于 HashMap 的 hash 函數(shù)算法巧妙之處可以參見(jiàn)本文鏈接：http://pengranxiang.iteye.com/blog/543893

42.簡(jiǎn)單解釋一下 Comparable 和 Comparator 的區(qū)別和場(chǎng)景提澎？

解析：

Comparable 對(duì)實(shí)現(xiàn)它的每個(gè)類的對(duì)象進(jìn)行整體排序，這個(gè)接口需要類本身去實(shí)現(xiàn)念链，若一個(gè)類實(shí)現(xiàn)了 Comparable 接口盼忌，實(shí)現(xiàn) Comparable 接口的類的對(duì)象的 List 列表(或數(shù)組)可以通過(guò) Collections.sort（或 Arrays.sort）進(jìn)行排序，此外實(shí)現(xiàn) Comparable 接口的類的對(duì)象可以用作有序映射(如TreeMap)中的鍵或有序集合(如TreeSet)中的元素掂墓，而不需要指定比較器碴犬，
實(shí)現(xiàn) Comparable 接口必須修改自身的類（即在自身類中實(shí)現(xiàn)接口中相應(yīng)的方法），如果我們使用的類無(wú)法修改（如SDK中一個(gè)沒(méi)有實(shí)現(xiàn)Comparable的類）梆暮，我們又想排序服协，就得用到 Comparator 這個(gè)接口了（策略模式）。
所以如果你正在編寫一個(gè)值類啦粹，它具有非常明顯的內(nèi)在排序關(guān)系偿荷，比如按字母順序、按數(shù)值順序或者按年代順序唠椭，那你就應(yīng)該堅(jiān)決考慮實(shí)現(xiàn) Comparable 這個(gè)接口跳纳，
若一個(gè)類實(shí)現(xiàn)了 Comparable 接口就意味著該類支持排序，而 Comparator 是比較器贪嫂，我們?nèi)粜枰刂颇硞€(gè)類的次序寺庄，可以建立一個(gè)該類的比較器來(lái)進(jìn)行排序。
Comparable 比較固定力崇，和一個(gè)具體類相綁定斗塘，而 Comparator 比較靈活，可以被用于各個(gè)需要比較功能的類使用亮靴。

43.簡(jiǎn)單說(shuō)說(shuō) Iterator 和 ListIterator 的區(qū)別馍盟？

解析：

ListIterator 有 add() 方法，可以向 List 中添加對(duì)象茧吊，而 Iterator 不能贞岭。

ListIterator 和 Iterator 都有 hasNext() 和 next() 方法八毯，可以實(shí)現(xiàn)順序向后遍歷，但是 ListIterator 有 hasPrevious() 和 previous() 方法瞄桨，可以實(shí)現(xiàn)逆向（順序向前）遍歷话速，Iterator 就不可以。

ListIterator 可以定位當(dāng)前的索引位置芯侥，通過(guò) nextIndex() 和 previousIndex() 可以實(shí)現(xiàn)尿孔，Iterator 沒(méi)有此功能。

都可實(shí)現(xiàn)刪除對(duì)象筹麸，但是 ListIterator 可以實(shí)現(xiàn)對(duì)象的修改，通過(guò) set() 方法可以實(shí)現(xiàn)雏婶，Iierator 僅能遍歷物赶，不能修改。

容器類提供的迭代器都會(huì)在迭代中間進(jìn)行結(jié)構(gòu)性變化檢測(cè)留晚，如果容器發(fā)生了結(jié)構(gòu)性變化酵紫，就會(huì)拋出 ConcurrentModificationException，所以不能在迭代中間直接調(diào)用容器類提供的 add错维、remove 方法奖地，如需添加和刪除，應(yīng)調(diào)用迭代器的相關(guān)方法赋焕。

44.請(qǐng)實(shí)現(xiàn)一個(gè)極簡(jiǎn) LRU 算法容器参歹？

解析：

看起來(lái)是一道很難的題目，其實(shí)靜下來(lái)你會(huì)發(fā)現(xiàn)想考察的其實(shí)就是 LRU 的原理和 LinkedHashMap 容器知識(shí)隆判，當(dāng)然犬庇，你要是厲害不依賴 LinkedHashMap 自己純手寫擼一個(gè)也不介意。
LinkedHashMap 支持插入順序或者訪問(wèn)順序侨嘀，LRU 算法其實(shí)就要用到它訪問(wèn)順序的特性臭挽，即對(duì)一個(gè)鍵執(zhí)行 get、put 操作后其對(duì)應(yīng)的鍵值對(duì)會(huì)移到鏈表末尾咬腕，所以最末尾的是最近訪問(wèn)的欢峰，最開(kāi)始的最久沒(méi)被訪問(wèn)的。
LRU 是一種流行的替換算法涨共，它的全稱是 Least Recently Used纽帖，最近最少使用，它的思路是最近剛被使用的很快再次被用的可能性最高举反，而最久沒(méi)被訪問(wèn)的很快再次被用的可能性最低抛计，所以被優(yōu)先清理。
下面給出極簡(jiǎn) LRU 緩存算法容器：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxEntries;
    
    //maxEntries 最大緩存?zhèn)€數(shù)
    public LRUCache(int maxEntries){
        super(16, 0.75f, true);
        this.maxEntries = maxEntries;
    }
    
    //在添加元素到 LinkedHashMap 后會(huì)調(diào)用這個(gè)方法照筑，傳遞的參數(shù)是最久沒(méi)被訪問(wèn)的鍵值對(duì)吹截，如果這個(gè)方法返回 true 則這個(gè)最久的鍵值對(duì)就會(huì)被刪除瘦陈，LinkedHashMap 的實(shí)現(xiàn)總是返回 false，所有容量沒(méi)有限制波俄。
    @Override
    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}