前言

工作加實(shí)習(xí)兩年了碍脏，想總結(jié)和記錄這幾天的面試重點(diǎn)和題目，盡量把答案寫出來(lái)卖擅，由于大多網(wǎng)上搜的或者查閱書(shū)籍鸣奔，如有錯(cuò)誤還忘指出。
大多數(shù)好的公司面的比較有深度惩阶，主要還是要靠自學(xué)和積累挎狸，文章中答案都不深度討論，后續(xù)會(huì)細(xì)細(xì)分析断楷。

基礎(chǔ)篇

集合和多線程是Java基礎(chǔ)的重中之重

1. Map 有多少個(gè)實(shí)現(xiàn)類锨匆？

Java自帶了各種 Map 類，這些 Map 類可歸為三種類型：

• 通用 Map冬筒，用于在應(yīng)用程序中管理映射恐锣，通常在 Java.util 程序包中實(shí)現(xiàn)：HashMap Hashtable Properties LinkedHashMap IdentityHashMap TreeMap WeakHashMap ConcurrentHashMap
• 專用 Map，你通常不必親自創(chuàng)建此類 Map舞痰，而是通過(guò)某些其他類對(duì)其進(jìn)行訪問(wèn)：java.util.Attributes javax.print.attribute.standard.PrinterStateReasons java.security.Provider java.awt.RenderingHints javax.swing.UIDefaults
• 一個(gè)用于幫助實(shí)現(xiàn)你自己的 Map 類的抽象類：AbstractMap

不用記住所有的侥蒙，根據(jù)自己比較常用和了解的來(lái)回答就可以。

2. HashMap 是不是有序的匀奏？有序的 Map 類是哪個(gè)？Hashtable 是如何實(shí)現(xiàn)線程安全的学搜？

HashMap 不是有序的娃善，下一題通過(guò)源碼來(lái)解析HashMap的結(jié)構(gòu)。

LinkedHashMap 是有序的瑞佩，并且可以分為按照插入順序和訪問(wèn)順序的鏈表聚磺，默認(rèn)是按插入順序排序的。在創(chuàng)建的時(shí)候如果是new LinkedHashMap<String, String>(16,0.75f,true)炬丸，true就代表按照訪問(wèn)順序排序瘫寝，那么調(diào)用 get 方法后蜒蕾，會(huì)將這次訪問(wèn)的元素移至尾部，不斷訪問(wèn)可以形成按訪問(wèn)順序排序的鏈表焕阿。

根據(jù)源碼可以看到咪啡，Hashtable 中的方法都加上了 synchronized 關(guān)鍵字。

3. HashMap 的實(shí)現(xiàn)原理以及如何擴(kuò)容暮屡？

眾所周知 HashMap 是數(shù)組和鏈表的結(jié)合撤摸，如下圖所示:

map.png

左邊是連續(xù)的數(shù)組，我們可以稱為哈希桶褒纲，右邊連接著鏈表准夷。

具體如何實(shí)現(xiàn)我們來(lái)看源碼，在 HashMap 定義中有一個(gè)屬性Entry<K,V>[] table屬性莺掠，所以可以看到 HashMap 的實(shí)質(zhì)是一個(gè) Entry 數(shù)組衫嵌。
看 HashMap 的初始化：

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];  //初始化
        initHashSeedAsNeeded(capacity);
    }

我們看到table = new Entry[capacity]這行，這行就是 HashMap 的初始化彻秆。capacity 是容量楔绞，容量的默認(rèn)大小是16，最大不能超過(guò)2的30次方掖棉。然后我們來(lái)看 put() 方法：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);  //計(jì)算出key的hash值
        int i = indexFor(hash, table.length);  //通過(guò)容量來(lái)找到key對(duì)應(yīng)哈希桶的位置
         //在對(duì)應(yīng)的哈希桶上的鏈表查找是否有相同的key墓律，如果有則覆蓋
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;
            //這里解釋了map就是根據(jù)對(duì)象的hashcode和equals方法來(lái)決定有沒(méi)有重復(fù)的key
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //添加一個(gè)鍵值對(duì)
        addEntry(hash, key, value, i);
        return null;
    }

可以看到，addEntry 才是真正在添加一個(gè)鍵值對(duì)幔亥，addEntry 方法中有擴(kuò)容的操作耻讽，這個(gè)等會(huì)兒再看，所以我們直接看添加的鍵值對(duì)的操作：

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];    //拿到哈希桶中存放的地址
        //新建的entry指向剛剛那個(gè)地址帕棉，并且哈希桶指向新建的entry
        table[bucketIndex] = new Entry<>(hash, key, value, e);  
        size++;
}

