1.???? HashMap的源碼，實(shí)現(xiàn)原理，JDK8中對(duì)HashMap做了怎樣的優(yōu)化。

在JDK1.6，JDK1.7中，HashMap采用位桶+鏈表實(shí)現(xiàn)，即使用鏈表處理沖突，同一hash值的鏈表都存儲(chǔ)在一個(gè)鏈表里。HashMap由鏈表+數(shù)組組成，他的底層結(jié)構(gòu)是一個(gè)數(shù)組，而數(shù)組的元素是一個(gè)單向鏈表。但是當(dāng)位于一個(gè)桶中的元素較多，即hash值相等的元素較多時(shí)，通過key值依次查找的效率較低。而JDK1.8中，HashMap采用位桶+鏈表+紅黑樹實(shí)現(xiàn)，當(dāng)鏈表長度超過閾值（8）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，這樣大大減少了查找時(shí)間。

簡單說下HashMap的實(shí)現(xiàn)原理：

首先有一個(gè)每個(gè)元素都是鏈表（可能表述不準(zhǔn)確）的數(shù)組，當(dāng)添加一個(gè)元素（key-value）時(shí)，就首先計(jì)算元素key的hash值，以此確定插入數(shù)組中的位置，但是可能存在同一hash值的元素已經(jīng)被放在數(shù)組同一位置了，這時(shí)就添加到同一hash值的元素的后面，他們?cè)跀?shù)組的同一位置，但是形成了鏈表，同一各鏈表上的Hash值是相同的，所以說數(shù)組存放的是鏈表。而當(dāng)鏈表長度太長時(shí)，鏈表就轉(zhuǎn)換為紅黑樹，這樣大大提高了查找的效率。

當(dāng)鏈表數(shù)組的容量超過初始容量的0.75時(shí)，再散列將鏈表數(shù)組擴(kuò)大2倍，把原鏈表數(shù)組的搬移到新的數(shù)組中

存取機(jī)制：

HashMap如何getValue值，看源碼：

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab;//Entry對(duì)象數(shù)組 Node<K,V> first,e; //在tab數(shù)組中經(jīng)過散列的第一個(gè)位置 int n; K k; /*找到插入的第一個(gè)Node，方法是hash值和n-1相與，tab[(n - 1) & hash]*/ //也就是說在一條鏈上的hash值相同的 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { /*檢查第一個(gè)Node是不是要找的Node*/ if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//判斷條件是hash值要相同，key值要相同 return first; /*檢查first后面的node*/ if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); /*遍歷后面的鏈表，找到key值和hash值都相同的Node*/ do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } View Code

get(key)方法時(shí)獲取key的hash值，計(jì)算hash&(n-1)得到在鏈表數(shù)組中的位置first=tab[hash&(n-1)],先判斷first的key是否與參數(shù)key相等，不等就遍歷后面的鏈表找到相同的key值返回對(duì)應(yīng)的Value值即可

HashMap如何put(key，value);看源碼

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /*如果table的在（n-1）&hash的值是空，就新建一個(gè)節(jié)點(diǎn)插入在該位置*/ if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); /*表示有沖突,開始處理沖突*/ else { Node<K,V> e; K k; /*檢查第一個(gè)Node，p是不是要找的值*/ if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { /*指針為空就掛在后面*/ if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果沖突的節(jié)點(diǎn)數(shù)已經(jīng)達(dá)到8個(gè)，看是否需要改變沖突節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)，　　　　　　　　　　　　　 //treeifyBin首先判斷當(dāng)前hashMap的長度，如果不足64，只進(jìn)行 //resize，擴(kuò)容table，如果達(dá)到64，那么將沖突的存儲(chǔ)結(jié)構(gòu)為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } /*如果有相同的key值就結(jié)束遍歷*/ if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } /*就是鏈表上有相同的key值*/ if (e != null) { // existing mapping for key，就是key的Value存在 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue;//返回存在的Value值 } } ++modCount; /*如果當(dāng)前大小大于門限，門限原本是初始容量*0.75*/ if (++size > threshold) resize();//擴(kuò)容兩倍 afterNodeInsertion(evict); return null; } View Code

下面簡單說下添加鍵值對(duì)put(key,value)的過程：

1，判斷鍵值對(duì)數(shù)組tab[]是否為空或?yàn)閚ull，否則以默認(rèn)大小resize()；

