大家好，我是小林。

今天分享一位同學快手Java后端面經，問的問題基礎比較多，可惜同學沒怎么準備好，回答的不是很多，面完就秒掛了。

圖片

考察的知識，我給大家羅列一下：

• 操作系統：進程線程、上下文、中斷
• Java：JVM、HashMap、synchronized、線程池
• 數據結構：數組和鏈表
• 算法：合并k個有序鏈表

技術八股

進程和線程區別是什么？

圖片

• 本質區別：進程是操作系統資源分配的基本單位，而線程是任務調度和執行的基本單位
• 在開銷方面：每個進程都有獨立的代碼和數據空間（程序上下文），程序之間的切換會有較大的開銷；線程可以看做輕量級的進程，同一類線程共享代碼和數據空間，每個線程都有自己獨立的運行棧和程序計數器（PC），線程之間切換的開銷小
• 穩定性方面：進程中某個線程如果崩潰了，可能會導致整個進程都崩潰。而進程中的子進程崩潰，并不會影響其他進程。
• 內存分配方面：系統在運行的時候會為每個進程分配不同的內存空間；而對線程而言，除了CPU外，系統不會為線程分配內存（線程所使用的資源來自其所屬進程的資源），線程組之間只能共享資源
• 包含關系：沒有線程的進程可以看做是單線程的，如果一個進程內有多個線程，則執行過程不是一條線的，而是多條線（線程）共同完成的；線程是進程的一部分，所以線程也被稱為輕權進程或者輕量級進程

什么是上下文？

任務是交給 CPU 運行的，那么在每個任務運行前，CPU 需要知道任務從哪里加載，又從哪里開始運行所以，操作系統需要事先幫 CPU 設置好 CPU 寄存器和程序計數器。

CPU 寄存器和程序計數是 CPU 在運行任何任務前，所必須依賴的環境，這些環境就叫做 CPU 上下文。

CPU 上下文切換就是先把前一個任務的 CPU 上下文（CPU 寄存器和程序計數器）保存起來，然后加載新任務的上下文到這些寄存器和程序計數器，最后再跳轉到程序計數器所指的新位置，運行新任務。

系統內核會存儲保持下來的上下文信息，當此任務再次被分配給 CPU 運行時，CPU 會重新加載這些上下文，這樣就能保證任務原來的狀態不受影響，讓任務看起來還是連續運行。

上面說到所謂的「任務」，主要包含進程、線程和中斷。所以，可以根據任務的不同，把 CPU 上下文切換分成：進程上下文切換、線程上下文切換

進程是由內核管理和調度的，所以進程的切換只能發生在內核態。所以，進程的上下文切換不僅包含了虛擬內存、棧、全局變量等用戶空間的資源，還包括了內核堆棧、寄存器等內核空間的資源。

通常，會把交換的信息保存在進程的 PCB，當要運行另外一個進程的時候，我們需要從這個進程的 PCB 取出上下文，然后恢復到 CPU 中，這使得這個進程可以繼續執行，如下圖所示：

圖片

線程共享進程的虛擬內存資源，但是線程也有自己的私有數據，比如棧和寄存器等，這些在上下文切換時也是需要保存的。

線程上下文切換時，虛擬內存這些資源就保持不動，只需要切換線程的私有數據、寄存器等不共享的數據。

什么是中斷？

CPU停下當前的工作任務，去處理其他事情，處理完后回來繼續執行剛才的任務，這一過程便是中斷。

中斷分為外部中斷和內部中斷：

• 外部中斷分為可屏蔽中斷和不可屏蔽中斷：

• 可屏蔽中斷：通過INTR線向CPU請求的中斷，主要來自外部設備如硬盤，打印機，網卡等。此類中斷并不會影響系統運行，可隨時處理，甚至不處理，所以名為可屏蔽。
• 不可屏蔽中斷：通過NMI線向CPU請求的中斷，如電源掉電，硬件線路故障等。這里不可屏蔽的意思不是不可以屏蔽，不建議屏蔽，而是問題太大，屏蔽不了，不能屏蔽的意思。注：INTR和NMI都是CPU的引腳