以上注釋就說(shuō)明當(dāng)加入一個(gè)新鍵值對(duì)的時(shí)候针肥，新的鍵值對(duì)找到對(duì)應(yīng)的哈希桶之后就插入到鏈表的頭結(jié)點(diǎn)上。

接下來(lái)看擴(kuò)容香伴，我們說(shuō)到數(shù)組有容量慰枕，默認(rèn)16，在 HashMap 的定義中還有負(fù)載因子即纲，默認(rèn)為0.75具帮，一旦數(shù)組存放的元素超過(guò)16*0.75=12個(gè)就需要增大哈希桶。我們看 addEntry方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);  //如果是默認(rèn)16低斋，則增大到32
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

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

接下來(lái)看 resize 方法：

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];  //創(chuàng)建新的數(shù)組蜂厅，大小為原來(lái)數(shù)組的兩倍
        //將所有元素按照存放規(guī)則重新存放到新的數(shù)組中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));  
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

每次擴(kuò)容都會(huì)重新計(jì)算所有 key 的哈希值以及將所有元素重排，比較浪費(fèi)資源膊畴，所以在創(chuàng)建 HashMap 時(shí)掘猿，我們盡量初始化適當(dāng)?shù)娜萘恳詼p少元素重排帶來(lái)的開(kāi)支。

4. List的實(shí)現(xiàn)類以及區(qū)別唇跨？

• ArrayList 是最常用的 List 實(shí)現(xiàn)類稠通，內(nèi)部是通過(guò)數(shù)組實(shí)現(xiàn)的衬衬，它允許對(duì)元素進(jìn)行快速隨機(jī)訪問(wèn)。數(shù)組的缺點(diǎn)是每個(gè)元素之間不能有間隔改橘，當(dāng)數(shù)組大小不滿足時(shí)需要增加存儲(chǔ)能力滋尉，就要將已經(jīng)有數(shù)組的數(shù)據(jù)復(fù)制到新的存儲(chǔ)空間中。當(dāng)從 ArrayList 的中間位置插入或者刪除元素時(shí)唧龄，需要對(duì)數(shù)組進(jìn)行復(fù)制兼砖、移動(dòng)、代價(jià)比較高既棺。因此讽挟，它適合隨機(jī)查找和遍歷，不適合插入和刪除丸冕，允許空元素耽梅。
• LinkedList 是用鏈表結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的，很適合數(shù)據(jù)的動(dòng)態(tài)插入和刪除胖烛，隨機(jī)訪問(wèn)和遍歷速度比較慢眼姐。另外，接口中沒(méi)有定義的方法get佩番、remove众旗、insertList，專門用于操作表頭和表尾元素趟畏，可以當(dāng)作堆棧贡歧、隊(duì)列和雙向隊(duì)列使用。LinkedList 沒(méi)有同步方法赋秀。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)List利朵，則必須自己實(shí)現(xiàn)訪問(wèn)同步，一種解決方法是在創(chuàng)建List時(shí)構(gòu)造一個(gè)同步的List:
  List list = Collections.synchronizedList(new LinkedList())
• 應(yīng)該避免使用 Vector猎莲，它只存在于支持遺留代碼的類庫(kù)中绍弟。
• CopyOnWriteArrayList 是 List 的一個(gè)特殊實(shí)現(xiàn)，專門用于并發(fā)編程著洼。

5. 如何實(shí)現(xiàn)線程并發(fā)樟遣？

用 Lock 接口的實(shí)現(xiàn)類或者 synchroized 關(guān)鍵字。

6. Lock 類比起 synchroized身笤，優(yōu)勢(shì)在哪里豹悬？

Lock 接口是 JavaSE5 引入的新接口，最大的優(yōu)勢(shì)是為讀和寫分別提供了鎖展鸡。
延伸：如果需要實(shí)現(xiàn)一個(gè)高效的緩存，它允許多個(gè)用戶讀埃难，但只允許一個(gè)用戶寫莹弊，以此來(lái)保證它的完整性涤久，如何實(shí)現(xiàn)?
讀寫鎖 ReadWriteLock 擁有更加強(qiáng)大的功能，它可以分為讀鎖和解鎖忍弛。讀鎖可以允許多個(gè)進(jìn)行讀操作的線程同時(shí)進(jìn)入响迂，但不允許寫進(jìn)程進(jìn)入；寫鎖只允許一個(gè)寫進(jìn)程進(jìn)入细疚，在這期間任何進(jìn)程都不能再進(jìn)入蔗彤。