2，根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果tab[i]==null，直接新建節(jié)點(diǎn)添加，否則轉(zhuǎn)入3

3，判斷當(dāng)前數(shù)組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個(gè)節(jié)點(diǎn)類型即可),分別處理

?

2.???? HaspMap擴(kuò)容是怎樣擴(kuò)容的，為什么都是2的N次冪的大小。

HashMap使用的是懶加載，構(gòu)造完HashMap對(duì)象后，只要不進(jìn)行put 方法插入元素之前，HashMap并不會(huì)去初始化或者擴(kuò)容table：

若threshold（閾值）不為空，table的首次初始化大小為閾值，否則初始化為缺省值大小16

當(dāng)table需要擴(kuò)容時(shí)，擴(kuò)容后的table大小變?yōu)樵瓉淼膬杀?#xff0c;接下來就是進(jìn)行擴(kuò)容后table的調(diào)整：假設(shè)擴(kuò)容前的table大小為2的N次方，有put方法解析可知，元素的table索引為其hash值的后N位確定，那么擴(kuò)容后的table大小即為2的N+1次方，則其中元素的table索引為其hash值的后N+1位確定，比原來多了一位

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; //創(chuàng)建一個(gè)oldTab數(shù)組用于保存之前的數(shù)組int oldCap = (oldTab == null) ? 0 : oldTab.length; //獲取原來數(shù)組的長度int oldThr = threshold; //原來數(shù)組擴(kuò)容的臨界值int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) { //如果原來的數(shù)組長度大于最大值(2^30)threshold = Integer.MAX_VALUE; //擴(kuò)容臨界值提高到正無窮return oldTab; //返回原來的數(shù)組，也就是系統(tǒng)已經(jīng)管不了了，隨便你怎么玩吧 }//else if((新數(shù)組newCap)長度乘2) < 最大值(2^30) && (原來的數(shù)組長度)>= 初始長度(2^4))//這個(gè)else if 中實(shí)際上就是咋判斷新數(shù)組(此時(shí)剛創(chuàng)建還為空)和老數(shù)組的長度合法性，同時(shí)交代了，//我們擴(kuò)容是以2^1為單位擴(kuò)容的。下面的newThr(新數(shù)組的擴(kuò)容臨界值)一樣，在原有臨界值的基礎(chǔ)上擴(kuò)2^1else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold }else if (oldThr > 0)newCap = oldThr; //新數(shù)組的初始容量設(shè)置為老數(shù)組擴(kuò)容的臨界值else { // 否則 oldThr == 0,零初始閾值表示使用默認(rèn)值newCap = DEFAULT_INITIAL_CAPACITY; //新數(shù)組初始容量設(shè)置為默認(rèn)值newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //計(jì)算默認(rèn)容量下的閾值 }if (newThr == 0) { //如果newThr == 0，說明為上面 else if (oldThr > 0)//的情況(其他兩種情況都對(duì)newThr的值做了改變),此時(shí)newCap = oldThr;float ft = (float)newCap * loadFactor; //ft為臨時(shí)變量，用于判斷閾值的合法性newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE); //計(jì)算新的閾值 }threshold = newThr; //改變threshold值為新的閾值@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab; //改變table全局變量為，擴(kuò)容后的newTableif (oldTab != null) {for (int j = 0; j < oldCap; ++j) { //遍歷數(shù)組，將老數(shù)組(或者原來的桶)遷移到新的數(shù)組(新的桶)中Node<K,V> e;if ((e = oldTab[j]) != null) { //新建一個(gè)Node<K,V>類對(duì)象，用它來遍歷整個(gè)數(shù)組oldTab[j] = null;if (e.next == null)//將e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置，newTab[e.hash & (newCap - 1)] = e; //這個(gè)我們之前講過，是一個(gè)取模操作else if (e instanceof TreeNode) //如果e已經(jīng)是一個(gè)紅黑樹的元素，這個(gè)我們不展開講((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 鏈表重排，這一段是最難理解的，也是ldk1.8做的一系列優(yōu)化，我們?cè)谙旅嬖敿?xì)講解Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;} View Code

