一文搞定所有Java集合面試題

剛剛經(jīng)歷過(guò)秋招，看了大量的面經(jīng)，順便將常見(jiàn)的Java集合?？贾R(shí)點(diǎn)總結(jié)了一下，并根據(jù)被問(wèn)到的頻率大致做了一個(gè)標(biāo)注。一顆星表示知識(shí)點(diǎn)需要了解，被問(wèn)到的頻率不高，面試時(shí)起碼能說(shuō)個(gè)差不多。兩顆星表示被問(wèn)到的頻率較高或?qū)斫釰ava有著重要的作用，建議熟練掌握。三顆星表示被問(wèn)到的頻率非常高，建議深入理解并熟練掌握其相關(guān)知識(shí)，方便面試時(shí)拓展（方便裝逼），給面試官留下個(gè)好印象。

微信搜索公眾號(hào)路人zhang，回復(fù)面試手冊(cè)，領(lǐng)取本文檔PDF版及更多面試資料。

推薦閱讀：

常用的集合類(lèi)有哪些？?。?/h3>

Map接口和Collection接口是所有集合框架的父接口。下圖中的實(shí)線和虛線看著有些亂，其中接口與接口之間如果有聯(lián)系為繼承關(guān)系，類(lèi)與類(lèi)之間如果有聯(lián)系為繼承關(guān)系，類(lèi)與接口之間則是類(lèi)實(shí)現(xiàn)接口。重點(diǎn)掌握的抽象類(lèi)有HashMap，LinkedList，HashTable，ArrayList，HashSet，Stack，TreeSet，TreeMap。注意：Collection接口不是Map的父接口。

在這里插入圖片描述
在這里插入圖片描述

List，Set，Map三者的區(qū)別？ ＊＊＊

  • List：有序集合（有序指存入的順序和取出的順序相同，不是按照元素的某些特性排序），可存儲(chǔ)重復(fù)元素，可存儲(chǔ)多個(gè)null。
  • Set：無(wú)序集合（元素存入和取出順序不一定相同），不可存儲(chǔ)重復(fù)元素，只能存儲(chǔ)一個(gè)null。
  • Map：使用鍵值對(duì)的方式對(duì)元素進(jìn)行存儲(chǔ)，key是無(wú)序的，且是唯一的。value值不唯一。不同的key值可以對(duì)應(yīng)相同的value值。

常用集合框架底層數(shù)據(jù)結(jié)構(gòu)　＊＊＊

  • List：

    1. ArrayList：數(shù)組
    2. LinkedList：雙線鏈表

  • Set：

    1. HashSet：底層基于HashMap實(shí)現(xiàn)，HashSet存入讀取元素的方式和HashMap中的Key是一致的。
    2. TreeSet：紅黑樹(shù)

  • Map：

    1. HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的， JDK1.8之后有數(shù)組+鏈表/紅黑樹(shù)組成，當(dāng)鏈表長(zhǎng)度大于8時(shí)，鏈表轉(zhuǎn)化為紅黑樹(shù)，當(dāng)長(zhǎng)度小于6時(shí)，從紅黑樹(shù)轉(zhuǎn)化為鏈表。這樣做的目的是能提高HashMap的性能，因?yàn)榧t黑樹(shù)的查找元素的時(shí)間復(fù)雜度遠(yuǎn)小于鏈表。
    2. HashTable：數(shù)組+鏈表
    3. TreeMap：紅黑樹(shù)

哪些集合類(lèi)是線程安全的？?。?/h3>
  • Vector：相當(dāng)于有同步機(jī)制的ArrayList
  • Stack：棧
  • HashTable
  • enumeration：枚舉

迭代器 Iterator 是什么?。?/h3>

Iterator 是 Java 迭代器最簡(jiǎn)單的實(shí)現(xiàn)，它不是一個(gè)集合，它是一種用于訪問(wèn)集合的方法，Iterator接口提供遍歷任何Collection的接口。