要注意的是每個(gè)讀寫鎖都有掛鎖和解鎖，最好將每一對(duì)掛鎖和解鎖操作都用 try疯兼、finally 來(lái)套入中間的代碼然遏，這樣就會(huì)防止因異常發(fā)生而造成死鎖的情況。

下面是一段示例：

import java.util.Random;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class ReadWriteLockTest {
    //用于關(guān)閉線程
    public volatile static boolean blag= true;
    public static void main(String[] args) throws InterruptedException {
        final TheData myData = new TheData();  //各線程的共享資源
        for (int i = 0; i < 3; i++) {   //開(kāi)啟三個(gè)讀線程
            new Thread(new Runnable() {
                @Override
                public void run() {
                    while(blag){
                        myData.get();
                    }
                }
            }).start();
        }
        for (int i = 0; i < 3; i++) {   //開(kāi)啟三個(gè)寫線程
            new Thread(new Runnable() {
                @Override
                public void run() {
                    while (blag) {
                        myData.put(new Random().nextInt(10000));
                    }
                }
            }).start();
        }
        Thread.sleep(5000);
        BLAG = false;
    }

}
/**
 * 模擬同步讀寫
 * @author hedy
 *
 */
class TheData{
    private Object data=null;
    private ReadWriteLock rwl = new ReentrantReadWriteLock();
    public void get(){
        rwl.readLock().lock();   //讀鎖開(kāi)啟吧彪，讀線程均可進(jìn)入
        try {
            System.out.println(Thread.currentThread().getName()+" is ready to read");
            Thread.sleep(new Random().nextInt(100));
            System.out.println(Thread.currentThread().getName()+" have read data "+data);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }finally {
            rwl.readLock().unlock();    //讀鎖解鎖
        }
    }
    
    public void put(Object data){
        rwl.writeLock().lock(); //寫鎖開(kāi)啟待侵，這時(shí)只有一個(gè)寫線程進(jìn)入
        try {
            System.out.println(Thread.currentThread().getName()+" is ready to write");
            Thread.sleep(new Random().nextInt(100));
            this.data = data;
            System.out.println(Thread.currentThread().getName()+" have write data "+data);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            rwl.writeLock().unlock();   //寫鎖解鎖
        }
        
    }
}

7. java中的 wait() 和 sleep() 方法有何不同？

最大的不同是在等待 wait 時(shí)會(huì)釋放鎖姨裸，而 sleep 一直持有鎖秧倾，wait
通常被用于線程間交互，sleep 通常被用于暫停執(zhí)行傀缩。
其他不同有：

• sleep 是 Thread 類的靜態(tài)方法那先，wait 是 Object 方法
• wait,notify 和 notifyAll 只能在同步控制方法或者同步控制塊里面使用，而 sleep 可以在任何地方使用
• sleep 必須捕獲異常赡艰，而 wait,notiry 和 notifyAll 不需要捕獲異常

8. 如何實(shí)現(xiàn)阻塞隊(duì)列（BlockingQueue）?

阻塞隊(duì)列（BlockingQueue）是一個(gè)支持兩個(gè)附加操作的隊(duì)列售淡。這兩個(gè)附加的操作是：在隊(duì)列為空時(shí)，獲取元素的線程會(huì)等待隊(duì)列為飛控瞄摊；當(dāng)隊(duì)列滿時(shí)勋又，存儲(chǔ)元素的線程會(huì)等待隊(duì)列可用。阻塞隊(duì)列常用于生產(chǎn)者和消費(fèi)者的場(chǎng)景换帜，生產(chǎn)者是往隊(duì)列里添加元素的線程楔壤，消費(fèi)者是從隊(duì)列里拿元素的線程。阻塞隊(duì)列就是生產(chǎn)者存放元素的容器惯驼，而消費(fèi)者也只從容器里拿元素蹲嚣。

阻塞隊(duì)列的簡(jiǎn)單實(shí)現(xiàn)：

import java.util.LinkedList;
import java.util.List;

public class BlockingQueue {
    
    private List<Object> queue = new LinkedList<Object>();  //存儲(chǔ)快
    private int limit = 10; //默認(rèn)隊(duì)列大小
    public BlockingQueue(int limit){
        this.limit = limit;
    }
    public BlockingQueue() {}
    public synchronized void enQueue(Object item) throws InterruptedException{
        while (this.queue.size()==this.limit) {
            wait(); //很多資料上寫不需要捕獲異常，但看源碼還是有異常聲明
        }
        if (this.queue.size()==0) {
            notifyAll();
        }
        this.queue.add(item);   //元素添加到鏈表最后
    }