因此，table中的元素只有兩種情況：

元素hash值第N+1位為0：不需要進(jìn)行位置調(diào)整

元素hash值第N+1位為1：調(diào)整至原索引的兩倍位置

在resize方法中，確定元素hashi值第N+1位是否為0：

若為0，則使用loHead與loTail，將元素移至新table的原索引處

若不為0，則使用hiHead與hiHead，將元素移至新table的兩倍索引處

擴(kuò)容或初始化完成后，resize方法返回新的table

?

hashMap為啥初始化容量為2的次冪

hashMap源碼獲取元素的位置：

static int indexFor(int hashcode, int length) {

??? // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

??? return hashcode & (length-1);

}

如果length不為2的冪，比如15。那么length-1的2進(jìn)制就會(huì)變成1110。在h為隨機(jī)數(shù)的情況下，和1110做&操作。尾數(shù)永遠(yuǎn)為0。那么0001、1001、1101等尾數(shù)為1的位置就永遠(yuǎn)不可能被entry占用。這樣會(huì)造成浪費(fèi)，不隨機(jī)等問題

?

3.???? HashMap，HashTable，ConcurrentHashMap的區(qū)別。

HashTable

底層數(shù)組+鏈表實(shí)現(xiàn)，無論key還是value都不能為null，線程安全，實(shí)現(xiàn)線程安全的方式是在修改數(shù)據(jù)時(shí)鎖住整個(gè)HashTable，效率低，ConcurrentHashMap做了相關(guān)優(yōu)化

初始size為11，擴(kuò)容：newsize = olesize*2+1

計(jì)算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

底層數(shù)組+鏈表實(shí)現(xiàn)，可以存儲(chǔ)null鍵和null值，線程不安全

初始size為16，擴(kuò)容：newsize = oldsize*2，size一定為2的n次冪

擴(kuò)容針對(duì)整個(gè)Map，每次擴(kuò)容時(shí)，原來數(shù)組中的元素依次重新計(jì)算存放位置，并重新插入

插入元素后才判斷該不該擴(kuò)容，有可能無效擴(kuò)容（插入后如果擴(kuò)容，如果沒有再次插入，就會(huì)產(chǎn)生無效擴(kuò)容）

當(dāng)Map中元素總數(shù)超過Entry數(shù)組的75%，觸發(fā)擴(kuò)容操作，為了減少鏈表長度，元素分配更均勻

計(jì)算index方法：index = hash & (tab.length – 1)

ConcurrentHashMap

底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)，線程安全

通過把整個(gè)Map分為N個(gè)Segment，可以提供相同的線程安全，但是效率提升N倍，默認(rèn)提升16倍。(讀操作不加鎖，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值。)

Hashtable的synchronized是針對(duì)整張Hash表的，即每次鎖住整張表讓線程獨(dú)占，ConcurrentHashMap允許多個(gè)修改操作并發(fā)進(jìn)行，其關(guān)鍵在于使用了鎖分離技術(shù)

有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個(gè)表而而不僅僅是某個(gè)段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖

擴(kuò)容：段內(nèi)擴(kuò)容（段內(nèi)元素超過該段對(duì)應(yīng)Entry數(shù)組長度的75%觸發(fā)擴(kuò)容，不會(huì)對(duì)整個(gè)Map進(jìn)行擴(kuò)容），插入前檢測需不需要擴(kuò)容，有效避免無效擴(kuò)容

?

4.???? 極高并發(fā)下HashTable和ConcurrentHashMap哪個(gè)性能更好，為什么，如何實(shí)現(xiàn)的。

ConcurrentHashMap在多線程下效率更高

HashTable使用一把鎖處理并發(fā)問題，當(dāng)有多個(gè)線程訪問時(shí)，需要多個(gè)線程競爭一把鎖，導(dǎo)致阻塞

ConcurrentHashMap則使用分段，相當(dāng)于把一個(gè)HashMap分成多個(gè)，然后每個(gè)部分分配一把鎖，這樣就可以支持多線程訪問

