Hello，今天給各位童鞋們分享java常見的面試題柠辞，想在面試团秽、工作中脫穎而出？想在最短的時(shí)間內(nèi)快速掌握 Java 的核心基礎(chǔ)知識(shí)點(diǎn)叭首？那趕緊拿出小本本記下來(lái)吧习勤！

1. List，Set焙格，Map三者的區(qū)別图毕？

List：一個(gè)有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復(fù)间螟，可以插入多個(gè)null元素吴旋，元素都有索引。常用的實(shí)現(xiàn)類有 ArrayList厢破、LinkedList 和 Vector

Set：一個(gè)無(wú)序（存入和取出順序有可能不一致）容器荣瑟，不可以存儲(chǔ)重復(fù)元素，只允許存入一個(gè)null元素摩泪，必須保證元素唯一性笆焰。Set 接口常用實(shí)現(xiàn)類是 HashSet、LinkedHashSet 以及 TreeSet

Map是一個(gè)鍵值對(duì)集合见坑，存儲(chǔ)鍵嚷掠、值和之間的映射捏检。 Key無(wú)序，唯一不皆；value 不要求有序贯城，允許重復(fù)。Map 的常用實(shí)現(xiàn)類：HashMap霹娄、TreeMap能犯、HashTable、LinkedHashMap犬耻、ConcurrentHashMap

2. 集合框架底層的數(shù)據(jù)結(jié)構(gòu)

List集合

Arraylist和Vector使用的是 Object 數(shù)組踩晶， LinkedList使用雙向循環(huán)鏈表

Set集合

HashSet（無(wú)序，唯一）：基于 HashMap 實(shí)現(xiàn)的枕磁，HashSet的值作為key渡蜻，value是Object類型的常量

LinkedHashSet繼承HashSet，并且通過 LinkedHashMap 來(lái)實(shí)現(xiàn)的

TreeSet（有序计济，唯一）： 紅黑樹(自平衡的排序二叉樹茸苇。)

Map集合

HashMap由數(shù)組+鏈表+紅黑樹組成的，數(shù)組是HashMap的主體沦寂，鏈表則是主要為了解決哈希沖突而存在的税弃，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）并且數(shù)組長(zhǎng)度大于64時(shí)，將鏈表轉(zhuǎn)化為紅黑樹

LinkedHashMap（有序） 繼承自 HashMap凑队，底層仍然是數(shù)組+鏈表+紅黑樹組成。另外幔翰，LinkedHashMap 在此基礎(chǔ)上漩氨，節(jié)點(diǎn)之間增加了一條雙向鏈表，使得可以保持鍵值對(duì)的插入順序

HashTable無(wú)序遗增，數(shù)組+鏈表組成的叫惊，數(shù)組是 HashTable的主體，鏈表則是主要為了解決哈希沖突而存在的

TreeMap有序做修，紅黑樹

3. 集合框架的擴(kuò)容

ArrayList和Vector默認(rèn)初始容量為10，當(dāng)元素個(gè)數(shù)超過容量長(zhǎng)度時(shí)都進(jìn)行進(jìn)行擴(kuò)容，ArrayList擴(kuò)容為原來(lái)的1.5倍怔揩，而Vector擴(kuò)容為原來(lái)的2倍

HashSet和HashMap默認(rèn)初始容量為16砰奕，加載因子為0.75：即當(dāng)元素個(gè)數(shù)超過容量長(zhǎng)度的0.75倍時(shí)，進(jìn)行擴(kuò)容燎含，擴(kuò)容為原來(lái)的2倍宾濒。HashSet基于 HashMap 實(shí)現(xiàn)的，因此兩者相同

HashTable：默認(rèn)初始容量為11屏箍，加載因子為0.75绘梦，擴(kuò)容策略是2倍+1橘忱，如 初始的容量為11，一次擴(kuò)容后是容量為23

4. HashMap 的實(shí)現(xiàn)原理以及JDK1.7和JDK1.8的區(qū)別卸奉？

實(shí)現(xiàn)原理