• 內部中斷分為陷阱、故障、終止：

• 陷阱：是一種有意的，預先安排的異常事件，一般是在編寫程序時故意設下的陷阱指令，而后執行到陷阱指令后，CPU將會調用特定程序進行相應的處理，處理結束后返回到陷阱指令的下一條指令。如系統調用，程序調試功能等。如printf函數，最底層的實現中會有一條int 0x80指令，這就是一條陷阱指令，使用0x80號中斷進行系統調用。

• 故障：故障是在引起故障的指令被執行，但還沒有執行結束時，CPU檢測到的一類的意外事件。出錯時交由故障處理程序處理，如果能處理修正這個錯誤，就將控制返回到引起故障的指令即CPU重新執這條指令。如果不能處理就報錯。常見的故障為缺頁，當CPU引用的虛擬地址對應的物理頁不存在時就會發生故障。缺頁異常是能夠修正的，有著專門的缺頁處理程序，它會將缺失的物理頁從磁盤中重新調進主存。而后再次執行引起故障的指令時便能夠順利執行了。

• 終止：執行指令的過程中發生了致命錯誤，不可修復，程序無法繼續運行，只能終止，通常會是一些硬件的錯誤。終止處理程序不會將控制返回給原程序，而是直接終止原程序

數組和鏈表區別是什么？

• 訪問效率：數組可以通過索引直接訪問任何位置的元素，訪問效率高，時間復雜度為O(1)，而鏈表需要從頭節點開始遍歷到目標位置，訪問效率較低，時間復雜度為O(n)。
• 插入和刪除操作效率：數組插入和刪除操作可能需要移動其他元素，時間復雜度為O(n)，而鏈表只需要修改指針指向，時間復雜度為O(1)。
• 緩存命中率：由于數組元素在內存中連續存儲，可以提高CPU緩存的命中率，而鏈表節點不連續存儲，可能導致CPU緩存的命中率較低，頻繁的緩存失效會影響性能。
• 應用場景：數組適合靜態大小、頻繁訪問元素的場景，而鏈表適合動態大小、頻繁插入、刪除操作的場景

為什么數組查詢的復雜度為O(1)？

數組必須要內存中一塊連續的空間，并且數組中必須存放相同的數據類型。 比如我們創建一個長度為 10，數據類型為整型的數組，在內存中的地址是從 1000 開始，那么它在內存中的存儲格式如下。

圖片

由于每個整型數據占據 4 個字節的內存空間，因此整個數組的內存空間地址是 1000～1039，根據這個，我們就可以輕易算出數組中每個數據的內存下標地址。 利用這個特性，我們只要知道了數組下標，也就是數據在數組中的位置，比如下標 2，就可以計算得到這個數據在內存中的位置 1008，從而對這個位置的數據 241 進行快速讀寫訪問，時間復雜度為 O(1)。

JVM是什么？

JVM是 java 虛擬機，主要工作是解釋自己的指令集（即字節碼）并映射到本地的CPU指令集和OS的系統調用。

JVM屏蔽了與操作系統平臺相關的信息，使得Java程序只需要生成在Java虛擬機上運行的目標代碼（字節碼），就可在多種平臺上不加修改的運行，這也是Java能夠“一次編譯，到處運行的”原因。

Java為什么是跨平臺的？

Java 能支持跨平臺，主要依賴于 JVM 關系比較大。

JVM也是一個軟件，不同的平臺有不同的版本。我們編寫的Java源碼，編譯后會生成一種 .class 文件，稱為字節碼文件。Java虛擬機就是負責將字節碼文件翻譯成特定平臺下的機器碼然后運行。也就是說，只要在不同平臺上安裝對應的JVM，就可以運行字節碼文件，運行我們編寫的Java程序。

而這個過程中，我們編寫的Java程序沒有做任何改變，僅僅是通過JVM這一”中間層“，就能在不同平臺上運行，真正實現了”一次編譯，到處運行“的目的。