推薦：https://blog.csdn.net/zhushuai1221/article/details/51706468

5.???? HashMap在高并發(fā)下如果沒有處理線程安全會(huì)有怎樣的安全隱患，具體表現(xiàn)是什么。

1、多線程put時(shí)可能會(huì)導(dǎo)致get無限循環(huán)，具體表現(xiàn)為CPU使用率100%；

原因：在向HashMap put元素時(shí)，會(huì)檢查HashMap的容量是否足夠，如果不足，則會(huì)新建一個(gè)比原來容量大兩倍的Hash表，然后把數(shù)組從老的Hash表中遷移到新的Hash表中，遷移的過程就是一個(gè)rehash()的過程，多個(gè)線程同時(shí)操作就有可能會(huì)形成循環(huán)鏈表，所以在使用get()時(shí)，就會(huì)出現(xiàn)Infinite Loop的情況

2、多線程put時(shí)可能導(dǎo)致元素丟失

原因：當(dāng)多個(gè)線程同時(shí)執(zhí)行addEntry(hash,key ,value,i)時(shí)，如果產(chǎn)生哈希碰撞，導(dǎo)致兩個(gè)線程得到同樣的bucketIndex去存儲(chǔ)，就可能會(huì)發(fā)生元素覆蓋丟失的情況

?

6.???? java中四種修飾符的限制范圍。

訪問權(quán)限	類	包	子類	其他包
public????	∨	∨	∨	∨
protect???	∨	∨	∨	×
default???	∨	∨	×	×
private???	∨	×	×	×

?

7.???? Object類中的方法。

equale()用于確認(rèn)兩個(gè)對(duì)象是否相同。 hashCode()用于獲取對(duì)象的哈希值，用于檢索 finalize()：這個(gè)函數(shù)在進(jìn)行垃圾回收的時(shí)候會(huì)用到，匿名對(duì)象回收之前會(huì)調(diào)用到 toString()返回一個(gè)String對(duì)象，用來標(biāo)識(shí)自己 getClass()返回一個(gè)Class對(duì)象 wait()用于讓當(dāng)前線程失去操作權(quán)限，當(dāng)前線程進(jìn)入等待序列 notify()用于隨機(jī)通知一個(gè)持有對(duì)象的鎖的線程獲取操作權(quán)限 notifyAll()用于通知所有持有對(duì)象的鎖的線程獲取操作權(quán)限 wait(long) 和wait(long,int)用于設(shè)定下一次獲取鎖的距離當(dāng)前釋放鎖的時(shí)間間隔

?

?

8.???? 接口和抽象類的區(qū)別，注意JDK8的接口可以有實(shí)現(xiàn)。

首先是相同的地方：

1. 接口和抽象類都能定義方法和屬性。

2. 接口和抽象類都是看作是一種特殊的類。大部分的時(shí)候，定義的方法要子類來實(shí)現(xiàn)

3. 抽象類和接口都可以不含有抽象方法。接口沒有方法就可以作為一個(gè)標(biāo)志。比如可序列化的接口Serializable，沒有方法的接口稱為空接口

4. 抽象類和接口都不能創(chuàng)建對(duì)象。

5. 抽象類和接口都能利用多態(tài)性原理來使用抽象類引用指向子類對(duì)象。

6. 繼承和實(shí)現(xiàn)接口或抽象類的子類必須實(shí)現(xiàn)接口或抽象類的所有的方法，抽象類若有沒有實(shí)現(xiàn)的方法就繼續(xù)作為抽象類，要加abstract修飾。若接口的子類沒有實(shí)現(xiàn)的方法，也要變?yōu)槌橄箢悺?/p>

?

下面是接口和抽象類的不同點(diǎn)：

1. 接口能夠多實(shí)現(xiàn)，而抽象類只能單獨(dú)被繼承，其本質(zhì)就是，一個(gè)類能繼承多個(gè)接口，而只能繼承一個(gè)抽象類。

2. 方法上，抽象類的方法可以用abstract 和public或者protect修飾。而接口默認(rèn)為public abttact 修飾。