數(shù)組的特點(diǎn)是：尋址容易钝诚，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難榄棵，插入和刪除容易凝颇。我們綜合兩者的特性，做出一種尋址容易秉继，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)哈希表祈噪。并且使用最常用的一種方法—— 拉鏈法來(lái)實(shí)現(xiàn)哈希表。

數(shù)組存儲(chǔ)的元素是一個(gè)Entry類尚辑，這個(gè)類有三個(gè)數(shù)據(jù)域辑鲤，key、value（鍵值對(duì)）杠茬，next(指向下一個(gè)Entry)月褥。當(dāng)兩個(gè)key經(jīng)過計(jì)算得到的index（索引）相同時(shí)，即產(chǎn)生哈希沖突時(shí)瓢喉，用鏈地址法來(lái)解決哈希沖突宁赤，即通過next屬性將索引值相同的鏈接在一起。隨著map的容量或者鏈表長(zhǎng)度越來(lái)越大栓票，在進(jìn)行進(jìn)一步的優(yōu)化决左，比如使用紅黑樹。

存儲(chǔ)過程

HashMap個(gè)put()方法：

第一步首先將k,v封裝成Node節(jié)點(diǎn)走贪。第二步調(diào)用hashCode()方法得出hash值并將hash值轉(zhuǎn)換成數(shù)組的下標(biāo)佛猛，下標(biāo)位置上如果沒有任何元素（沒有碰撞），就把Node節(jié)點(diǎn)添加到這個(gè)位置上坠狡。如果說(shuō)下標(biāo)對(duì)應(yīng)的位置上有值（hash碰撞）继找。碰撞的元素與要插入的元素key值相等，直接進(jìn)行value的更新逃沿；如果key值不相同婴渡，于是增長(zhǎng)鏈表或者樹節(jié)點(diǎn)的增加。插入之后判斷是否進(jìn)行擴(kuò)容凯亮。

HashMap個(gè)get()方法：

先調(diào)用k的hashCode()方法得出哈希值边臼，并轉(zhuǎn)換成數(shù)組的下標(biāo)。第二步：通過數(shù)組下標(biāo)快速定位到某個(gè)位置上触幼。如果該位置上什么都沒有硼瓣，則返回null。如果這個(gè)位置上有數(shù)據(jù)，那么它就會(huì)拿著參數(shù)k和單向鏈表上(紅黑樹)的每一個(gè)節(jié)點(diǎn)的k進(jìn)行equals堂鲤，如果所有equals方法都返回false亿傅，則get方法返回null。如果其中一個(gè)節(jié)點(diǎn)的k和參數(shù)k進(jìn)行equals返回true瘟栖，那么返回該節(jié)點(diǎn)的value葵擎。

區(qū)別

JDK1.7是數(shù)組+鏈表，無(wú)沖突時(shí)半哟，存放數(shù)組酬滤；沖突時(shí)，存放鏈表寓涨；采用頭插法盯串。

JDK1.8是數(shù)組 + 鏈表 + 紅黑樹，無(wú)沖突時(shí)戒良，存放數(shù)組体捏；有沖突存放鏈表或者紅黑樹，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）并且數(shù)組長(zhǎng)度大于64時(shí)糯崎，將鏈表轉(zhuǎn)化為紅黑樹几缭；樹元素小于等于6時(shí)，樹結(jié)構(gòu)還原成鏈表形式沃呢。

5. HashMap是怎么解決哈希沖突的年栓？

使用鏈地址法（鏈表）來(lái)鏈接擁有相同hash值的數(shù)據(jù)；

使用2次擾動(dòng)函數(shù)（hash函數(shù)）來(lái)降低哈希沖突的概率薄霜，使得數(shù)據(jù)分布更平均某抓；

引入紅黑樹進(jìn)一步降低遍歷的時(shí)間復(fù)雜度，使得遍歷更快惰瓜；

擾動(dòng)函數(shù)的解釋：

如果只使用hashCode取余搪缨，那么相當(dāng)于參與運(yùn)算的只有hashCode的低位，高位是沒有起到任何作用的鸵熟，所以我們的思路就是讓hashCode的高位（與自己右移16位進(jìn)行異或）也參與運(yùn)算，來(lái)獲取hash值负甸，進(jìn)一步降低hash碰撞的概率流强，使得數(shù)據(jù)分布更平均，我們把這樣的操作稱為擾動(dòng)呻待。