JVM是一個”橋梁“，是一個”中間件“，是實現跨平臺的關鍵，Java代碼首先被編譯成字節碼文件，再由JVM將字節碼文件翻譯成機器語言，從而達到運行Java程序的目的。

編譯的結果不是生成機器碼，而是生成字節碼，字節碼不能直接運行，必須通過JVM翻譯成機器碼才能運行。不同平臺下編譯生成的字節碼是一樣的，但是由JVM翻譯成的機器碼卻不一樣。

所以，運行Java程序必須有JVM的支持，因為編譯的結果不是機器碼，必須要經過JVM的再次翻譯才能執行。即使你將Java程序打包成可執行文件（例如 .exe），仍然需要JVM的支持。

跨平臺的是Java程序，不是JVM。JVM是用C/C++開發的，是編譯后的機器碼，不能跨平臺，不同平臺下需要安裝不同版本的JVM。

圖片

Java為什么既是編譯型也是解釋型的？

首先在Java經過編譯之后生成字節碼文件，接下來進入JVM中，就有兩個步驟編譯和解釋。 如下圖：

圖片

編譯性：

• Java源代碼首先被編譯成字節碼，JIT 會把編譯過的機器碼保存起來,以備下次使用。

解釋性：

• JVM中一個方法調用計數器，當累計計數大于一定值的時候，就使用JIT進行編譯生成機器碼文件。否則就是用解釋器進行解釋執行，然后字節碼也是經過解釋器進行解釋運行的。

所以Java既是編譯型也是解釋性語言，默認采用的是解釋器和編譯器混合的模式。

Python和Java區別是什么？

• Java是一種已編譯的編程語言，Java編譯器將源代碼編譯為字節碼，而字節碼則由Java虛擬機執行
• python是一種解釋語言，翻譯時會在執行程序的同時進行翻譯。

了解HashMap嗎？

• 在 JDK 1.7 版本之前， HashMap 數據結構是數組和鏈表，HashMap通過哈希算法將元素的鍵（Key）映射到數組中的槽位（Bucket）。如果多個鍵映射到同一個槽位，它們會以鏈表的形式存儲在同一個槽位上，因為鏈表的查詢時間是O(n)，所以沖突很嚴重，一個索引上的鏈表非常長，效率就很低了。
• 所以在 JDK 1.8 版本的時候做了優化，當一個鏈表的長度超過8的時候就轉換數據結構，不再使用鏈表存儲，而是使用紅黑樹，查找時使用紅黑樹，時間復雜度O（log n），可以提高查詢性能，但是在數量較少時，即數量小于6時，會將紅黑樹轉換回鏈表。

圖片

HashMap插入元素過程？

圖片

HashMap HashMap的put()方法用于向HashMap中添加鍵值對。當調用HashMap的put()方法時，會按照以下詳細流程執行：

第一步：根據要添加的鍵的哈希碼計算在數組中的位置（索引）。

第二步：檢查該位置是否為空（即沒有鍵值對存在）

• 如果為空，則直接在該位置創建一個新的Entry對象來存儲鍵值對。將要添加的鍵值對作為該Entry的鍵和值，并保存在數組的對應位置。將HashMap的修改次數（modCount）加1，以便在進行迭代時發現并發修改。

第三步：如果該位置已經存在其他鍵值對，檢查該位置的第一個鍵值對的哈希碼和鍵是否與要添加的鍵值對相同？

• 如果相同，則表示找到了相同的鍵，直接將新的值替換舊的值，完成更新操作。

第四步：如果第一個鍵值對的哈希碼和鍵不相同，則需要遍歷鏈表或紅黑樹來查找是否有相同的鍵：

如果鍵值對集合是鏈表結構：

• 從鏈表的頭部開始逐個比較鍵的哈希碼和equals()方法，直到找到相同的鍵或達到鏈表末尾。
• 如果找到了相同的鍵，則使用新的值取代舊的值，即更新鍵對應的值。
• 如果沒有找到相同的鍵，則將新的鍵值對添加到鏈表的頭部。

如果鍵值對集合是紅黑樹結構：