Java集合的快速失敗機(jī)制 “fail-fast”和安全失敗機(jī)制“fail-safe”是什么？?。?/h3>

  • 快速失敗

    Java的快速失敗機(jī)制是Java集合框架中的一種錯(cuò)誤檢測(cè)機(jī)制，當(dāng)多個(gè)線程同時(shí)對(duì)集合中的內(nèi)容進(jìn)行修改時(shí)可能就會(huì)拋出ConcurrentModificationException異常。其實(shí)不僅僅是在多線程狀態(tài)下，在單線程中用增強(qiáng)for循環(huán)中一邊遍歷集合一邊修改集合的元素也會(huì)拋出ConcurrentModificationException異常?？聪旅娲a

    public class Main{
    public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
        for(Integer i : list){
            list.remove(i);  //運(yùn)行時(shí)拋出ConcurrentModificationException異常
        }
    }
}

    正確的做法是用迭代器的remove()方法，便可正常運(yùn)行。

    public class Main{
    public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    Iterator<Integer> it = list.iterator();
        while(it.hasNext()){
            it.remove();
        }
    }
}

    造成這種情況的原因是什么？細(xì)心的同學(xué)可能已經(jīng)發(fā)現(xiàn)兩次調(diào)用的remove()方法不同，一個(gè)帶參數(shù)據(jù)，一個(gè)不帶參數(shù)，這個(gè)后面再說(shuō)，經(jīng)過(guò)查看ArrayList源碼，找到了拋出異常的代碼

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

    從上面代碼中可以看到如果modCount和expectedModCount這兩個(gè)變量不相等就會(huì)拋出ConcurrentModificationException異常。那這兩個(gè)變量又是什么呢？繼續(xù)看源碼

    protected transient int modCount = 0; //在AbstractList中定義的變量

    int expectedModCount = modCount;//在ArrayList中的內(nèi)部類(lèi)Itr中定義的變量

    從上面代碼可以看到，modCount初始值為0，而expectedModCount初始值等于modCount。也就是說(shuō)在遍歷的時(shí)候直接調(diào)用集合的remove()方法會(huì)導(dǎo)致modCount不等于expectedModCount進(jìn)而拋出ConcurrentModificationException異常，而使用迭代器的remove()方法則不會(huì)出現(xiàn)這種問(wèn)題。那么只能在看看remove()方法的源碼找找原因了

        public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    從上面代碼中可以看到只有modCount++了，而expectedModCount沒(méi)有操作，當(dāng)每一次迭代時(shí)，迭代器會(huì)比較expectedModCount和modCount的值是否相等，所以在調(diào)用remove()方法后，modCount不等于expectedModCount了，這時(shí)就了報(bào)ConcurrentModificationException異常。但用迭代器中remove()的方法為什么不拋異常呢？原來(lái)迭代器調(diào)用的remove()方法和上面的remove()方法不是同一個(gè)！迭代器調(diào)用的remove()方法長(zhǎng)這樣：

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

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;    //這行代碼保證了expectedModCount和modCount是相等的
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

    從上面代碼可以看到expectedModCount = modCount，所以迭代器的remove()方法保證了expectedModCount和modCount是相等的，進(jìn)而保證了在增強(qiáng)for循環(huán)中修改集合內(nèi)容不會(huì)報(bào)ConcurrentModificationException異常。

    上面介紹的只是單線程的情況，用迭代器調(diào)用remove()方法即可正常運(yùn)行，但如果是多線程會(huì)怎么樣呢？

    答案是在多線程的情況下即使用了迭代器調(diào)用remove()方法，還是會(huì)報(bào)ConcurrentModificationException異常。這又是為什么呢？還是要從expectedModCount和modCount這兩個(gè)變量入手分析，剛剛說(shuō)了modCount在AbstractList類(lèi)中定義，而expectedModCount在ArrayList內(nèi)部類(lèi)中定義，所以modCount是個(gè)共享變量而expectedModCount是屬于線程各自的。簡(jiǎn)單說(shuō)，線程1更新了modCount和屬于自己的expectedModCount，而在線程2看來(lái)只有modCount更新了，expectedModCount并未更新，所以會(huì)拋出ConcurrentModificationException異常。

  • 安全失敗

    采用安全失敗機(jī)制的集合容器，在遍歷時(shí)不是直接在集合內(nèi)容上訪問(wèn)的，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷。所以在遍歷過(guò)程中對(duì)原集合所作的修改并不能被迭代器檢測(cè)到，所以不會(huì)拋出ConcurrentModificationException異常。缺點(diǎn)是迭代器遍歷的是開(kāi)始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生了修改，迭代器是無(wú)法訪問(wèn)到修改后的內(nèi)容。java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用。

如何邊遍歷邊移除 Collection 中的元素？　＊＊＊

從上文“快速失敗機(jī)制”可知在遍歷集合時(shí)如果直接調(diào)用remove()方法會(huì)拋出ConcurrentModificationException異常，所以使用迭代器中調(diào)用remove()方法。

Array 和 ArrayList 有何區(qū)別？?。?/h3>
  • Array可以包含基本類(lèi)型和對(duì)象類(lèi)型，ArrayList只能包含對(duì)象類(lèi)型。
  • Array大小是固定的，ArrayList的大小是動(dòng)態(tài)變化的。(ArrayList的擴(kuò)容是個(gè)常見(jiàn)面試題)
  • 相比于Array，ArrayList有著更多的內(nèi)置方法，如addAll()，removeAll()。
  • 對(duì)于基本類(lèi)型數(shù)據(jù)，ArrayList 使用自動(dòng)裝箱來(lái)減少編碼工作量；而當(dāng)處理固定大小的基本數(shù)據(jù)類(lèi)型的時(shí)候，這種方式相對(duì)比較慢，這時(shí)候應(yīng)該使用Array。