6. 為什么默認(rèn)長(zhǎng)度和擴(kuò)容后的長(zhǎng)度都必須是 2 的冪

獲取數(shù)組索引的計(jì)算方式為 key 的 hash 值與數(shù)組長(zhǎng)度減一按位與打月，當(dāng)長(zhǎng)度為 2 的冪時(shí)減一的值的二進(jìn)制位數(shù)一定全為 1，這樣數(shù)組下標(biāo) index 的值完全取決于 key 的 hash 值的后幾位蚕捉，只要key 的 hash 值分布均勻奏篙，HashMap 中Node也就盡可能是均勻的，所以當(dāng)長(zhǎng)度為 2 的冪時(shí)不同的 hash 值發(fā)生碰撞的概率比較小。

7. HashMap的數(shù)據(jù)的遷移機(jī)制

由于數(shù)組的容量是以2的冪次方擴(kuò)容的秘通，新的位置要么在原位置为严，要么在原長(zhǎng)度+原位置的位置。因?yàn)閿?shù)組長(zhǎng)度變?yōu)樵瓉?lái)的2倍肺稀，表現(xiàn)為key 的 hash 值在二進(jìn)制上就是多了一個(gè)高位參與數(shù)組下標(biāo)確定第股。此時(shí)，一個(gè)元素通過hash轉(zhuǎn)換坐標(biāo)的方法計(jì)算后话原，恰好出現(xiàn)一個(gè)現(xiàn)象：最高位是0則坐標(biāo)不變夕吻，最高位是1則坐標(biāo)變?yōu)椤霸L(zhǎng)度+原坐標(biāo)”。 因此繁仁，我們?cè)跀U(kuò)充HashMap的時(shí)候涉馅，不需要像JDK1.7的實(shí)現(xiàn)那樣重新計(jì)算hash，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好黄虱。

例如：HashMap擴(kuò)容之前為16稚矿，那么length-1的二進(jìn)制為01111，同理擴(kuò)容后的數(shù)組長(zhǎng)度為32悬钳，length-1二進(jìn)制表示為011111盐捷。我們可以看出擴(kuò)容后只有一位差異，也就是多出了最左位的1默勾，這樣在通過 h&(length-1)的時(shí)候碉渡，只要h對(duì)應(yīng)的最左邊的那一個(gè)差異位為0，那么就是在原先位置母剥；差異位為1滞诺，就在原長(zhǎng)度+原位置

8. ConcurrentHashMap 底層具體實(shí)現(xiàn)

在 JDK1.7 中，ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成环疼。Segment 繼承了 ReentrantLock习霹，是一種可重入鎖。HashEntry 則用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)炫隶。一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組淋叶，一個(gè) Segment 里包含一個(gè) HashEntry 數(shù)組 ，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素伪阶，因此 JDK1.7 的 ConcurrentHashMap 是一種數(shù)組+鏈表結(jié)構(gòu)煞檩。當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得與它對(duì)應(yīng)的 Segment 鎖栅贴，這樣只要保證每個(gè) Segment 是線程安全的斟湃，也就實(shí)現(xiàn)了全局的線程安全

在 JDK1.8 中采用Node + CAS + Synchronized來(lái)保證并發(fā)安全進(jìn)行實(shí)現(xiàn)，synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)檐薯。如果相應(yīng)位置的Node還沒有初始化凝赛，則調(diào)用CAS插入相應(yīng)的數(shù)據(jù)；如果相應(yīng)位置的Node不為空，如果該節(jié)點(diǎn)的first.hash!=-1墓猎，則對(duì)該節(jié)點(diǎn)加synchronized鎖捆昏，更新節(jié)點(diǎn)或插入新節(jié)點(diǎn)； 如果該節(jié)點(diǎn)的first.hash=-1陶衅，則擴(kuò)容屡立。讀操作無(wú)鎖，Node節(jié)點(diǎn)的val和next使用volatile修飾搀军，數(shù)組也用volatile修飾膨俐。

好啦，今天的文章就到這里罩句，希望能幫助到屏幕前的你們焚刺！