集合常見面試題總結(jié)

List

1、List常見實(shí)現(xiàn)類
①底層數(shù)據(jù)結(jié)構(gòu)基于"Object數(shù)組"的ArrayList
②底層數(shù)據(jù)結(jié)構(gòu)基于"Object數(shù)組"的線程安全的Vector
③底層數(shù)據(jù)結(jié)構(gòu)基于"雙向鏈表"的LinkedList【JDK1.6之前為循環(huán)雙向鏈表，JKD1.7取消了 循環(huán)】
2、Arraylist 與 LinkedList 區(qū)別?
①相同點(diǎn)：Arraylist 與 LinkedList都是線程不安全的，性能效率相對(duì)較高
②底層數(shù)據(jù)結(jié)構(gòu)不同：ArrayList基于"Object數(shù)組"，LinkedList基于"雙向鏈表"【JDK1.6之 前為循環(huán)雙向鏈表，JKD1.7取消了循環(huán)】
③ArrayList有擴(kuò)容機(jī)制，初始化長度為10【按照無參構(gòu)造方法創(chuàng)建集合，底層數(shù)組長度默 認(rèn)為0，第一次調(diào)用add()添加元素?cái)?shù)組長度變?yōu)?0；按照有參構(gòu)造方法創(chuàng)建集合，長度為 創(chuàng)建時(shí)指定長度】，之后調(diào)用grow()按照原有容量的1.5倍擴(kuò)容，最大容量為 Integer.MAX_VALUE-8或Integer.MAX_VALUE LinkedList沒有擴(kuò)容機(jī)制，添加元素在前面或后面直接添加
④ArrayList實(shí)現(xiàn)了RandomAccess接口【標(biāo)志性接口】，支持下標(biāo)快速隨機(jī)訪問，由于底 層數(shù)據(jù)結(jié)構(gòu)為數(shù)組插入刪除效率低；LinkedList沒有實(shí)現(xiàn)RandomAccess接口，不支持快速 隨機(jī)訪問，地層結(jié)構(gòu)是雙向鏈表插入刪除效率高
3、ArrayList 與 Vector 區(qū)別呢?
①相同點(diǎn)：底層數(shù)據(jù)結(jié)構(gòu)相同，都是基于"Object"數(shù)組
②線程安全不同：ArrayList是線程不安全的，效率高；Vector是線程安全的（有 synchronized關(guān)鍵字修飾），效率低
③擴(kuò)容機(jī)制不同：ArrayList的初始容量為0，第一次調(diào)用add()方法時(shí)，容量變?yōu)?0，之后 調(diào)用grow()方法按照原有容量1.5倍增長；Vector的初始容量為10，之后調(diào)用grow()按照原 有的2倍增長
4、ArrayList 的擴(kuò)容機(jī)制？ ArrayList擴(kuò)容機(jī)制，初始化長度為10【按照無參構(gòu)造方法創(chuàng)建集合，底層數(shù)組長度默認(rèn)為 0，第一次調(diào)用add()添加元素?cái)?shù)組長度變?yōu)?0；按照有參構(gòu)造方法創(chuàng)建集合，長度為創(chuàng)建時(shí)指定長度】，之后調(diào)用grow()按照原有容量的1.5倍擴(kuò)容，最大容量為 Integer.MAX_VALUE-8或Integer.MAX_VALUE

Set

1、HashSet如何檢查元素重復(fù)？
通過hashCode()和equals()方法檢查重復(fù)

Map

1、HashMap 和 HashTable的區(qū)別?
①存儲(chǔ)方式不同：HashMap在JDK1.7底層數(shù)據(jù)結(jié)構(gòu)采用"數(shù)組"+"鏈表"；JDK1.8底層數(shù)據(jù) 結(jié)構(gòu)采用"數(shù)組"+"鏈表"+"紅黑樹"【當(dāng)鏈表長度大于閾值8時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，以減 少搜索時(shí)間】；HashTable底層數(shù)據(jù)結(jié)構(gòu)為"數(shù)組"+"鏈表"
②擴(kuò)容機(jī)制不同：HashMap初始容量為16，加載因子為0.75，當(dāng)元素個(gè)數(shù)超過容量的0.75 倍，按照原有容量的2倍進(jìn)行擴(kuò)容；HashTable初始容量為11，按照原有容量的2n+1進(jìn)行 擴(kuò)容
③線程安全不同：HashMap是線程不安全的，性能效率較高；HashTable是線程安全的， 性能效率相對(duì)較低
④HashMap允許Null Key 和 Null Value，Null Key只允許有一個(gè)，Null Value允許有多 個(gè)；HashTable不允許Null Key 和 Null Value，會(huì)導(dǎo)致NullPointerException
2、HashMap 和 HashSet區(qū)別?
①HashMap是以鍵值對(duì)存儲(chǔ)數(shù)據(jù)的，鍵不允許重復(fù)值可以重復(fù)；HashSet中存儲(chǔ)的元素是 無序、不允許重復(fù)的
②實(shí)現(xiàn)接口不同：HashMap實(shí)現(xiàn)的是Map接口；HashSet實(shí)現(xiàn)的是Set接口
3、HashMap的底層實(shí)現(xiàn)?
HashMap是基于HashTable實(shí)現(xiàn)的，在JDK1.7底層數(shù)據(jù)結(jié)構(gòu)采用"數(shù)組"+"鏈表"；JDK1.8 底層數(shù)據(jù)結(jié)構(gòu)采用"數(shù)組"+"鏈表"+"紅黑樹"【當(dāng)鏈表長度大于閾值8時(shí)，將鏈表轉(zhuǎn)換為紅黑 樹，以減少搜索時(shí)間】
4、HashMap 的長度為什么是2的冪次方?
HashMap為了存取高效，要盡量較少碰撞，要盡量把數(shù)據(jù)分配均勻