comparable 和 comparator的區(qū)別？　＊＊

  • comparable接口出自java.lang包，可以理解為一個(gè)內(nèi)比較器，因?yàn)閷?shí)現(xiàn)了Comparable接口的類(lèi)可以和自己比較，要和其他實(shí)現(xiàn)了Comparable接口類(lèi)比較，可以使用compareTo(Object obj)方法。compareTo方法的返回值是int，有三種情況：
    1. 返回正整數(shù)（比較者大于被比較者）
    2. 返回0（比較者等于被比較者）
    3. 返回負(fù)整數(shù)（比較者小于被比較者）
  • comparator接口出自java.util 包，它有一個(gè)compare(Object obj1, Object obj2)方法用來(lái)排序，返回值同樣是int，有三種情況，和compareTo類(lèi)似。

它們之間的區(qū)別：很多包裝類(lèi)都實(shí)現(xiàn)了comparable接口，像Integer、String等，所以直接調(diào)用Collections.sort()直接可以使用。如果對(duì)類(lèi)里面自帶的自然排序不滿意，而又不能修改其源代碼的情況下，使用Comparator就比較合適。此外使用Comparator可以避免添加額外的代碼與我們的目標(biāo)類(lèi)耦合，同時(shí)可以定義多種排序規(guī)則，這一點(diǎn)是Comparable接口沒(méi)法做到的，從靈活性和擴(kuò)展性講Comparator更優(yōu)，故在面對(duì)自定義排序的需求時(shí)，可以?xún)?yōu)先考慮使用Comparator接口。

Collection 和 Collections 有什么區(qū)別？?。?/h3>
  • Collection 是一個(gè)集合接口。它提供了對(duì)集合對(duì)象進(jìn)行基本操作的通用接口方法。
  • Collections 是一個(gè)包裝類(lèi)。它包含有各種有關(guān)集合操作的靜態(tài)多態(tài)方法，例如常用的sort()方法。此類(lèi)不能實(shí)例化，就像一個(gè)工具類(lèi)，服務(wù)于Java的Collection框架。

List集合

遍歷一個(gè) List 有哪些不同的方式？?。?/h4>

先說(shuō)一下常見(jiàn)的元素在內(nèi)存中的存儲(chǔ)方式，主要有兩種：

  1. 順序存儲(chǔ)（Random Access）：相鄰的數(shù)據(jù)元素在內(nèi)存中的位置也是相鄰的，可以根據(jù)元素的位置（如ArrayList中的下表）讀取元素。
  2. 鏈?zhǔn)酱鎯?chǔ)（Sequential Access）：每個(gè)數(shù)據(jù)元素包含它下一個(gè)元素的內(nèi)存地址，在內(nèi)存中不要求相鄰。例如LinkedList。

主要的遍歷方式主要有三種：

  1. for循環(huán)遍歷：遍歷者自己在集合外部維護(hù)一個(gè)計(jì)數(shù)器，依次讀取每一個(gè)位置的元素。
  2. Iterator遍歷：基于順序存儲(chǔ)集合的Iterator可以直接按位置訪問(wèn)數(shù)據(jù)?；阪?zhǔn)酱鎯?chǔ)集合的Iterator，需要保存當(dāng)前遍歷的位置，然后根據(jù)當(dāng)前位置來(lái)向前或者向后移動(dòng)指針。
  3. foreach遍歷：foreach 內(nèi)部也是采用了Iterator的方式實(shí)現(xiàn)，但使用時(shí)不需要顯示地聲明Iterator。

那么對(duì)于以上三種遍歷方式應(yīng)該如何選取呢？

在Java集合框架中，提供了一個(gè)RandomAccess接口，該接口沒(méi)有方法，只是一個(gè)標(biāo)記。通常用來(lái)標(biāo)記List的實(shí)現(xiàn)是否支持RandomAccess。所以在遍歷時(shí)，可以先判斷是否支持RandomAccess（list instanceof RandomAccess），如果支持可用 for循環(huán)遍歷，否則建議用Iterator或 foreach遍歷。

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

先說(shuō)下結(jié)論，一般面試時(shí)需要記住，ArrayList的初始容量為10，擴(kuò)容時(shí)對(duì)是舊的容量值加上舊的容量數(shù)值進(jìn)行右移一位（位運(yùn)算，相當(dāng)于除以2，位運(yùn)算的效率更高），所以每次擴(kuò)容都是舊的容量的1.5倍。

具體的實(shí)現(xiàn)大家可查看下ArrayList的源碼。

