面試專題我放在git上了，地址Github 歡迎fork然后一起更新
設(shè)計模式
0，什么是設(shè)計模式，設(shè)計模式的六大原則，你是否在代碼中使用過設(shè)計模式？
設(shè)計模式是世界上各種各樣程序員用來解決特定設(shè)計問題的嘗試和測試的方法。設(shè)計模式是代碼可用性的延伸。
設(shè)計模式分三類：
創(chuàng)建型，與對象創(chuàng)建有關(guān)包括單例模式，工廠方法模式，抽象工廠模式，建造者模式，原型模式
結(jié)構(gòu)性，結(jié)構(gòu)性設(shè)計模式是從程序的結(jié)構(gòu)上解決模塊之間的耦合問題，包括適配器模式，代理模式，裝飾模式，外觀模式，橋接模式，組合模式和享元模式
行為型，主要處理類或?qū)ο笕绾谓换ゼ叭绾畏峙渎氊?zé)，包括策略模式，模板方法模式，觀察者模式，迭代器模式，責(zé)任鏈模式，命令模式，備忘錄模式，狀態(tài)模式，訪問者模式，中介模式，解析器模式
a.單一職責(zé)原則：就一個類來說，應(yīng)該只有一個引起它變化的原因
一個類做一件事情，避免職責(zé)過多。比如這種情況是不太好的，在一個Activity中既有bean文件，又有http請求，還有adapter等等，這就導(dǎo)致我們需要修改任何一個東西的時候都會導(dǎo)致Activity的改變，這樣一來就有多個引起它變化的原因，不符合單一職責(zé)原則
b.開放封閉原則：類，模塊，函數(shù)應(yīng)該是可以擴展的，但是不可以修改
對于擴展是開放的，對于修改是封閉的。盡量做到面對需求的改變時，我們的代碼能保持相對穩(wěn)定，通過擴展的方式應(yīng)對變化，而不是修改原有代碼實現(xiàn)
c.里氏替換原則：所有引用基類的地方，必須可以透明的時候其子類的對象
里氏替換原則是實現(xiàn)開放封閉原則的重要方式之一，我們知道，使用基類的地方都可以使用子類去實現(xiàn)，因為子類擁有基類的所有方法，所以在程序設(shè)計中盡量使用基類類型對對象進行定義，在運行時確定子類類型。
d.依賴倒置原則：高層模塊不應(yīng)該依賴于底層模塊，兩者都應(yīng)該依賴于抽象，抽象不應(yīng)該依賴于細節(jié)，細節(jié)應(yīng)該依賴于抽象
依賴倒置原則針對的是模塊之間的依賴關(guān)系，高層模塊指調(diào)用端，底層模塊指具體的實現(xiàn)類，抽象指接口或抽象類，細節(jié)就是實現(xiàn)類。該原則的具體表現(xiàn)就是模塊間的依賴通過抽象發(fā)生，直線類之間不發(fā)生直接依賴關(guān)系，依賴通過接口或抽象類產(chǎn)生，降低耦合，比如MVP模式下，View層和P層通過接口產(chǎn)生依賴關(guān)系
e.迪米特原則（最少知識原則）：一個軟件實體應(yīng)該盡可能少的與其他實體發(fā)生相互作用
迪米特原則要求我們在設(shè)計系統(tǒng)時，盡量減少對象之間的交互
f.接口隔離原則：一個類對另一個類的依賴應(yīng)該建立在最小的接口上
接口隔離原則的關(guān)鍵是接口以及這個接口要小，如何小呢，也就是我們要為專門的類創(chuàng)建專門的接口，這個接口只對它有效，不要試圖讓一個接口包羅萬象，要建立最小的依賴關(guān)系
1，單例模式
單例模式是一種確保系統(tǒng)中的一個類只產(chǎn)生一個實例的對象創(chuàng)建模式；Java.lang.Runtime就是單例的經(jīng)典例子
好處：
對于頻繁使用的對象，可以省略創(chuàng)建對象所花費的時間，這對于那些重量級對象而言，是非?？捎^的一筆系統(tǒng)開銷
由于new操作的次數(shù)減少，因而對系統(tǒng)內(nèi)存的使用頻率也會減低，這將減輕GC壓力，縮短GC停頓時間。
2，JDK中幾個常用是設(shè)計模式？
單例（Singleton），用于Runtime，Calender和其他類中
工廠模式（Factory），用于各種不可變的類如Boolean，像Boolean.valueOf
觀察者模式（Observer），用于Swing和很多事件監(jiān)聽中
裝飾器模式（Decorator design），用于多個JavaIO類中
3，Java中，什么叫觀察者模式？
觀察者模式是基于對象的狀態(tài)變化和觀察者的通訊，以便他們作出相應(yīng)的操作。簡單的例子就是一個天氣系統(tǒng)，當天氣變化時必須在展示給公眾的視圖中進行反映。這個視圖對象是一個主體，而不同的視圖是觀察者。
5.使用工廠模式最主要的好處是什么？在哪里使用？
工廠模式的最大好處是增加了創(chuàng)建對象時的封裝層次。如果你使用工廠來創(chuàng)建對象，之后你可以使用更高級和更高性能的實現(xiàn)來替換原始的產(chǎn)品實現(xiàn)或類，這不需要在調(diào)用層做任何修改。
6.舉一個用 Java 實現(xiàn)的裝飾模式(decorator design pattern)？它是作用于對象層次還是類層次？
裝飾模式增加強了單個對象的能力。Java IO 到處都使用了裝飾模式，典型例子就是Buffered 系列類如 BufferedReader 和 BufferedWriter，它們增強了 Reader 和 Writer 對象，以實現(xiàn)提升性能的 Buffer 層次的讀取和寫入。
7.在 Java 中，為什么不允許從靜態(tài)方法中訪問非靜態(tài)變量？
Java 中不能從靜態(tài)上下文訪問非靜態(tài)數(shù)據(jù)只是因為非靜態(tài)變量是跟具體的對象實例關(guān)聯(lián)的，而靜態(tài)的卻沒有和任何實例關(guān)聯(lián)。
8.設(shè)計一個 ATM 機，請說出你的設(shè)計思路？
比如設(shè)計金融系統(tǒng)來說，必須知道它們應(yīng)該在任何情況下都能夠正常工作。不管是斷電還是其他情況，ATM 應(yīng)該保持正確的狀態(tài)（事務(wù)） , 想想 加鎖（locking）、事務(wù)（transaction）、錯誤條件（error condition）、邊界條件（boundary condition） 等等。盡管你不能想到具體的設(shè)計，但如果你可以指出非功能性需求，提出一些問題，想到關(guān)于邊界條件，這些都會是很好的。
9.在 Java 中，什么時候用重載，什么時候用重寫？
如果你看到一個類的不同實現(xiàn)有著不同的方式來做同一件事，那么就應(yīng)該用重寫（overriding），而重載（overloading）是用不同的輸入做同一件事。在 Java 中，重載的方法簽名不同，而重寫并不是。
10.舉例說明什么情況下會更傾向于使用抽象類而不是接口？
接口和抽象類都遵循”面向接口而不是實現(xiàn)編碼”設(shè)計原則，它可以增加代碼的靈活性，可以適應(yīng)不斷變化的需求。
下面有幾個點可以幫助你回答這個問題：
在 Java 中，你只能繼承一個類，但可以實現(xiàn)多個接口。所以一旦你繼承了一個類，你就失去了繼承其他類的機會了。
接口通常被用來表示附屬描述或行為如：Runnable、Clonable、Serializable 等等，因此當你使用抽象類來表示行為時，你的類就不能同時是 Runnable 和 Clonable(注：這里的意思是指如果把 Runnable 等實現(xiàn)為抽象類的情況)，因為在 Java 中你不能繼承兩個類，但當你使用接口時，你的類就可以同時擁有多個不同的行為。在一些對時間要求比較高的應(yīng)用中，傾向于使用抽象類，它會比接口稍快一點。如果希望把一系列行為都規(guī)范在類繼承層次內(nèi)，并且可以更好地在同一個地方進行編碼，那么抽象類是一個更好的選擇。有時，接口和抽象類可以一起使用，接口中定義函數(shù)，而在抽象類中定義默認的實現(xiàn)
11，android中舉例說說用到了什么設(shè)計模式？
o AlertDialog、Notification 源碼中使用了 Builder（建造者）模式完成參數(shù)的初始化
o Okhttp 內(nèi)部使用了責(zé)任鏈模式來完成每個 Interceptor 攔截器的調(diào)用
o RxJava 的觀察者模式；單例模式；GridView 的適配器模式；Intent 的原型模式
o 日常開發(fā)的 BaseActivity 抽象工廠模式
數(shù)據(jù)結(jié)構(gòu)
1、常用數(shù)據(jù)結(jié)構(gòu)簡介
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素間的關(guān)系組成。常用的數(shù)據(jù)有：數(shù)組、棧、隊列、鏈表、樹、圖、堆、散列表。
1）數(shù)組：在內(nèi)存中連續(xù)存儲多個元素的結(jié)構(gòu)。數(shù)組元素通過下標訪問，下標從0開始。優(yōu)點：訪問速度快；缺點：數(shù)組大小固定后無法擴容，只能存儲一種類型的數(shù)據(jù)，添加刪除操作慢。適用場景：適用于需頻繁查找，對存儲空間要求不高，很少添加刪除。
2）棧：一種特殊的線性表，只可以在棧頂操作，先進后出，從棧頂放入元素叫入棧，從棧頂取出元素叫出棧。應(yīng)用場景：用于實現(xiàn)遞歸功能，如斐波那契數(shù)列。
3）隊列：一種線性表，在列表一端添加元素，另一端取出，先進先出。使用場景：多線程阻塞隊列管理中。
4）鏈表：物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實現(xiàn)，每個元素包含兩個結(jié)點，一個是存儲元素的數(shù)據(jù)域，一個是指向下一個結(jié)點地址的指針域。有單鏈表、雙向鏈表、循環(huán)鏈表。優(yōu)點：可以任意加減元素，不需要初始化容量，添加刪除元素只需改變前后兩個元素結(jié)點的指針域即可。缺點：因為含有大量指針域，固占用空間大，查找耗時。適用場景：數(shù)據(jù)量小，需頻繁增加刪除操作。
5）樹：由n個有限節(jié)點組成一種具有層次關(guān)系的集合。二叉樹（每個結(jié)點最多有兩個子樹，結(jié)點的度最大為2，左子樹和右子樹有順序）、紅黑樹（HashMap底層源碼）、B+樹（mysql的數(shù)據(jù)庫索引結(jié)構(gòu)）
6）散列表（哈希表）：根據(jù)鍵值對來存儲訪問。
7）堆：堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值，堆總是一棵完全二叉樹。
8）圖：由結(jié)點的有窮集合V和邊的集合E組成。
2、并發(fā)集合了解哪些？
1）并發(fā)List，包括Vector和CopyOnWriteArrayList是兩個線程安全的List，Vector讀寫操作都用了同步，CopyOnWriteArrayList在寫的時候會復(fù)制一個副本，對副本寫，寫完用副本替換原值，讀時不需要同步。
2）并發(fā)Set，CopyOnWriteArraySet基于CopyOnWriteArrayList來實現(xiàn)的，不允許存在重復(fù)的對象。
3）并發(fā)Map，ConcurrentHashMap，內(nèi)部實現(xiàn)了鎖分離，get操作是無鎖的。
4）并發(fā)Queue，ConcurrentLinkedQueue適用于高并發(fā)場景下的隊列，通過無鎖方式實現(xiàn)。 BlockingQueue阻塞隊列，應(yīng)用場景，生產(chǎn)者-消費者模式，若生產(chǎn)快于消費，生產(chǎn)隊列裝滿時會阻塞，等待消費。
5）并發(fā)Deque, LinkedBlockingDueue沒有進行讀寫鎖分離，同一時間只能有一個線程對其操作。
6）并發(fā)鎖重入鎖ReentrantLock，互斥鎖，一次最多只能一個線程拿到鎖。
7）讀寫鎖ReadWriteLock，有讀取和寫入鎖兩種，讀取允許多個讀取線程同時持有，而寫入只能有一個線程持有。
3、列舉java的集合以及集合之間的繼承關(guān)系
5、容器類介紹以及之間的區(qū)別
1）Collection接口：集合框架的根接口，它是集合類框架中最具一般性的頂層接口。
2）Map接口：提供了鍵值對的映射關(guān)系的集合，關(guān)鍵字不能有重復(fù)值，每個關(guān)鍵字至多可映射一個值。HashMap(通過散列機制，用于快速訪問)，TreeMap（保持key處于排序狀態(tài)，訪問速度不如hashmap）, LinkedHashMap(保持元素的插入順序)
3）Set接口：可包含重復(fù)的元素，LinkedHashSet TreeSet(用紅黑樹來存儲元素) HashSet
4）List接口:可通過索引對元素進行精準的插入和查找，實現(xiàn)類有ArrayList LinkedList
5）Queue接口：繼承自Collection接口，LinkedList實現(xiàn)了Queue接口，提供了支持隊列的行為。
6）Iterator接口：為了迭代集合
7）Comparable接口：用于比較
6、List,Set,Map的區(qū)別
Set是一個無序的集合，不能包含重復(fù)的元素；
list是一個有序的集合可以包含重復(fù)的元素，提供了按索引訪問的方式；
map包含了key-value對，map中key必須唯一，value可以重復(fù)。
7、HashMap的實現(xiàn)原理
1）數(shù)據(jù)結(jié)構(gòu)
jdk1.7及以前，HashMap由數(shù)組+鏈表組成，數(shù)組Entry是HashMap的主體，Entry是HashMap中的一個靜態(tài)內(nèi)部類，每一個Entry包含一個key-value鍵值對，鏈表是為解決哈希沖突而存在。
從jdk1.8起，HashMap是由數(shù)組+鏈表/紅黑樹組成，當某個bucket位置的鏈表長度達到閥值8時，這個鏈表就轉(zhuǎn)變成紅黑樹。
2）HashMap是線程不安全的，存儲比較快，能接受null值，HashMap通過put(key, value)來儲存元素，通過get(key)來得到value值，通過hash算法來計算hashcode值，用hashcode標識Entry在bucket中存儲的位置。
3）HashMap中為什么要使用加載因子，為什么要進行擴容
加載因子是指當HashMap中存儲的元素/最大空間值的閥值，如果超過這個值，就會進行擴容。加載因子是為了讓空間得到充分利用，如果加載因子太大，雖對空間利用更充分，但查找效率會降低；如果加載因子太小，表中的數(shù)據(jù)過于稀疏，很多空間還沒用就開始擴容，就會對空間造成浪費。
至于為什么要擴容，如果不擴容，HashMap中數(shù)組處的鏈表會越來越長，這樣查找效率就會大大降低。
7.1 HashMap如何put數(shù)據(jù)（從HashMap源碼角度講解）？
當我們使用put(key, value)存儲對象到HashMap中時，具體實現(xiàn)步驟如下：
1）先判斷table數(shù)組是否為空，為空以默認大小構(gòu)建table，table默認空間大小為16
2）計算key的hash值，并計算hash&(n-1)值得到在數(shù)組中的位置index，如果該位置沒值即table[index]為空，則直接將該鍵值對存放在table[index]處。
3）如果table[index]處不為空，說明發(fā)生了hash沖突，判斷table[index]處結(jié)點是否是TreeNode(紅黑樹結(jié)點)類型數(shù)據(jù)，如果是則執(zhí)行putTreeVal方法，按紅黑樹規(guī)則將鍵值對存入；
4）如果table[index]是鏈表形式，遍歷該鏈表上的數(shù)據(jù)，將該鍵值對放在table[index]處，并將其指向原index處的鏈表。判斷鏈表上的結(jié)點數(shù)是否大于鏈表最大結(jié)點限制（默認為8），如果超過了需執(zhí)行treeifyBin()操作，則要將該鏈表轉(zhuǎn)換成紅黑樹結(jié)構(gòu)。
5）判斷HashMap中數(shù)據(jù)個數(shù)是否超過了（最大容量*裝載因子），如果超過了，還需要對其進行擴容操作。
7.2 HashMap如何get數(shù)據(jù)？
get(key)方法獲取key的hash值，計算hash&(n-1)得到在鏈表數(shù)組中的位置first=table[hash&(n-1)]，先判斷first（即數(shù)組中的那個）的key是否與參數(shù)key相等，不等的話，判斷結(jié)點是否是TreeNode類型，是則調(diào)用getTreeNode(hash, key)從二叉樹中查找結(jié)點，不是TreeNode類型說明還是鏈表型，就遍歷鏈表找到相同的key值返回對應(yīng)的value值即可。
7.3 當兩個對象的hashcode相同，即發(fā)生碰撞時，HashMap如何處理
當兩個對象的hashcode相同，它們的bucket位置相同，hashMap會用鏈表或是紅黑樹來存儲對象。Entry類里有一個next屬性，作用是指向下一個Entry。第一個鍵值對A進來，通過計算其key的hash得到index，記做Entry[index]=A。一會又進來一個鍵值對B，通過計算其key的hash也是index，HashMap會將B.next=A, Entry[index]=B.如果又進來C，其key的hash也是index,會將C.next=B, Entry[index]=C.這樣bucket為index的地方存放了A\B\C三個鍵值對，它們能過next屬性鏈在一起。數(shù)組中存儲的是最后插入的元素，其他元素都在后面的鏈表里。
7.4 如果兩個鍵的hashcode相同，如何獲取值對象？
當調(diào)用get方法時，hashmap會使用鍵對象的hashcode找到bucket位置，找到bucket位置后，會調(diào)用key.equals()方法去找到鏈表中正確的節(jié)點，最終找到值對象。
7.5 hashMap如何擴容
HashMap默認負載因為是0.75，當一個map填滿了75%的bucket時，和其他集合類一樣，將會創(chuàng)建原來HashMap大小兩倍的bucket數(shù)組，來重新調(diào)整HashMap的大小，并將原來的對象放入新的bucket數(shù)組中。
在jdk1.7及以前，多線程擴容可能出現(xiàn)死循環(huán)。因為在調(diào)整大小過程中，存儲在某個bucket位置中的鏈表元素次序會反過來，而多線程情況下可能某個線程翻轉(zhuǎn)完鏈表，另外一個線程又開始翻轉(zhuǎn)，條件競爭發(fā)生了，那么就死循環(huán)了。
而在jdk1.8中，會將原來鏈表結(jié)構(gòu)保存至節(jié)點e中，將原來數(shù)組中的位置設(shè)為null，然后依次遍歷e，根據(jù)hash&n是否為0分成兩條支鏈，保存在新數(shù)組中。如果多線程情況可能會取到null值造成數(shù)據(jù)丟失。
8、ConcurrentHashMap的實現(xiàn)原理
1）jdk1.7及以前：一個ConcurrentHashMap由一個segment數(shù)組和多個HashEntry組成，每一個segment都包含一個HashEntry數(shù)組, Segment繼承ReentrantLock用來充當鎖角色，每一個segment包含了對自己的HashEntry的操作，如get\put\replace操作，這些操作發(fā)生時，對自己的HashEntry進行鎖定。由于每一個segment寫操作只鎖定自己的HashEntry，可以存在多個線程同時寫的情況。
jdk1.8以后：ConcurrentHashMap取消了segments字段，采用transient volatile HashEntry<K, V> table保存數(shù)據(jù)，采用table數(shù)組元素作為鎖，實現(xiàn)對每一個數(shù)組數(shù)據(jù)進行加鎖，進一小減少并發(fā)沖突概率。ConcurrentHashMap是用Node數(shù)組+鏈表+紅黑樹數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的，并發(fā)制定用synchronized和CAS操作。
2）Segment實現(xiàn)了ReentrantLock重入鎖，當執(zhí)行put操作，會進行第一次key的hash來定位Segment的位置，若該Segment還沒有初始化，會通過CAS操作進行賦值，再進行第二次hash操作，找到相應(yīng)的HashEntry位置。
9、ArrayMap和HashMap的對比
1)存儲方式不一樣，HashMap內(nèi)部有一個Node<K,V>[]對象，每個鍵值對都會存儲到這個對象里，當用put方法添加鍵值對時，會new一個Node對象，tab[i] = newNode(hash, key, value, next);
ArrayMap存儲則是由兩個數(shù)組來維護，int[] mHashes; Object[] mArray; mHashes數(shù)組中保存的是每一項的HashCode值，mArray存的是鍵值對，每兩個元素代表一個鍵值對，前面保存key，后面保存value。mHashes[index]=hash; mArray[index<<1]=key; mArray[(index<<1)+1]=value;
ArrayMap相對于HashMap，無需為每個鍵值對創(chuàng)建Node對象，且在數(shù)組中連續(xù)存放，更省空間。
2）添加數(shù)據(jù)時擴容處理不一樣，進行了new操作，重新創(chuàng)建對象，開銷很大；而ArrayMap用的是copy數(shù)據(jù)，所有效率相對高些；
3）ArrayMap提供了數(shù)組收縮功能，在clear或remove后，會重新收縮數(shù)組，釋放空間；
4）ArrayMap采用二分法查找，mHashes中的hash值是按照從小到大的順序連續(xù)存放的，通過二分查找來獲取對應(yīng)hash下標index，去mArray中查找鍵值對。mHashes中的index2是mArray中的key下標，index2+1為value的下標，由于存在hash碰撞情況，二分查找到的下標可能是多個連續(xù)相同的hash值中的任意一個，此時需要用equals比對命中的key對象是否相等，不相等，應(yīng)當從當前index先向后再向前遍歷所有相同hash值。
5）sparseArray比ArrayMap進一步優(yōu)化空間，SparseArray專門對基本類型做了優(yōu)化，Key只能是可排序的基本類型，如int\long，對value，除了泛型Value，還對每種基本類型有單獨實現(xiàn)，如SparseBooleanArray\SparseLongArray等。無需包裝，直接使用基本類型值，無需hash，直接使用基本類型值索引和判斷相等，無碰撞，無需調(diào)用hashCode方法，無需equals比較。SparseArray延遲刪除。
10、HashTable實現(xiàn)原理
Hashtable中的無參構(gòu)造方法Hashtable()中調(diào)用了this(11, 0.75f)，說明它默認容量是11，加載因子是0.75,在構(gòu)造方法上會new HashtableEntry<?, ?>[initialCapacity]; 會新建一個容量是初始容量的HashtableEntry數(shù)組。HashtableEntry數(shù)組中包含hash\Key\Value\next變量，鏈表形式，重寫了hashCode和equals方法。Hashtable所有public方法都在方法體上加上了synchronized鎖操作，說明它是線程安全的。它還實現(xiàn)了Serializable接口中的writeObject和readObject方法，分別實現(xiàn)了逐行讀取和寫入的功能，并且加了synchronized鎖操作。
（1） put(Key, Value)方法
1）先判斷value是否為空，為空拋出空指針異常；
2）根據(jù)key的hashCode()值，計算table表中的位置索引(hash&0x7FFFFFFF)%tab.length值index，如果該索引處有值，再判斷該索引處鏈表中是否包含相同的key，如果key值相同則替換舊值。
3）如果沒有相同的key值，調(diào)用addEntry方法，在addEntry中判斷count大小是否超過了最大容量限制，如果超過了需要重新rehash()，容量變成原來容量*2+1，將原表中的值都重新計算hash值放入新表中。再構(gòu)造一個HashtableEntry對象放入相應(yīng)的table表頭，如果原索引處有值，則將table[index].next指向原索引處的鏈表。
（2）get方法
根所key.hashCode()，計算它在table表中的位置，(hash&0x7FFFFFFF)%tab.length，遍歷該索引處表的位置中是否有值，是否存在鏈表，再判斷是key值和hash值是否相等，相等則返回對應(yīng)的value值。
11、HashMap和HashTable的區(qū)別
1）Hashtable是個線程安全的類，在對外方法都添加了synchronized方法，序列化方法上也添加了synchronized同步鎖方法，而HashMap非線程安全。這也導(dǎo)致Hashtable的讀寫等操作比HashMap慢。
2）Hashtable不允許值和鍵為空，若為空會拋出空指針。而HashMap允許鍵和值為空；
3）Hashtable根據(jù)key值的hashCode計算索引，(hash&0x7FFFFFFF)%tab.length，保證hash值始終為正數(shù)且不超過表的長度。而HashMap中計算索引值是通過hash(key)&(tab.length-1)，是通過與操作，計算出在表中的位置會比Hashtable快。
4）Hashtable容量能為任意大于等于1的正數(shù)，而HashMap的容量必須為2^n，Hashtable默認容量為11，HashMap初始容量為16
5）Hashtable每次擴容，新容量為舊容量的2倍+1，而HashMap為舊容量的2倍。
12、HashMap與HashSet的區(qū)別
HashSet底層實現(xiàn)是HashMap,內(nèi)部包含一個HashMap<E, Ojbect> map變量
private transient HashMap<E,Object> map;
一個Object PRESENT變量（當成插入map中的value值）
private static final Object PRESENT = new Object();
HashSet中元素都存到HashMap鍵值對的Key上面。具體可以查看HashSet的add方法，直接調(diào)用了HashMap的put方法，將值作為HashMap的鍵，值用一個固定的PRESENT值。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashSet沒有單獨的get方法，用的是HashMap的。HashSet實現(xiàn)了Set接口，不允許集合中出現(xiàn)重復(fù)元素，將對象存儲進HashSet前，要先確保對象重寫了hashCode()和equals方法，以保證放入set對象是唯一的。
13、HashSet與HashMap怎么判斷集合元素重復(fù)？
HashMap在放入key-value鍵值對是，先通過key計算其hashCode()值，再與tab.length-1做與操作，確定下標index處是否有值，如果有值，再調(diào)用key對象的equals方法，對象不同則插入到表頭，相同則覆蓋；
HashSet是將數(shù)據(jù)存放到HashMap的key中，HashMap是key-value形式的數(shù)據(jù)結(jié)構(gòu)，它的key是唯一的，HashSet利用此原理保證放入的對象唯一性。
14、集合Set實現(xiàn)Hash怎么防止碰撞
HashSet底層實現(xiàn)是HashMap，HashMap如果兩個不同Key對象的hashCode()值相等，會用鏈表存儲，HashSet也一樣。
15、ArrayList和LinkedList的區(qū)別，以及應(yīng)用場景
ArrayList底層是用數(shù)組實現(xiàn)的，隨著元素添加，其大小是動態(tài)增大的；在內(nèi)存中是連續(xù)存放的；如果在集合末尾添加或刪除元素，所用時間是一致的，如果在列表中間添加或刪除元素，所用時間會大大增加。通過索引查找元素速度很快。適合場合：查詢比較多的場景
LinkedList底層是通過雙向鏈表實現(xiàn)的，LinkedList和ArrayList相比，增刪速度快，但查詢和修改值速度慢。在內(nèi)存中不是連續(xù)內(nèi)存。場景：增刪操作比較多的場景。
-二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的具體實現(xiàn)
-堆的結(jié)構(gòu)
-堆和樹的區(qū)別
-堆和棧在內(nèi)存中的區(qū)別是什么(解答提示：可以從數(shù)據(jù)結(jié)構(gòu)方面以及實際實現(xiàn)方面兩個方面去回答)？
-什么是深拷貝和淺拷貝
-手寫鏈表逆序代碼
-講一下對樹，B+樹的理解
-講一下對圖的理解
-判斷單鏈表成環(huán)與否？
-鏈表翻轉(zhuǎn)（即：翻轉(zhuǎn)一個單項鏈表）
-合并多個單有序鏈表（假設(shè)都是遞增的）