    public synchronized Object deQueue() throws InterruptedException{
        while (this.queue.size()==0){
            wait();
        }
        if (this.queue.size()==this.limit) {
            notifyAll();
        }
        return this.queue.remove(0);    //返回第一個(gè)數(shù)據(jù)祟牲，符合隊(duì)列先進(jìn)先出原理
    }
}

延伸：利用 Executors 創(chuàng)建線程池中的消息隊(duì)列情況隙畜，ThreadPoolExecutor 是 Executors 的底層，建議使用 Executors 说贝，想了解的可以自己查找資料议惰。

9. 創(chuàng)建一千個(gè)線程對(duì)一個(gè) static 的數(shù)據(jù)進(jìn)行++，之后會(huì)不會(huì)是1000乡恕，為什么言询？如果將 static 的數(shù)據(jù)加上 volatile 呢俯萎？

首先我們直接用代碼執(zhí)行一下看結(jié)果：

public class VolatileTest {

    public static int count = 0;
    
    public static void main(String[] args) throws InterruptedException {
        ThreadPoolExecutor executor = new ThreadPoolExecutor(1000,4000, 
                                  60l, TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>());
        
        for (int i = 0; i < 4000; i++) {  //由于1000個(gè)線程結(jié)果測(cè)試對(duì)比不明顯，所以創(chuàng)建4000個(gè)
            executor.execute(new ThreadPoolTask());
        }
        executor.shutdown();  //執(zhí)行完畢后關(guān)閉線程池
        while(!executor.isTerminated()){
            Thread.sleep(1000);
        }
        System.out.println(VolatileTest.count);  //線程都關(guān)閉之后輸出結(jié)果
    }
    
}
class ThreadPoolTask implements Runnable{

    @Override
    public void run() {
        VolatileTest.count++;
    }
    
}

結(jié)果都不盡相同运杭，大約在4000以下徘徊夫啊。接下來(lái)分析一下原因。Java 內(nèi)存模型是這樣的：

• 所有的變量都存儲(chǔ)在主內(nèi)存中
• 每個(gè)線程都有自己獨(dú)立的工作內(nèi)存辆憔，里面保證該線程是使用到的變量副本（即內(nèi)存中變量的拷貝）

JVM 還規(guī)定：

• 線程共享變量的所有操作必須在自己的工作內(nèi)存中進(jìn)行撇眯，不能直接從主內(nèi)存中讀寫；
• 不同線程之間無(wú)法直接訪問(wèn)其他線程工作內(nèi)存中的變量虱咧，線程間變量值得傳遞需要通過(guò)主內(nèi)存來(lái)完成熊榛；

通過(guò)以上規(guī)定我們想象一下4000個(gè)線程在同時(shí)操作count++的場(chǎng)景：
首先 A 線程從主內(nèi)存中拿到 count 值，比如說(shuō) 0彤钟，放到了自己的工作內(nèi)存中来候，在 A 沒(méi)處理完，B 線程就去主內(nèi)存拿 count 值逸雹，也是 0营搅，當(dāng) A、B 線程處理完之后將 count 值再放入主內(nèi)存時(shí) count 變成了1梆砸，實(shí)際我們要的結(jié)果是 2转质，這時(shí)候就出現(xiàn)了錯(cuò)誤。
接下來(lái)帖世，如果我們將 count 前加 volatile 關(guān)鍵字休蟹，運(yùn)行結(jié)果依然不保證是4000。先了解一下線程的可見(jiàn)性和原子性的定義：

• 可見(jiàn)性：一個(gè)線程對(duì)共享變量的修改日矫，能夠及時(shí)的被其他線程見(jiàn)到
• 原子性：一旦操作開(kāi)始赂弓，那么它一定可以在可能發(fā)生的“上下文切換”之前執(zhí)行完畢

而* volatile保證變量對(duì)線程的可見(jiàn)性，但不保證原子性 * 哪轿，如果要看volatile為什么不保證原子性可以看這篇文章盈魁。

而如果把 count 改為 AtomicInteger 類型，則即可以保證對(duì)線程的可見(jiàn)性以及原子性窃诉。

10. 在 synchroized 方法上加 static 和不加 static 的區(qū)別是什么杨耙？

synchroized 在修飾方法時(shí)稱為對(duì)象鎖，加了 static 則是類鎖飘痛，對(duì)象鎖則是每個(gè)對(duì)象都有一把鎖珊膜，而類鎖只有一個(gè)，即所有對(duì)象在調(diào)用此方法的時(shí)候共同用同一把鎖宣脉。