ArrayList 和 LinkedList 的區(qū)別是什么？?。?/h4>
  • 是否線程安全：ArrayList和LinkedList都是不保證線程安全的
  • 底層實(shí)現(xiàn)：ArrayList的底層實(shí)現(xiàn)是數(shù)組，LinkedList的底層是雙向鏈表。
  • 內(nèi)存占用：ArrayList會(huì)存在一定的空間浪費(fèi)，因?yàn)槊看螖U(kuò)容都是之前的1.5倍，而LinkedList中的每個(gè)元素要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)，所以對(duì)于每個(gè)元素的存儲(chǔ)都要比ArrayList花費(fèi)更多的空間。
  • 應(yīng)用場(chǎng)景：ArrayList的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，所以在插入和刪除元素時(shí)的時(shí)間復(fù)雜度都會(huì)收到位置的影響，平均時(shí)間復(fù)雜度為o(n)，在讀取元素的時(shí)候可以根據(jù)下標(biāo)直接查找到元素，不受位置的影響，平均時(shí)間復(fù)雜度為o(1)，所以ArrayList更加適用于多讀，少增刪的場(chǎng)景。LinkedList的底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，所以插入和刪除元素不受位置的影響，平均時(shí)間復(fù)雜度為o(1)，如果是在指定位置插入則是o(n)，因?yàn)樵诓迦胫靶枰日业皆撐恢茫x取元素的平均時(shí)間復(fù)雜度為o(n)。所以LinkedList更加適用于多增刪，少讀寫(xiě)的場(chǎng)景。

ArrayList 和 Vector 的區(qū)別是什么？　＊＊＊

  • 相同點(diǎn)

    1. 都實(shí)現(xiàn)了List接口
    2. 底層數(shù)據(jù)結(jié)構(gòu)都是數(shù)組

  • 不同點(diǎn)

    1. 線程安全：Vector使用了Synchronized來(lái)實(shí)現(xiàn)線程同步，所以是線程安全的，而ArrayList是線程不安全的。
    2. 性能：由于Vector使用了Synchronized進(jìn)行加鎖，所以性能不如ArrayList。
    3. 擴(kuò)容：ArrayList和Vector都會(huì)根據(jù)需要?jiǎng)討B(tài)的調(diào)整容量，但是ArrayList每次擴(kuò)容為舊容量的1.5倍，而Vector每次擴(kuò)容為舊容量的2倍。

簡(jiǎn)述 ArrayList、Vector、LinkedList 的存儲(chǔ)性能和特性？?。?/h4>
  • ArrayList底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，對(duì)元素的讀取速度快，而增刪數(shù)據(jù)慢，線程不安全。
  • LinkedList底層為雙向鏈表，對(duì)元素的增刪數(shù)據(jù)快，讀取慢，線程不安全。
  • Vector的底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，用Synchronized來(lái)保證線程安全，性能較差，但線程安全。

Set集合

說(shuō)一下 HashSet 的實(shí)現(xiàn)原理?。?/h4>

HashSet的底層是HashMap，默認(rèn)構(gòu)造函數(shù)是構(gòu)建一個(gè)初始容量為16，負(fù)載因子為0.75 的HashMap。HashSet的值存放于HashMap的key上，HashMap的value統(tǒng)一為PRESENT。

HashSet如何檢查重復(fù)？（HashSet是如何保證數(shù)據(jù)不可重復(fù)的？）　＊＊＊

這里面涉及到了HasCode()和equals()兩個(gè)方法。

  • equals()

    先看下String類(lèi)中重寫(xiě)的equals方法。

        public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

    從源碼中可以看到：

    1. equals方法首先比較的是內(nèi)存地址，如果內(nèi)存地址相同，直接返回true；如果內(nèi)存地址不同，再比較對(duì)象的類(lèi)型，類(lèi)型不同直接返回false；類(lèi)型相同，再比較值是否相同；值相同返回true，值不同返回false。總結(jié)一下，equals會(huì)比較內(nèi)存地址、對(duì)象類(lèi)型、以及值，內(nèi)存地址相同，equals一定返回true；對(duì)象類(lèi)型和值相同，equals方法一定返回true。
    2. 如果沒(méi)有重寫(xiě)equals方法，那么equals和==的作用相同，比較的是對(duì)象的地址值。

  • hashCode

    hashCode方法返回對(duì)象的散列碼，返回值是int類(lèi)型的散列碼。散列碼的作用是確定該對(duì)象在哈希表中的索引位置。

    關(guān)于hashCode有一些約定：

    1. 兩個(gè)對(duì)象相等，則hashCode一定相同。
    2. 兩個(gè)對(duì)象有相同的hashCode值，它們不一定相等。
    3. hashCode()方法默認(rèn)是對(duì)堆上的對(duì)象產(chǎn)生獨(dú)特值，如果沒(méi)有重寫(xiě)hashCode()方法，則該類(lèi)的兩個(gè)對(duì)象的hashCode值肯定不同

介紹完equals()方法和hashCode()方法，繼續(xù)說(shuō)下HashSet是如何檢查重復(fù)的。

HashSet的特點(diǎn)是存儲(chǔ)元素時(shí)無(wú)序且唯一，在向HashSet中添加對(duì)象時(shí)，首相會(huì)計(jì)算對(duì)象的HashCode值來(lái)確定對(duì)象的存儲(chǔ)位置，如果該位置沒(méi)有其他對(duì)象，直接將該對(duì)象添加到該位置；如果該存儲(chǔ)位置有存儲(chǔ)其他對(duì)象（新添加的對(duì)象和該存儲(chǔ)位置的對(duì)象的HashCode值相同），調(diào)用equals方法判斷兩個(gè)對(duì)象是否相同，如果相同，則添加對(duì)象失敗，如果不相同，則會(huì)將該對(duì)象重新散列到其他位置。