3. 抽象類的方法可以有需要子類實(shí)現(xiàn)的抽象方法，也可以有具體的方法。而接口在老版本的jdk中，只能有抽象方法，但是Java8版本的接口中，接口可以帶有默認(rèn)方法。

4. 屬性上，抽象類可以用各種各樣的修飾符修飾。而接口的屬性是默認(rèn)的public static final

5. 抽象類中可以含有靜態(tài)代碼塊和靜態(tài)方法，而接口不能含有靜態(tài)方法和靜態(tài)代碼塊。

6. 抽象類可以含有構(gòu)造方法，接口不能含有構(gòu)造方法。

7. 既然說到Java 8 那么就來說明，Java8中的接口中的默認(rèn)方法是可以被多重繼承的。而抽象類不行。

8. 另外，接口只能繼承接口。而抽象類可以繼承普通的類，也能繼承接口和抽象類。

?

9.???? 動(dòng)態(tài)代理的兩種方式，以及區(qū)別。

jdk動(dòng)態(tài)代理和cglib動(dòng)態(tài)代理。兩種方法同時(shí)存在，各有優(yōu)劣。

jdk動(dòng)態(tài)代理是由java內(nèi)部的反射機(jī)制來實(shí)現(xiàn)的，cglib動(dòng)態(tài)代理底層則是借助asm來實(shí)現(xiàn)的。

總的來說，反射機(jī)制在生成類的過程中比較高效，而asm在生成類之后的相關(guān)執(zhí)行過程中比較高效（可以通過將asm生成的類進(jìn)行緩存，這樣解決asm生成類過程低效問題）。還有一點(diǎn)必須注意：jdk動(dòng)態(tài)代理的應(yīng)用前提，必須是目標(biāo)類基于統(tǒng)一的接口。如果沒有上述前提，jdk動(dòng)態(tài)代理不能應(yīng)用。由此可以看出，jdk動(dòng)態(tài)代理有一定的局限性，cglib這種第三方類庫實(shí)現(xiàn)的動(dòng)態(tài)代理應(yīng)用更加廣泛，且在效率上更有優(yōu)勢。。

?

10.?? Java序列化的方式。

a.是相應(yīng)的對(duì)象實(shí)現(xiàn)了序列化接口Serializable，這個(gè)使用的比較多，對(duì)于序列化接口Serializable接口是一個(gè)空的接口，它的主要作用就是標(biāo)識(shí)這個(gè)對(duì)象時(shí)可序列化的，jre對(duì)象在傳輸對(duì)象的時(shí)候會(huì)進(jìn)行相關(guān)的封裝

b.實(shí)現(xiàn)序列化的第二種方式為實(shí)現(xiàn)接口Externalizable

?

11.?? 傳值和傳引用的區(qū)別，Java是怎么樣的，有沒有傳值引用。

1. 在java中所有的參數(shù)都是傳值的，引用符號(hào)&的傳遞是C++中才有的；

2. 在java傳參中，基本類型(byte--short--int--long--float--double--boolean--char)的變量總是按值傳遞；

3. 對(duì)于對(duì)象來說，不是將對(duì)象本身傳遞給方法，而是將對(duì)象的的引用或者說對(duì)象的首地址傳遞給方法，引用本身是按值傳遞的；

4. 對(duì)于String、Integer、Long，數(shù)組等，這些都相當(dāng)于對(duì)象，因此傳參時(shí)相當(dāng)于是傳引用；

?

12.?? 一個(gè)ArrayList在循環(huán)過程中刪除，會(huì)不會(huì)出問題，為什么。

for(int i),這種遍歷的時(shí)候刪除,被刪除元素的后面那個(gè)元素會(huì)被跳過,除非在循環(huán)里面操作i,你想想是不是,因?yàn)楫?dāng)前對(duì)象被remove了,下一個(gè)對(duì)象的序號(hào)就減一了,但是并沒有對(duì)下一個(gè)對(duì)象做判斷,i照常加1,就跳過了下一個(gè)對(duì)象

轉(zhuǎn)載于:https://www.cnblogs.com/yfz1552800131/p/9430503.html

總結(jié)

以上是生活随笔為你收集整理的JAVA面试整理之——JAVA基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。