• 在紅黑樹中使用哈希碼和equals()方法進行查找。根據鍵的哈希碼，定位到紅黑樹中的某個節點，然后逐個比較鍵，直到找到相同的鍵或達到紅黑樹末尾。
• 如果找到了相同的鍵，則使用新的值取代舊的值，即更新鍵對應的值。
• 如果沒有找到相同的鍵，則將新的鍵值對添加到紅黑樹中。

第五步：檢查鏈表長度是否達到閾值（默認為8）：

• 如果鏈表長度超過閾值，且HashMap的數組長度大于等于64，則會將鏈表轉換為紅黑樹，以提高查詢效率。

第六步：檢查負載因子是否超過閾值（默認為0.75）：

• 如果鍵值對的數量（size）與數組的長度的比值大于閾值，則需要進行擴容操作。

第七步：擴容操作：

• 創建一個新的兩倍大小的數組。
• 將舊數組中的鍵值對重新計算哈希碼并分配到新數組中的位置。
• 更新HashMap的數組引用和閾值參數。

第八步：完成添加操作。

需要注意的是，HashMap中的鍵和值都可以為null。此外，HashMap是非線程安全的，如果在多線程環境下使用，需要采取額外的同步措施或使用線程安全的ConcurrentHashMap。

重寫HashMap的equal和hashcode方法需要注意什么？

HashMap使用Key對象的hashCode()和equals()方法去決定key-value對的索引。當我們試著從HashMap中獲取值的時候，這些方法也會被用到。如果這些方法沒有被正確地實現，在這種情況下，兩個不同Key也許會產生相同的hashCode()和equals()輸出，HashMap將會認為它們是相同的，然后覆蓋它們，而非把它們存儲到不同的地方。

同樣的，所有不允許存儲重復數據的集合類都使用hashCode()和equals()去查找重復，所以正確實現它們非常重要。equals()和hashCode()的實現應該遵循以下規則：

• 如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()總是為true的。
• 如果o1.hashCode() == o2.hashCode()，并不意味著o1.equals(o2)會為true。

重寫HashMap的equal方法不當會出現什么問題？

HashMap在比較元素時，會先通過hashCode進行比較，相同的情況下再通過equals進行比較。

所以 equals相等的兩個對象，hashCode一定相等。hashCode相等的兩個對象，equals不一定相等（比如散列沖突的情況）

重寫了equals方法，不重寫hashCode方法時，可能會出現equals方法返回為true，而hashCode方法卻返回false，這樣的一個后果會導致在hashmap等類中存儲多個一模一樣的對象，導致出現覆蓋存儲的數據的問題，這與hashmap只能有唯一的key的規范不符合，

列舉HashMap在多線程下可能會出現的問題？

• JDK1.7中的 HashMap 使用頭插法插入元素，在多線程的環境下，擴容的時候有可能導致環形鏈表的出現，形成死循環。因此，JDK1.8使用尾插法插入元素，在擴容時會保持鏈表元素原本的順序，不會出現環形鏈表的問題。
• 多線程同時執行 put 操作，如果計算出來的索引位置是相同的，那會造成前一個 key 被后一個 key 覆蓋，從而導致元素的丟失。此問題在JDK 1.7和 JDK 1.8 中都存在。

synchronized關鍵字的底層原理是什么？

synchronized是java提供的原子性內置鎖，這種內置的并且使用者看不到的鎖也被稱為監視器鎖，使用synchronized之后，會在編譯之后在同步的代碼塊前后加上monitorenter和monitorexit字節碼指令，他依賴操作系統底層互斥鎖實現。他的作用主要就是實現原子性操作和解決共享變量的內存可見性問題。

執行monitorenter指令時會嘗試獲取對象鎖，如果對象沒有被鎖定或者已經獲得了鎖，鎖的計數器+1。此時其他競爭鎖的線程則會進入等待隊列中。

執行monitorexit指令時則會把計數器-1，當計數器值為0時，則鎖釋放，處于等待隊列中的線程再繼續競爭鎖。