HashSet與HashMap的區(qū)別?。?/h4>
HashMap HashSet
實(shí)現(xiàn)了Map接口 實(shí)現(xiàn)了Set接口
存儲(chǔ)鍵值對(duì) 存儲(chǔ)對(duì)象
key唯一，value不唯一 存儲(chǔ)對(duì)象唯一
HashMap使用鍵（Key）計(jì)算Hashcode HashSet使用成員對(duì)象來(lái)計(jì)算hashcode值
速度相對(duì)較快 速度相對(duì)較慢

Map集合

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實(shí)現(xiàn)?。?/h4>
  • JDK1.7的底層數(shù)據(jù)結(jié)構(gòu)(數(shù)組+鏈表)
在這里插入圖片描述
  • JDK1.8的底層數(shù)據(jù)結(jié)構(gòu)(數(shù)組+鏈表)
在這里插入圖片描述

  • JDK1.7的Hash函數(shù)

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

  • JDK1.8的Hash函數(shù)

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

    JDK1.8的函數(shù)經(jīng)過(guò)了一次異或一次位運(yùn)算一共兩次擾動(dòng)，而JDK1.7經(jīng)過(guò)了四次位運(yùn)算五次異或一共九次擾動(dòng)。這里簡(jiǎn)單解釋下JDK1.8的hash函數(shù)，面試經(jīng)常問(wèn)這個(gè)，兩次擾動(dòng)分別是key.hashCode()與key.hashCode()右移16位進(jìn)行異或。這樣做的目的是，高16位不變，低16位與高16位進(jìn)行異或操作，進(jìn)而減少碰撞的發(fā)生，高低Bit都參與到Hash的計(jì)算。如何不進(jìn)行擾動(dòng)處理，因?yàn)閔ash值有32位，直接對(duì)數(shù)組的長(zhǎng)度求余，起作用只是hash值的幾個(gè)低位。

HashMap在JDK1.7和JDK1.8中有哪些不同點(diǎn)：

JDK1.7 JDK1.8 JDK1.8的優(yōu)勢(shì)
底層結(jié)構(gòu) 數(shù)組+鏈表 數(shù)組+鏈表/紅黑樹(shù)(鏈表大于8) 避免單條鏈表過(guò)長(zhǎng)而影響查詢(xún)效率，提高查詢(xún)效率
hash值計(jì)算方式 9次擾動(dòng) = 4次位運(yùn)算 + 5次異或運(yùn)算 2次擾動(dòng) = 1次位運(yùn)算 + 1次異或運(yùn)算 可以均勻地把之前的沖突的節(jié)點(diǎn)分散到新的桶（具體細(xì)節(jié)見(jiàn)下面擴(kuò)容部分）
插入數(shù)據(jù)方式 頭插法（先講原位置的數(shù)據(jù)移到后1位，再插入數(shù)據(jù)到該位置） 尾插法（直接插入到鏈表尾部/紅黑樹(shù)） 解決多線程造成死循環(huán)地問(wèn)題
擴(kuò)容后存儲(chǔ)位置的計(jì)算方式 重新進(jìn)行hash計(jì)算 原位置或原位置+舊容量 省去了重新計(jì)算hash值的時(shí)間

HashMap 的長(zhǎng)度為什么是2的冪次方　＊＊＊

因?yàn)?code>HashMap是通過(guò)key的hash值來(lái)確定存儲(chǔ)的位置，但Hash值的范圍是-2147483648到2147483647，不可能建立一個(gè)這么大的數(shù)組來(lái)覆蓋所有hash值。所以在計(jì)算完hash值后會(huì)對(duì)數(shù)組的長(zhǎng)度進(jìn)行取余操作，如果數(shù)組的長(zhǎng)度是2的冪次方，(length - 1)&hash等同于hash%length，可以用(length - 1)&hash這種位運(yùn)算來(lái)代替%取余的操作進(jìn)而提高性能。

HashMap的put方法的具體流程？?。?/h4>

HashMap的主要流程可以看下面這個(gè)流程圖，邏輯非常清晰。

在這里插入圖片描述

