1.List?
ArrayList 、Vector 、LinkedList的區(qū)別？
答：ArrayList?底層是數(shù)組
特點(diǎn)：查詢快，增刪慢，線程不安全
LinkList?底層是鏈表
特點(diǎn)：查詢慢，增刪快，線程不安全
Vector?底層是數(shù)組
特點(diǎn)：查詢快，增刪慢，線程安全
Array 和 ArrayList 有什么區(qū)別？什么時(shí)候該應(yīng) Array 而不是 ArrayList 呢？
答：Array可以包含基本類型和對(duì)象類型，ArrayList只能包含對(duì)象類型。
Array大小是固定的，ArrayList的大小是動(dòng)態(tài)變化的。
ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。
對(duì)于基本類型數(shù)據(jù)，集合使用自動(dòng)裝箱來減少編碼工作量。但是，當(dāng)處理固定大小的基本數(shù)據(jù)類型的時(shí)候，這種方式相對(duì)比較慢。
適用場(chǎng)景：?如果想要保存一些在整個(gè)程序運(yùn)行期間都會(huì)存在而且不變的數(shù)據(jù)，我們可以將它們放進(jìn)一個(gè)全局?jǐn)?shù)組里，但是如果我們單純只是想要以數(shù)組的形式保存數(shù)據(jù)，而不對(duì)數(shù)據(jù)進(jìn)行增加等操作，只是方便我們進(jìn)行查找的話，那么，我們就選擇ArrayList。而且還有一個(gè)地方是必須知道的，就是如果我們需要對(duì)元素進(jìn)行頻繁的移動(dòng)或刪除，或者是處理的是超大量的數(shù)據(jù)，那么，使用ArrayList就真的不是一個(gè)好的選擇，因?yàn)樗男屎艿?，使用?shù)組進(jìn)行這樣的動(dòng)作就很麻煩，那么，我們可以考慮選擇LinkedList
2.Set
HashSet是如何保證數(shù)據(jù)不可重復(fù)的？HashSet和TreeSet有什么區(qū)別？TreeMap和TreeSet在排序時(shí)如何比較元素？Collections工具類中的sort()方法如何比較元素？
答：HashSet原理
我們使用Set集合都是需要去掉重復(fù)元素的, 如果在存儲(chǔ)的時(shí)候逐個(gè)equals()比較, 效率較低,哈希算法提高了去重復(fù)的效率, 降低了使用equals()方法的次數(shù)
當(dāng)HashSet調(diào)用add()方法存儲(chǔ)對(duì)象的時(shí)候, 先調(diào)用對(duì)象的hashCode()方法得到一個(gè)哈希值, 然后在集合中查找是否有哈希值相同的對(duì)象
如果沒有哈希值相同的對(duì)象就直接存入集合
如果有哈希值相同的對(duì)象, 就和哈希值相同的對(duì)象逐個(gè)進(jìn)行equals()比較,比較結(jié)果為false就存入, true則不存
TreeSet原理
TreeSet是用來排序的, 可以指定一個(gè)順序, 對(duì)象存入之后會(huì)按照指定的順序排列
TreeSet排序方式有兩種自然順序和比較器順序
總結(jié)一下他們的特點(diǎn)：
1.TreeSet 是二差樹實(shí)現(xiàn)的,TreeSet中的數(shù)據(jù)是自動(dòng)排好序的，不允許放入null值
2.HashSet 是哈希表實(shí)現(xiàn)的,HashSet中的數(shù)據(jù)是無序的，可以放入null，但只能放入一個(gè)null?
3.HashSet要求放入的對(duì)象必須實(shí)現(xiàn)HashCode()方法，放入的對(duì)象，是以hashcode碼作為標(biāo)識(shí)的，而具有相同內(nèi)容的 String對(duì)象，hashcode是一樣，所以放入的內(nèi)容不能重復(fù)。但是同一個(gè)類的對(duì)象可以放入不同的實(shí)例?
4.TreeSet要求存放的對(duì)象所屬的類必須實(shí)現(xiàn)Comparable接口，該接口提供了比較元素的compareTo()方法，當(dāng)插入元素時(shí)會(huì)回調(diào)該方法比較元素的大小。TreeMap要求存放的鍵值對(duì)映射的鍵必須實(shí)現(xiàn)Comparable接口從而根據(jù)鍵對(duì)元素進(jìn)行排序。
Collections工具類的sort方法有兩種重載的形式，第一種要求傳入的待排序容器中存放的對(duì)象必須實(shí)現(xiàn)Comparable接口以實(shí)現(xiàn)元素的比較；第二種不強(qiáng)制性的要求容器中的元素必須可比較，但是要求傳入第二個(gè)參數(shù)，參數(shù)是Comparator接口的子類型（需要重寫compare方法實(shí)現(xiàn)元素的比較），相當(dāng)于一個(gè)臨時(shí)定義的排序規(guī)則，其實(shí)就是通過接口注入比較元素大小的算法，也是對(duì)回調(diào)模式的應(yīng)用（Java中對(duì)函數(shù)式編程的支持）。
Set 里的元素是不能重復(fù)的，那么用什么方法來區(qū)分重復(fù)與否呢？是用 == 還是 equals()？ 它們有何區(qū)別?
答：Set?里的元素是不能重復(fù)的，元素重復(fù)與否是使用?equals()方法進(jìn)行判斷的。
equals()和==方法決定引用值是否指向同一對(duì)象?equals()在類中被覆蓋，為的是當(dāng)兩個(gè)
分離的對(duì)象的內(nèi)容和類型相配的話，返回真值。
equals（）和==的區(qū)別
==操作符專門用來比較兩個(gè)變量的值是否相等，也就是用于比較變量所對(duì)應(yīng)的內(nèi)存中所存
儲(chǔ)的數(shù)值是否相同，?要比較兩個(gè)基本類型的數(shù)據(jù)或兩個(gè)引用變量是否相等，只能用==操作
符。
如果一個(gè)變量指向的數(shù)據(jù)是對(duì)象類型的，那么，這時(shí)候涉及了兩塊內(nèi)存，?對(duì)象本身占用一塊
內(nèi)存（堆內(nèi)存），變量也占用一塊內(nèi)存，例如?Objet obj = new Object();變量?obj?是一個(gè)內(nèi)存，
new Object()是另一個(gè)內(nèi)存，此時(shí)，變量?obj?所對(duì)應(yīng)的內(nèi)存中存儲(chǔ)的數(shù)值就是對(duì)象占用的那
塊內(nèi)存的首地址。對(duì)于指向?qū)ο箢愋偷淖兞?，如果要比較兩個(gè)變量是否指向同一個(gè)對(duì)象，即
要看這兩個(gè)變量所對(duì)應(yīng)的內(nèi)存中的數(shù)值是否相等，這時(shí)候就需要用==操作符進(jìn)行比較。
equals?方法是用于比較兩個(gè)獨(dú)立對(duì)象的內(nèi)容是否相同，就好比去比較兩個(gè)人的長(zhǎng)相是否相
同，它比較的兩個(gè)對(duì)象是獨(dú)立的。例如，對(duì)于下面的代碼：
String a=newString("foo");
String b=newString("foo");
兩條?new?語句創(chuàng)建了兩個(gè)對(duì)象，然后用?a/b?這兩個(gè)變量分別指向了其中一個(gè)對(duì)象，這是兩
個(gè)不同的對(duì)象，它們的首地址是不同的，即?a?和?b?中存儲(chǔ)的數(shù)值是不相同的，所以，表達(dá)
式?a==b?將返回?false，而這兩個(gè)對(duì)象中的內(nèi)容是相同的，所以，表達(dá)式?a.equals(b)將返回
true。
在實(shí)際開發(fā)中，我們經(jīng)常要比較傳遞進(jìn)行來的字符串內(nèi)容是否等，例如，?String input
=?…;input.equals(“quit”)，許多人稍不注意就使用==進(jìn)行比較了，這是錯(cuò)誤的，隨便從網(wǎng)上
找?guī)讉€(gè)項(xiàng)目實(shí)戰(zhàn)的教學(xué)視頻看看，里面就有大量這樣的錯(cuò)誤。記住，字符串的比較基本上都
是使用?equals?方法。
如果一個(gè)類沒有自己定義?equals?方法，那么它將繼承?Object?類的?equals?方法，?Object?類
的?equals?方法的實(shí)現(xiàn)代碼如下：
boolean equals(Object o){returnthis==o;
}
這說明，如果一個(gè)類沒有自己定義?equals?方法，它默認(rèn)的?equals?方法（從?Object?類繼承
的）就是使用==操作符，也是在比較兩個(gè)變量指向的對(duì)象是否是同一對(duì)象，這時(shí)候使用
equals?和使用==會(huì)得到同樣的結(jié)果，如果比較的是兩個(gè)獨(dú)立的對(duì)象則總返回?false。如果你
編寫的類希望能夠比較該類創(chuàng)建的兩個(gè)實(shí)例對(duì)象的內(nèi)容是否相同，那么你必須覆蓋?equals
方法，由你自己寫代碼來決定在什么情況即可認(rèn)為兩個(gè)對(duì)象的內(nèi)容是相同的
由上述可見：
總結(jié)如下：
==：
基本類型：比較的是值是否相同
引用類型：比較的是地址值是否相同
equals（）：
引用類型：默認(rèn)情況下，比較的是地址值，可進(jìn)行重寫，比較的是對(duì)象的成員變量值是否相同
3.Map
HashMap的實(shí)現(xiàn)機(jī)制，底層數(shù)據(jù)結(jié)構(gòu)是什么？怎么樣HashMap線程安全，HashMap和HashTable有什么區(qū)別？
答：HashMap和Hashtable的底層實(shí)現(xiàn)都是數(shù)組+鏈表結(jié)構(gòu)實(shí)現(xiàn)的，這點(diǎn)上完全一致。添加、刪除、獲取元素時(shí)都是先計(jì)算hash，根據(jù)hash和table.length計(jì)算index也就是table數(shù)組的下標(biāo)，然后進(jìn)行相應(yīng)操作。
1.兩者最主要的區(qū)別在于Hashtable是線程安全，而HashMap則非線程安全
Hashtable的實(shí)現(xiàn)方法里面都添加了synchronized關(guān)鍵字來確保線程同步，因此相對(duì)而言HashMap性能會(huì)高一些，我們平時(shí)使用時(shí)若無特殊需求建議使用HashMap，在多線程環(huán)境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個(gè)線程安全的集合（Collections.synchronizedMap()實(shí)現(xiàn)原理是Collections定義了一個(gè)SynchronizedMap的內(nèi)部類，這個(gè)類實(shí)現(xiàn)了Map接口，在調(diào)用方法時(shí)使用synchronized來保證線程同步,當(dāng)然了實(shí)際上操作的還是我們傳入的HashMap實(shí)例，簡(jiǎn)單的說就是Collections.synchronizedMap()方法幫我們?cè)诓僮鱄ashMap時(shí)自動(dòng)添加了synchronized來實(shí)現(xiàn)線程同步，類似的其它Collections.synchronizedXX方法也是類似原理）
2.HashMap可以使用null作為key，而Hashtable則不允許null作為key
雖說HashMap支持null值作為key，不過建議還是盡量避免這樣使用，因?yàn)橐坏┎恍⌒氖褂昧耍粢虼艘l(fā)一些問題，排查起來很是費(fèi)事
HashMap以null作為key時(shí)，總是存儲(chǔ)在table數(shù)組的第一個(gè)節(jié)點(diǎn)上
3.HashMap是對(duì)Map接口的實(shí)現(xiàn)，HashTable實(shí)現(xiàn)了Map接口和Dictionary抽象類
4.HashMap的初始容量為16，Hashtable初始容量為11，兩者的填充因子默認(rèn)都是0.75
HashMap擴(kuò)容時(shí)是當(dāng)前容量翻倍即:capacity*2，Hashtable擴(kuò)容時(shí)是容量翻倍+1即:capacity*2+1
5.兩者計(jì)算hash的方法不同
Hashtable計(jì)算hash是直接使用key的hashcode對(duì)table數(shù)組的長(zhǎng)度直接進(jìn)行取模
HashMap計(jì)算hash對(duì)key的hashcode進(jìn)行了二次hash，以獲得更好的散列值，然后對(duì)table數(shù)組長(zhǎng)度取摸
6.HashMap和Hashtable的底層實(shí)現(xiàn)都是數(shù)組+鏈表結(jié)構(gòu)實(shí)現(xiàn)
為什么HashMap中String、Integer這樣的包裝類適合作為K？如果我想要讓自己的Object作為K應(yīng)該怎么辦呢？
答：String、Integer等包裝類的特性能夠保證Hash值的不可更改性和計(jì)算準(zhǔn)確性，能夠有效的減少Hash碰撞的幾率
都是final類型，即不可變性，保證key的不可更改性，不會(huì)存在獲取hash值不同的情況
內(nèi)部已重寫了equals()、hashCode()等方法，遵守了HashMap內(nèi)部的規(guī)范（不清楚可以去上面看看putValue的過程），不容易出現(xiàn)Hash值計(jì)算錯(cuò)誤的情況；
如果我想要讓自己的Object作為K，就重寫hashCode()和equals()方法
重寫hashCode()是因?yàn)樾枰?jì)算存儲(chǔ)數(shù)據(jù)的存儲(chǔ)位置，需要注意不要試圖從散列碼計(jì)算中排除掉一個(gè)對(duì)象的關(guān)鍵部分來提高性能，這樣雖然能更快但可能會(huì)導(dǎo)致更多的Hash碰撞；
重寫equals()方法，需要遵守自反性、對(duì)稱性、傳遞性、一致性以及對(duì)于任何非null的引用值x，x.equals(null)必須返回false的這幾個(gè)特性，目的是為了保證key在哈希表中的唯一性；
HashMap是怎么解決哈希沖突的？
答：Hash，一般翻譯為“散列”，也有直接音譯為“哈?！钡?，這就是把任意長(zhǎng)度的輸入通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值（哈希值）；這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡(jiǎn)單的說就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。
所有散列函數(shù)都有如下一個(gè)基本特性：根據(jù)同一散列函數(shù)計(jì)算出的散列值如果不同，那么輸入值肯定也不同。但是，根據(jù)同一散列函數(shù)計(jì)算出的散列值如果相同，輸入值不一定相同。
什么是哈希沖突？當(dāng)兩個(gè)不同的輸入值，根據(jù)同一散列函數(shù)計(jì)算出相同的散列值的現(xiàn)象，我們就把它叫做碰撞（哈希碰撞）。
HashMap的數(shù)據(jù)結(jié)構(gòu)
在Java中，保存數(shù)據(jù)有兩種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表。數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；鏈表的特點(diǎn)是：尋址困難，但插入和刪除容易；所以我們將數(shù)組和鏈表結(jié)合在一起，發(fā)揮兩者各自的優(yōu)勢(shì)，使用一種叫做鏈地址法的方式可以解決哈希沖突：
這樣我們就可以將擁有相同哈希值的對(duì)象組織成一個(gè)鏈表放在hash值所對(duì)應(yīng)的bucket下，但相比于hashCode返回的int類型，我們HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要遠(yuǎn)小于int類型的范圍，所以我們?nèi)绻皇菃渭兊挠胔ashCode取余來獲取對(duì)應(yīng)的bucket這將會(huì)大大增加哈希碰撞的概率，并且最壞情況下還會(huì)將HashMap變成一個(gè)單鏈表，所以我們還需要對(duì)hashCode作一定的優(yōu)化
hash()函數(shù)
上面提到的問題，主要是因?yàn)槿绻褂胔ashCode取余，那么相當(dāng)于參與運(yùn)算的只有hashCode的低位，高位是沒有起到任何作用的，所以我們的思路就是讓hashCode取值出的高位也參與運(yùn)算，進(jìn)一步降低hash碰撞的概率，使得數(shù)據(jù)分布更平均，我們把這樣的操作稱為擾動(dòng)，在JDK 1.8中的hash()函數(shù)如下：
static final inthash(Object key){
int h;
return(key ==null) ?0: (h = key.hashCode()) ^ (h >>>16);// 與自己右移16位進(jìn)行異或運(yùn)算（高低位異或）
}
這比在JDK 1.7中，更為簡(jiǎn)潔，相比在1.7中的4次位運(yùn)算，5次異或運(yùn)算（9次擾動(dòng)），在1.8中，只進(jìn)行了1次位運(yùn)算和1次異或運(yùn)算（2次擾動(dòng)）；
通過上面的鏈地址法（使用散列表）和擾動(dòng)函數(shù)我們成功讓我們的數(shù)據(jù)分布更平均，哈希碰撞減少，但是當(dāng)我們的HashMap中存在大量數(shù)據(jù)時(shí)，加入我們某個(gè)bucket下對(duì)應(yīng)的鏈表有n個(gè)元素，那么遍歷時(shí)間復(fù)雜度就為O(n)，為了針對(duì)這個(gè)問題，JDK1.8在HashMap中新增了紅黑樹的數(shù)據(jù)結(jié)構(gòu)，進(jìn)一步使得遍歷復(fù)雜度降低至O(logn)；
總結(jié)
簡(jiǎn)單總結(jié)一下HashMap是使用了哪些方法來有效解決哈希沖突的：
1. 使用鏈地址法（使用散列表）來鏈接擁有相同hash值的數(shù)據(jù)；
2. 使用2次擾動(dòng)函數(shù)（hash函數(shù)）來降低哈希沖突的概率，使得數(shù)據(jù)分布更平均；
3. 引入紅黑樹進(jìn)一步降低遍歷的時(shí)間復(fù)雜度，使得遍歷更快；
TreeMap 是采用什么樹實(shí)現(xiàn)的？TreeMap、HashMap、LindedHashMap的區(qū)別。
答：TreeMap的實(shí)現(xiàn)是紅黑樹算法的實(shí)現(xiàn)，LinkedHashMap可以保證HashMap集合有序。存入的順序和取出的順序一致。TreeMap實(shí)現(xiàn)SortMap接口，能夠把它保存的記錄根據(jù)鍵排序,默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器，當(dāng)用Iterator 遍歷TreeMap時(shí)，得到的記錄是排過序的。HashMap不保證順序，即為無序的，具有很快的訪問速度。HashMap最多只允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步。
4.數(shù)組
在java中，聲明一個(gè)數(shù)組過程中，是如何分配內(nèi)存的？
答：1.當(dāng)聲明數(shù)組類型變量時(shí)，為其分配了（32位）引用空間，由于未賦值，因此并不指向任何對(duì)象；
2.當(dāng)創(chuàng)建了一個(gè)數(shù)組對(duì)象（也就是new出來的）并將其地址賦值給了變量，其中創(chuàng)建出來的那幾個(gè)數(shù)組元素相當(dāng)于引用類型變量，因此各自占用（32位的）引用空間并按其默認(rèn)初始化規(guī)則被賦值為null
3.程序繼續(xù)運(yùn)行，當(dāng)創(chuàng)建新的對(duì)象并（將其地址）賦值給各數(shù)組元素，此時(shí)堆內(nèi)存就會(huì)有值了
怎么判斷數(shù)組是 null 還是為空
答：1.數(shù)組為null和數(shù)組為空的區(qū)別
數(shù)組為null：是創(chuàng)建了數(shù)組的引用，但在堆中并沒有數(shù)組中的元素
例：
int[] array1 = null;
array1是數(shù)組類型的空引用，棧中名為array1的內(nèi)存空間沒有存放任何地址。
數(shù)組為空：數(shù)組是空其實(shí)就是數(shù)組的長(zhǎng)度為0，數(shù)組是真正的對(duì)象，只是對(duì)象中沒有元素，也就是說里面沒有內(nèi)容
例：
int[] array = {};
此時(shí)創(chuàng)建了數(shù)組，數(shù)組的長(zhǎng)度為0，是一個(gè)空數(shù)組，但是array不是null，它也是一個(gè)對(duì)象，只不過它的元素個(gè)數(shù)為0。
2.判斷數(shù)組是否為空?
判斷數(shù)組為空，使用array.length==0可以
但array==null不可以，這種會(huì)報(bào)錯(cuò)，Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
3.判斷數(shù)組是否為null?
直接使用變量名==null
例：
String[ ]? arr = null;
if(arr == null){......}