synchronized是排它鎖，當一個線程獲得鎖之后，其他線程必須等待該線程釋放鎖后才能獲得鎖，而且由于Java中的線程和操作系統原生線程是一一對應的，線程被阻塞或者喚醒時時會從用戶態切換到內核態，這種轉換非常消耗性能。

從內存語義來說，加鎖的過程會清除工作內存中的共享變量，再從主內存讀取，而釋放鎖的過程則是將工作內存中的共享變量寫回主內存。

實際上大部分時候我認為說到monitorenter就行了，但是為了更清楚的描述，還是再具體一點。

如果再深入到源碼來說，synchronized實際上有兩個隊列waitSet和entryList。

1. 當多個線程進入同步代碼塊時，首先進入entryList
2. 有一個線程獲取到monitor鎖后，就賦值給當前線程，并且計數器+1
3. 如果線程調用wait方法，將釋放鎖，當前線程置為null，計數器-1，同時進入waitSet等待被喚醒，調用notify或者notifyAll之后又會進入entryList競爭鎖
4. 如果線程執行完畢，同樣釋放鎖，計數器-1，當前線程置為null

圖片

線程池了解嗎？有哪些常見參數？

線程池是為了減少頻繁的創建線程和銷毀線程帶來的性能損耗。線程池的構造函數有7個參數：

圖片

• corePoolSize：線程池核心線程數量。默認情況下，線程池中線程的數量如果 <= corePoolSize，那么即使這些線程處于空閑狀態，那也不會被銷毀。
• maximumPoolSize：線程池中最多可容納的線程數量。當一個新任務交給線程池，如果此時線程池中有空閑的線程，就會直接執行，如果沒有空閑的線程且當前線程池的線程數量小于corePoolSize，就會創建新的線程來執行任務，否則就會將該任務加入到阻塞隊列中，如果阻塞隊列滿了，就會創建一個新線程，從阻塞隊列頭部取出一個任務來執行，并將新任務加入到阻塞隊列末尾。如果當前線程池中線程的數量等于maximumPoolSize，就不會創建新線程，就會去執行拒絕策略。
• keepAliveTime：當線程池中線程的數量大于corePoolSize，并且某個線程的空閑時間超過了keepAliveTime，那么這個線程就會被銷毀。
• unit：就是keepAliveTime時間的單位。
• workQueue：工作隊列。當沒有空閑的線程執行新任務時，該任務就會被放入工作隊列中，等待執行。
• threadFactory：線程工廠。可以用來給線程取名字等等
• handler：拒絕策略。當一個新任務交給線程池，如果此時線程池中有空閑的線程，就會直接執行，如果沒有空閑的線程，就會將該任務加入到阻塞隊列中，如果阻塞隊列滿了，就會創建一個新線程，從阻塞隊列頭部取出一個任務來執行，并將新任務加入到阻塞隊列末尾。如果當前線程池中線程的數量等于maximumPoolSize，就不會創建新線程，就會去執行拒絕策略。

線程池工作隊列滿了有哪些拒接策略？

當線程池的任務隊列滿了之后，線程池會執行指定的拒絕策略來應對，常用的四種拒絕策略包括：CallerRunsPolicy、AbortPolicy、DiscardPolicy、DiscardOldestPolicy，此外，還可以通過實現RejectedExecutionHandler接口來自定義拒絕策略。

四種預置的拒絕策略：

• CallerRunsPolicy，使用線程池的調用者所在的線程去執行被拒絕的任務，除非線程池被停止或者線程池的任務隊列已有空缺。
• AbortPolicy，直接拋出一個任務被線程池拒絕的異常。
• DiscardPolicy，不做任何處理，靜默拒絕提交的任務。
• DiscardOldestPolicy，拋棄最老的任務，然后執行該任務。
• 自定義拒絕策略，通過實現接口可以自定義任務拒絕策略。

有線程池參數設置的經驗嗎？

• CPU密集型：corePoolSize = CPU核數 + 1
• IO密集型：corePoolSize = CPU核數 * 2

手撕算法

• 合并k個有序鏈表（面試官說給我出個簡單題）