HashMap的擴(kuò)容操作是怎么實(shí)現(xiàn)的？?。?/h4>

  • 初始值為16，負(fù)載因子為0.75，閾值為負(fù)載因子*容量

  • resize()方法是在hashmap中的鍵值對(duì)大于閥值時(shí)或者初始化時(shí)，就調(diào)用resize()方法進(jìn)行擴(kuò)容。

  • 每次擴(kuò)容，容量都是之前的兩倍

  • 擴(kuò)容時(shí)有個(gè)判斷e.hash & oldCap是否為零，也就是相當(dāng)于hash值對(duì)數(shù)組長(zhǎng)度的取余操作，若等于0，則位置不變，若等于1，位置變?yōu)樵恢眉优f容量。

    源碼如下：

    final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) { //如果舊容量已經(jīng)超過(guò)最大值，閾值為整數(shù)最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;  //沒(méi)有超過(guò)最大值就變?yōu)樵瓉?lái)的2倍
    }
    else if (oldThr > 0) 
        newCap = oldThr;

    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    Node<K,V> loHead = null, loTail = null;//loHead,loTail 代表擴(kuò)容后在原位置
                    Node<K,V> hiHead = null, hiTail = null;//hiHead,hiTail 代表擴(kuò)容后在原位置+舊容量
                    Node<K,V> next;
                    do {             
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { //判斷是否為零，為零賦值到loHead，不為零賦值到hiHead
                            if (loTail == null)
                                loHead = e;
                            else                                
                                loTail.next = e;
                            loTail = e;                           
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;   //loHead放在原位置
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;  //hiHead放在原位置+舊容量
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap默認(rèn)加載因子為什么選擇0.75？

這個(gè)主要是考慮空間利用率和查詢(xún)成本的一個(gè)折中。如果加載因子過(guò)高，空間利用率提高，但是會(huì)使得哈希沖突的概率增加；如果加載因子過(guò)低，會(huì)頻繁擴(kuò)容，哈希沖突概率降低，但是會(huì)使得空間利用率變低。具體為什么是0.75，不是0.74或0.76，這是一個(gè)基于數(shù)學(xué)分析（泊松分布）和行業(yè)規(guī)定一起得到的一個(gè)結(jié)論。

為什么要將鏈表中轉(zhuǎn)紅黑樹(shù)的閾值設(shè)為8？為什么不一開(kāi)始直接使用紅黑樹(shù)？

可能有很多人會(huì)問(wèn)，既然紅黑樹(shù)性能這么好，為什么不一開(kāi)始直接使用紅黑樹(shù)，而是先用鏈表，鏈表長(zhǎng)度大于8時(shí)，才轉(zhuǎn)換為紅紅黑樹(shù)。

  • 因?yàn)榧t黑樹(shù)的節(jié)點(diǎn)所占的空間是普通鏈表節(jié)點(diǎn)的兩倍，但查找的時(shí)間復(fù)雜度低，所以只有當(dāng)節(jié)點(diǎn)特別多時(shí)，紅黑樹(shù)的優(yōu)點(diǎn)才能體現(xiàn)出來(lái)。至于為什么是8，是通過(guò)數(shù)據(jù)分析統(tǒng)計(jì)出來(lái)的一個(gè)結(jié)果，鏈表長(zhǎng)度到達(dá)8的概率是很低的，綜合鏈表和紅黑樹(shù)的性能優(yōu)缺點(diǎn)考慮將大于8的鏈表轉(zhuǎn)化為紅黑樹(shù)。
  • 鏈表轉(zhuǎn)化為紅黑樹(shù)除了鏈表長(zhǎng)度大于8，還要HashMap中的數(shù)組長(zhǎng)度大于64。也就是如果HashMap長(zhǎng)度小于64，鏈表長(zhǎng)度大于8是不會(huì)轉(zhuǎn)化為紅黑樹(shù)的，而是直接擴(kuò)容。

HashMap是怎么解決哈希沖突的？?。?/h4>

哈希沖突：hashMap在存儲(chǔ)元素時(shí)會(huì)先計(jì)算key的hash值來(lái)確定存儲(chǔ)位置，因?yàn)?code>key的hash值計(jì)算最后有個(gè)對(duì)數(shù)組長(zhǎng)度取余的操作，所以即使不同的key也可能計(jì)算出相同的hash值，這樣就引起了hash沖突。hashMap的底層結(jié)構(gòu)中的鏈表/紅黑樹(shù)就是用來(lái)解決這個(gè)問(wèn)題的。

HashMap中的哈希沖突解決方式可以主要從三方面考慮（以JDK1.8為背景）

  • 拉鏈法

    HasMap中的數(shù)據(jù)結(jié)構(gòu)為數(shù)組+鏈表/紅黑樹(shù)，當(dāng)不同的key計(jì)算出的hash值相同時(shí)，就用鏈表的形式將Node結(jié)點(diǎn)（沖突的key及key對(duì)應(yīng)的value）掛在數(shù)組后面。

  • hash函數(shù)

    key的hash值經(jīng)過(guò)兩次擾動(dòng)，key的hashCode值與key的hashCode值的右移16位進(jìn)行異或，然后對(duì)數(shù)組的長(zhǎng)度取余（實(shí)際為了提高性能用的是位運(yùn)算，但目的和取余一樣），這樣做可以讓hashCode取值出的高位也參與運(yùn)算，進(jìn)一步降低hash沖突的概率，使得數(shù)據(jù)分布更平均。

  • 紅黑樹(shù)

    在拉鏈法中，如果hash沖突特別嚴(yán)重，則會(huì)導(dǎo)致數(shù)組上掛的鏈表長(zhǎng)度過(guò)長(zhǎng)，性能變差，因此在鏈表長(zhǎng)度大于8時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，可以提高遍歷鏈表的速度。

HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標(biāo)？?。?/h4>

hashCode()處理后的哈希值范圍太大，不可能在內(nèi)存建立這么大的數(shù)組。

能否使用任何類(lèi)作為 Map 的 key？?。?/h4>

可以，但要注意以下兩點(diǎn)：

  • 如果類(lèi)重寫(xiě)了 equals()方法，也應(yīng)該重寫(xiě)hashCode()方法。
  • 最好定義key類(lèi)是不可變的，這樣key對(duì)應(yīng)的hashCode()值可以被緩存起來(lái)，性能更好，這也是為什么String特別適合作為HashMap的key。

為什么HashMap中String、Integer這樣的包裝類(lèi)適合作為Key？?。?/h4>
  • 這些包裝類(lèi)都是final修飾，是不可變性的， 保證了key的不可更改性，不會(huì)出現(xiàn)放入和獲取時(shí)哈希值不同的情況。
  • 它們內(nèi)部已經(jīng)重寫(xiě)過(guò)hashcode(),equal()等方法。

如果使用Object作為HashMap的Key，應(yīng)該怎么辦呢？　＊＊

  • 重寫(xiě)hashCode()方法，因?yàn)樾枰?jì)算hash值確定存儲(chǔ)位置
  • 重寫(xiě)equals()方法，因?yàn)樾枰ＷCkey的唯一性。

HashMap 多線程導(dǎo)致死循環(huán)問(wèn)題?。?/h4>

由于JDK1.7的hashMap遇到hash沖突采用的是頭插法，在多線程情況下會(huì)存在死循環(huán)問(wèn)題，但JDK1.8已經(jīng)改成了尾插法，不存在這個(gè)問(wèn)題了。但需要注意的是JDK1.8中的HashMap仍然是不安全的，在多線程情況下使用仍然會(huì)出現(xiàn)線程安全問(wèn)題。基本上面試時(shí)說(shuō)到這里既可以了，具體流程用口述是很難說(shuō)清的，感興趣的可以看這篇文章。HASHMAP的死循環(huán)

ConcurrentHashMap 底層具體實(shí)現(xiàn)知道嗎？　＊＊

  • JDK1.7

    在JDK1.7中，ConcurrentHashMap采用Segment數(shù)組 + HashEntry數(shù)組的方式進(jìn)行實(shí)現(xiàn)。Segment實(shí)現(xiàn)了ReentrantLock，所以Segment有鎖的性質(zhì)，HashEntry用于存儲(chǔ)鍵值對(duì)。一個(gè)ConcurrentHashMap包含著一個(gè)Segment數(shù)組，一個(gè)Segment包含著一個(gè)HashEntry數(shù)組，HashEntry是一個(gè)鏈表結(jié)構(gòu)，如果要獲取HashEntry中的元素，要先獲得Segment的鎖。

在這里插入圖片描述

  • JDK1.8

    在JDK1.8中，不在是Segment+HashEntry的結(jié)構(gòu)了，而是和HashMap類(lèi)似的結(jié)構(gòu)，Node數(shù)組+鏈表/紅黑樹(shù)，采用CAS+synchronized來(lái)保證線程安全。當(dāng)鏈表長(zhǎng)度大于8，鏈表轉(zhuǎn)化為紅黑樹(shù)。在JDK1.8中synchronized只鎖鏈表或紅黑樹(shù)的頭節(jié)點(diǎn)，是一種相比于segment更為細(xì)粒度的鎖，鎖的競(jìng)爭(zhēng)變小，所以效率更高。

在這里插入圖片描述

總結(jié)一下：

  • JDK1.7底層是ReentrantLock+Segment+HashEntry，JDK1.8底層是synchronized+CAS+鏈表/紅黑樹(shù)
  • JDK1.7采用的是分段鎖，同時(shí)鎖住幾個(gè)HashEntry，JDK1.8鎖的是Node節(jié)點(diǎn)，只要沒(méi)有發(fā)生哈希沖突，就不會(huì)產(chǎn)生鎖的競(jìng)爭(zhēng)。所以JDK1.8相比于JDK1.7提供了一種粒度更小的鎖，減少了鎖的競(jìng)爭(zhēng)，提高了ConcurrentHashMap的并發(fā)能力。

HashTable的底層實(shí)現(xiàn)知道嗎？

HashTable的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表，鏈表主要是為了解決哈希沖突，并且整個(gè)數(shù)組都是synchronized修飾的，所以HashTable是線程安全的，但鎖的粒度太大，鎖的競(jìng)爭(zhēng)非常激烈，效率很低。

