最近校招季材鹦，特把自己面試中遇到的問(wèn)題整理整理逝淹，以鞏固自己的知識(shí)。
Java中對(duì)于容器有兩大類存儲(chǔ)方式桶唐，一種是單元素存放创橄，還有一種就是key-value這種有關(guān)聯(lián)的雙元素存放了。對(duì)于Java中的容器莽红，有下列的結(jié)構(gòu)圖可以參照：
Collection （用來(lái)存放獨(dú)立元素的序列）
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
├HashSet
└TreeSet
Map （用來(lái)存放key-value型的元素對(duì)）
├Hashtable
├HashMap
├TreeMap
└WeakHashMap
下面妥畏，我們就來(lái)分別講講這幾種容器。
List
List是有序的Collection安吁，使用此接口能控制每個(gè)元素插入的位置醉蚁，用戶能夠使用索引來(lái)訪問(wèn)元素。與Set不同的是鬼店，List允許有重復(fù)的元素在其中网棍。
-
ArrayList
ArrayList相當(dāng)于順式存儲(chǔ)（線性表），當(dāng)實(shí)例化一個(gè)ArrayList時(shí)妇智，一個(gè)數(shù)組也被實(shí)例化了滥玷，默認(rèn)初始化一個(gè)長(zhǎng)度為10的數(shù)組氏身。當(dāng)添加數(shù)據(jù)的時(shí)候會(huì)判斷當(dāng)前容量是否能夠容下新增的對(duì)象，一旦發(fā)現(xiàn)容量不足惑畴，會(huì)自動(dòng)擴(kuò)容蛋欣，新的大小為原有容量的1.5倍+1。ArrayList可以快速隨機(jī)訪問(wèn)如贷，通過(guò)調(diào)用get(i)方法來(lái)訪問(wèn)下標(biāo)為i的元素陷虎。
-
LindedList
LinkedList相當(dāng)于鏈?zhǔn)酱鎯?chǔ)（雙向鏈表），它是通過(guò)節(jié)點(diǎn)直接彼此連接來(lái)實(shí)現(xiàn)的杠袱。每一個(gè)節(jié)點(diǎn)都包括前一個(gè)節(jié)點(diǎn)的引用尚猿，后一個(gè)節(jié)點(diǎn)的引用和節(jié)點(diǎn)存儲(chǔ)的值。
當(dāng)插入或刪除節(jié)點(diǎn)時(shí)楣富，只需要修改其中保持先后關(guān)系的節(jié)點(diǎn)的引用即可凿掂，所以，操作其中的對(duì)象速度比ArrayList要快的多纹蝴。但是LinkedList不能隨機(jī)訪問(wèn)元素缠劝，雖然它有g(shù)et()方法，但是這個(gè)方法是通過(guò)遍歷節(jié)點(diǎn)來(lái)定位的骗灶，速度很慢惨恭。
-
Vector
Vector和ArrayList一樣，也是用數(shù)組來(lái)存儲(chǔ)元素耙旦。但是Vector使用了synchronized方法脱羡，線程安全，所以在性能上比ArrayList要差免都。
ArrayList和LinkedList的區(qū)別
- ArrayList實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)锉罐，LinkedList實(shí)現(xiàn)了基于鏈表的數(shù)據(jù)結(jié)構(gòu)
- 對(duì)于隨機(jī)訪問(wèn)get和set，ArrayList優(yōu)于LinkedList
- 對(duì)于增刪add和remove绕娘，LinkedList優(yōu)于ArrayList
Set
Set是一種不包含重復(fù)元素的Collection脓规，它的構(gòu)造函數(shù)有一個(gè)約束條件，傳入的Collection參數(shù)不能包含重復(fù)的元素险领。
-
HashSet
HashSet實(shí)現(xiàn)了Set接口侨舆，由哈希表支持。它不保證Set的迭代順序绢陌，特別是它不保證該順序恒久不變挨下。HashSet底層使用的容器實(shí)際上就是HashMap，它以HashMap的key來(lái)保存所有的元素脐湾，value使用一個(gè)static final的Object對(duì)象來(lái)標(biāo)識(shí)臭笆。
private static final Object PRESENT = new Object(); -
TreeSet
TreeSet整體上性能沒(méi)有HashSet好，但是它可以維持元素的排序狀態(tài)。TreeSet底層使用的容器實(shí)際上就是TreeMap愁铺，它以TreeMap的key來(lái)保存set集合的元素鹰霍，value都以一個(gè)名為PRESENT的Object對(duì)象代替（無(wú)實(shí)際意義）。
Map
Map接口提供key到value的映射茵乱，一個(gè)Map不能包含相同的key茂洒，每個(gè)key只能映射一個(gè)value。
HashMap
HashMap底層就是一個(gè)數(shù)組結(jié)構(gòu)似将，數(shù)組中的每一項(xiàng)又是一個(gè)鏈表(其實(shí)就是哈希表的拉鏈法實(shí)現(xiàn))获黔。但是此類不保證映射的順序蚀苛，特別是不保證該順序恒久不變在验。但是TreeMap可以維持映射的順序。Hashtable
和HashMap實(shí)現(xiàn)差不多堵未，具體區(qū)別見(jiàn)下面的Hashtable和HashMap的區(qū)別腋舌。-
TreeMap
TreeMap的底層實(shí)現(xiàn)是一個(gè)紅黑樹(shù)結(jié)構(gòu)，這樣可以保證快速檢索節(jié)點(diǎn)渗蟹，TreeMap可以維持映射的順序块饺。下面我們來(lái)具體說(shuō)下TreeMap的底層實(shí)現(xiàn)，首先我們需要了解下排序二叉樹(shù)：
- 排序二叉樹(shù)：要么是一棵空二叉樹(shù)雌芽，要么是具有下列性質(zhì)的二叉樹(shù)：
- 若它的左子樹(shù)不為空授艰，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值
- 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值
- 它的左右自子樹(shù)也分別為排序二叉樹(shù)
對(duì)于排序二叉樹(shù)世落，它的中序遍歷就可以得到由小到大的有序序列淮腾，所以用它就可以實(shí)現(xiàn)快速檢索，但是為什么Java還要多此一舉用紅黑樹(shù)呢屉佳？
- 排序二叉樹(shù)雖然可以快速檢索谷朝，但是在最壞情況下：若插入的節(jié)點(diǎn)本身就是有序的，要么由小到大排列武花，要么由大到小排列圆凰，那么最后得到的排序二叉樹(shù)就變?yōu)榱随湵恚核械墓?jié)點(diǎn)只有左節(jié)點(diǎn)或者所有的節(jié)點(diǎn)只有右節(jié)點(diǎn)。這種情況下体箕，排序二叉樹(shù)就變?yōu)榱似胀ㄦ湵碜ǘぃ瑱z索效率會(huì)很差。
所以累铅，Java引入了紅黑樹(shù)作為TreeMap的底層實(shí)現(xiàn)
-
紅黑樹(shù)：紅黑樹(shù)是一種更高效的檢索二叉樹(shù)驶沼，它的性質(zhì)為：
- 所有的節(jié)點(diǎn)都為紅色或者黑色
- 根節(jié)點(diǎn)永遠(yuǎn)是黑色
- 所有的葉節(jié)點(diǎn)都是空節(jié)點(diǎn)（NULL），并且是黑色
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色争群，即從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上不會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)回怜。
- 從任一節(jié)點(diǎn)到其子樹(shù)中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)
紅黑樹(shù)通過(guò)上面的限制來(lái)保證它大致是平衡的（因?yàn)榧t黑樹(shù)的高度不會(huì)無(wú)限增高），這樣保證了紅黑樹(shù)在最壞情況下都是高效的，不會(huì)出現(xiàn)普通排序二叉樹(shù)的情況玉雾。
- 排序二叉樹(shù)：要么是一棵空二叉樹(shù)雌芽，要么是具有下列性質(zhì)的二叉樹(shù)：
Hashtable和HashMap的區(qū)別
繼承和實(shí)現(xiàn)不同
Hashtable是繼承自陳舊的Dictionary類翔试，實(shí)現(xiàn)了Map接口；HashMap實(shí)現(xiàn)接口（繼承自AbstractMap复旬，AbstractMap實(shí)現(xiàn)Map接口）線程安全不同
Hashtable是線程安全的垦缅，它的實(shí)現(xiàn)方法里面都添加了synchronized關(guān)鍵字來(lái)確保線程同步。HashMap是線程不安全的驹碍，在多線程編程下如使用HashMap需要使用Collections.synchronizedMap()來(lái)獲取一個(gè)線程安全的集合壁涎。對(duì)null的處理不同
HashMap支持null作為key和value，但是Hashtable不允許（key志秃，value都不允許）怔球。HashMap的方法get()返回null時(shí)，既可以表示沒(méi)有改鍵浮还，也可以表示該鍵對(duì)應(yīng)的值為null竟坛，所以不能用此判斷是否有該鍵，而應(yīng)該用containsKey()钧舌。HashMap初始容量為16担汤，Hashtable初始容量為11。HashMap擴(kuò)容時(shí)是當(dāng)前容量翻倍：capacity2洼冻，Hashtable是當(dāng)前容量翻倍+1：capacity2+1崭歧。
哈希值的使用不同
Hashtable直接使用key的hashcode對(duì)table數(shù)組的長(zhǎng)度取模，HashMap是對(duì)key的hashcode進(jìn)行二次hash撞牢，然后對(duì)table數(shù)組的長(zhǎng)度取模率碾，以獲得更好的散列值。