在這里插入圖片描述

HashMap、ConcurrentHashMap及Hashtable 的區(qū)別?。?/h4>
HashMap(JDK1.8) ConcurrentHashMap(JDK1.8) Hashtable
底層實(shí)現(xiàn) 數(shù)組+鏈表/紅黑樹(shù) 數(shù)組+鏈表/紅黑樹(shù) 數(shù)組+鏈表
線程安全 不安全 安全(Synchronized修飾Node節(jié)點(diǎn)) 安全(Synchronized修飾整個(gè)表)
效率 高 較高 低
擴(kuò)容 初始16，每次擴(kuò)容成2n 初始16，每次擴(kuò)容成2n 初始11，每次擴(kuò)容成2n+1
是否支持Null key和Null Value 可以有一個(gè)Null key，Null Value多個(gè) 不支持 不支持

Java集合的常用方法　＊＊

這些常用方法是需要背下來(lái)的，雖然面試用不上，但是筆試或者面試寫(xiě)算法題時(shí)會(huì)經(jīng)常用到。

Collection常用方法

方法
booean add(E e) 在集合末尾添加元素
boolean remove(Object o) 若本類(lèi)集中有值與o的值相等的元素，移除該元素并返回true
void clear() 清除本類(lèi)中所有元素
boolean contains(Object o) 判斷集合中是否包含該元素
boolean isEmpty() 判斷集合是否為空
int size() 返回集合中元素的個(gè)數(shù)
boolean addAll(Collection c) 將一個(gè)集合中c中的所有元素添加到另一個(gè)集合中
Object[] toArray() 返回一個(gè)包含本集所有元素的數(shù)組，數(shù)組類(lèi)型為Object[]
`boolean equals(Object c)`` 判斷元素是否相等
int hashCode() 返回元素的hash值

List特有方法

方法
void add(int index,Object obj) 在指定位置添加元素
Object remove(int index) 刪除指定元素并返回
Object set(int index,Object obj) 把指定索引位置的元素更改為指定值并返回修改前的值
int indexOf(Object o) 返回指定元素在集合中第一次出現(xiàn)的索引
Object get(int index) 返回指定位置的元素
List subList(int fromIndex,int toIndex) 截取集合(左閉右開(kāi))

LinkedList特有方法

方法
addFirst() 在頭部添加元素
addLast() 在尾部添加元素
removeFirst() 在頭部刪除元素
removeLat() 在尾部刪除元素
getFirst() 獲取頭部元素
getLast() 獲取尾部元素

Map

方法
void clear() 清除集合內(nèi)的元素
boolean containsKey(Object key) 查詢(xún)Map中是否包含指定key,如果包含則返回true
Set entrySet() 返回Map中所包含的鍵值對(duì)所組成的Set集合，每個(gè)集合元素都是Map.Entry的對(duì)象
Object get(Object key) 返回key指定的value,若Map中不包含key返回null
boolean isEmpty() 查詢(xún)Map是否為空，若為空返回true
Set keySet() 返回Map中所有key所組成的集合
Object put(Object key,Object value) 添加一個(gè)鍵值對(duì)，如果已有一個(gè)相同的key,則新的鍵值對(duì)會(huì)覆蓋舊的鍵值對(duì),返回值為覆蓋前的value值，否則為null
void putAll(Map m) 將制定Map中的鍵值對(duì)復(fù)制到Map中
Object remove(Object key) 刪除指定key所對(duì)應(yīng)的鍵值對(duì)，返回所關(guān)聯(lián)的value,如果key不存在返回null
int size() 返回Map里面的鍵值對(duì)的個(gè)數(shù)
Collection values() 返回Map里所有values所組成的Collection
boolean containsValue ( Object value) 判斷映像中是否存在值 value

Stack

方法
boolean empty() 測(cè)試堆棧是否為空。
E peek() 查看堆棧頂部的對(duì)象，但不從堆棧中移除它。
E pop() 移除堆棧頂部的對(duì)象，并作為此函數(shù)的值返回該對(duì)象。
E push(E item) 把項(xiàng)壓入堆棧頂部。
int search(Object o) 返回對(duì)象在堆棧中的位置，以 1 為基數(shù)。

Queue

方法
boolean add(E e) 將指定元素插入到隊(duì)列的尾部（隊(duì)列滿了話，會(huì)拋出異常）
boolean offer(E e) 將指定元素插入此隊(duì)列的尾部(隊(duì)列滿了話，會(huì)返回false)
E remove() 返回取隊(duì)列頭部的元素，并刪除該元素(如果隊(duì)列為空，則拋出異常)
E poll() 返回隊(duì)列頭部的元素，并刪除該元素(如果隊(duì)列為空，則返回null)
E element() 返回隊(duì)列頭部的元素,不刪除該元素(如果隊(duì)列為空，則拋出異常)
E peek() 返回隊(duì)列頭部的元素，不刪除該元素(如果隊(duì)列為空，則返回null)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容