終究還是沒扛過，快手 1 小時的拷打...

作者：小林coding 2024-09-02 14:13:15

開發(fā) 前端

算法題目是反轉(zhuǎn)鏈表，只給了main函數(shù)要手動寫輸入輸出，用到了list但這個IDE不讓我加頭文件，寫完以后一直報錯導(dǎo)致運行不起來，最后講了一下思路。

大家好，我是小林。

快手在投遞簡歷的過程中，即使你有個部門面掛了，但是你還有機會投其他部門的，而且不限次數(shù)，也被很多人說「快手有無線復(fù)活的 buff」。

之前就有讀者跟我說，他投快手失敗了 8 次，第 9 才上岸快手成功，換誰能堅持做到？實在太不容易了，能堅持到這個程度，已經(jīng)超越很多人了，大部分人失敗 3 次，就不敢繼續(xù)投了。

圖片

這次，就來分享一位同學(xué)的快手的 Java 后端面經(jīng)，八股拷打了半個多小時，做算法題花了十幾分鐘，累計時長有 1 個小時。

算法題出了經(jīng)典的反轉(zhuǎn)鏈表，但是 acm 模式，頭文件啥的都需要自己導(dǎo)入，包括輸入輸出也需要自己構(gòu)造，調(diào)試半天沒編譯通過，實在難繃。。。

八股主要考慮計算機網(wǎng)絡(luò)、Java、MySQL、Redis 這些內(nèi)容，整體上難度不算難，可惜同學(xué)準(zhǔn)備的不夠充分，面完最終還是掛了，但是就像我前面說的，掛了沒什么所謂，重在補充自己不足的地方，下次再戰(zhàn)！

圖片

計算機網(wǎng)絡(luò)

加密方式有哪些？

對稱加密：也稱為共享密鑰加密，使用相同的密鑰進(jìn)行加密和解密。常見的對稱加密算法包括AES（高級加密標(biāo)準(zhǔn)）、DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）等。
非對稱加密：也稱為公鑰加密，使用公鑰進(jìn)行加密，私鑰進(jìn)行解密。常見的非對稱加密算法包括RSA、ECC等。
混合加密：結(jié)合了對稱加密和非對稱加密的優(yōu)點，先使用對稱加密對數(shù)據(jù)進(jìn)行加密，再使用公鑰對密鑰進(jìn)行非對稱加密。這種方式的優(yōu)點是既保證了數(shù)據(jù)的安全性，又提高了加密和解密的速度。
哈希算法：通過哈希函數(shù)將任意長度的數(shù)據(jù)轉(zhuǎn)化為固定長度的哈希值，但無法逆向還原為原始數(shù)據(jù)。哈希算法包括MD5、SHA（安全哈希算法）等，通常用于存儲密碼和產(chǎn)生信息指紋等。

Java

知道哪些java集合？

圖片

List是有序的Collection，使用此接口能夠精確的控制每個元素的插入位置，用戶能根據(jù)索引訪問List中元素。常用的實現(xiàn)List的類有LinkedList，ArrayList，Vector，Stack。

ArrayList是容量可變的非線程安全列表，其底層使用數(shù)組實現(xiàn)。當(dāng)幾何擴(kuò)容時，會創(chuàng)建更大的數(shù)組，并把原數(shù)組復(fù)制到新數(shù)組。ArrayList支持對元素的快速隨機訪問，但插入與刪除速度很慢。
LinkedList本質(zhì)是一個雙向鏈表，與ArrayList相比，，其插入和刪除速度更快，但隨機訪問速度更慢。

Set不允許存在重復(fù)的元素，與List不同，set中的元素是無序的。常用的實現(xiàn)有HashSet，LinkedHashSet和TreeSet。

HashSet通過HashMap實現(xiàn)，HashMap的Key即HashSet存儲的元素，所有Key都是用相同的Value，一個名為PRESENT的Object類型常量。使用Key保證元素唯一性，但不保證有序性。由于HashSet是HashMap實現(xiàn)的，因此線程不安全。
LinkedHashSet繼承自HashSet，通過LinkedHashMap實現(xiàn)，使用雙向鏈表維護(hù)元素插入順序。
TreeSet通過TreeMap實現(xiàn)的，添加元素到集合時按照比較規(guī)則將其插入合適的位置，保證插入后的集合仍然有序。

Map 是一個鍵值對集合，存儲鍵、值和之間的映射。Key 無序，唯一；value 不要求有序，允許重復(fù)。Map 沒有繼承于 Collection 接口，從 Map 集合中檢索元素時，只要給出鍵對象，就會返回對應(yīng)的值對象。主要實現(xiàn)有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap

HashMap：JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突），JDK1.8 以后在解決哈希沖突時有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為 8）時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間
LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序。同時通過對鏈表進(jìn)行相應(yīng)的操作，實現(xiàn)了訪問順序相關(guān)邏輯。
HashTable：數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的
TreeMap：紅黑樹（自平衡的排序二叉樹）
ConcurrentHashMap：Node數(shù)組+鏈表+紅黑樹實現(xiàn)，線程安全的（jdk1.8以前Segment鎖，1.8以后volatile + CAS 或者 synchronized）

hashmap是線程安全的嗎？

hashmap不是線程安全的，hashmap在多線程會存在下面的問題：

JDK 1.7 HashMap 采用數(shù)組 + 鏈表的數(shù)據(jù)結(jié)構(gòu)，多線程背景下，在數(shù)組擴(kuò)容的時候，存在 Entry 鏈死循環(huán)和數(shù)據(jù)丟失問題。
JDK 1.8 HashMap 采用數(shù)組 + 鏈表 + 紅黑二叉樹的數(shù)據(jù)結(jié)構(gòu)，優(yōu)化了 1.7 中數(shù)組擴(kuò)容的方案，解決了 Entry 鏈死循環(huán)和數(shù)據(jù)丟失問題。但是多線程背景下，put 方法存在數(shù)據(jù)覆蓋的問題。

如果要保證線程安全，可以通過這些方法來保證：

多線程環(huán)境可以使用Collections.synchronizedMap同步加鎖的方式，還可以使用HashTable，但是同步的方式顯然性能不達(dá)標(biāo)，而ConurrentHashMap更適合高并發(fā)場景使用。
ConcurrentHashmap在JDK1.7和1.8的版本改動比較大，1.7使用Segment+HashEntry分段鎖的方式實現(xiàn)，1.8則拋棄了Segment，改為使用CAS+synchronized+Node實現(xiàn)，同樣也加入了紅黑樹，避免鏈表過長導(dǎo)致性能的問題。

為什么hashmap擴(kuò)容的時候不安全？

擴(kuò)容造成死循環(huán)分析過程

這里假設(shè)

hash 算法為簡單的用 key mod 鏈表的大小。
最開始 hash 表 size=2，key=3,7,5，則都在 table[1] 中。
然后進(jìn)行 resize，使 size 變成 4。

未 resize 前的數(shù)據(jù)結(jié)構(gòu)如下：

圖片

如果在單線程環(huán)境下，最后的結(jié)果如下：

圖片

這里的轉(zhuǎn)移過程，不再進(jìn)行詳述，只要理解 transfer 函數(shù)在做什么，其轉(zhuǎn)移過程以及如何對鏈表進(jìn)行反轉(zhuǎn)應(yīng)該不難。

然后在多線程環(huán)境下，假設(shè)有兩個線程 A 和 B 都在進(jìn)行 put 操作。線程 A 在執(zhí)行到 transfer 函數(shù)中第 11 行代碼處掛起，因為該函數(shù)在這里分析的地位非常重要，因此再次貼出來。

圖片

此時線程 A 中運行結(jié)果如下：

圖片

線程 A 掛起后，此時線程 B 正常執(zhí)行，并完成 resize 操作，結(jié)果如下：

圖片

這里需要特別注意的點：由于線程 B 已經(jīng)執(zhí)行完畢，根據(jù) Java 內(nèi)存模型，現(xiàn)在 newTable 和 table 中的 Entry 都是主存中最新值：7.next=3，3.next=null。

此時切換到線程 A 上，在線程 A 掛起時內(nèi)存中值如下：e=3，next=7，newTable[3]=null，代碼執(zhí)行過程如下：

newTable[3]=e ----> newTable[3]=3
e=next ----> e=7

此時結(jié)果如下：

圖片

繼續(xù)循環(huán)：

e=7
next=e.next ----> next=3【從主存中取值】
e.next=newTable[3] ----> e.next=3【從主存中取值】
newTable[3]=e ----> newTable[3]=7
e=next ----> e=3

結(jié)果如下：

圖片

再次進(jìn)行循環(huán)：

e=3
next=e.next ----> next=null
e.next=newTable[3] ----> e.next=7 即：3.next=7
newTable[3]=e ----> newTable[3]=3
e=next ----> e=null

注意此次循環(huán)：e.next=7，而在上次循環(huán)中 7.next=3，出現(xiàn)環(huán)形鏈表，并且此時 e=null 循環(huán)結(jié)束。結(jié)果如下：

圖片

在后續(xù)操作中只要涉及輪詢 hashmap 的數(shù)據(jù)結(jié)構(gòu)，就會在這里發(fā)生死循環(huán)，造成悲劇。

擴(kuò)容造成數(shù)據(jù)丟失分析過程

遵照上述分析過程，初始時：

圖片

線程 A 和線程 B 進(jìn)行 put 操作，同樣線程 A 掛起：

圖片

此時線程 A 的運行結(jié)果如下：

圖片

此時線程 B 已獲得 CPU 時間片，并完成 resize 操作：

圖片

同樣注意由于線程 B 執(zhí)行完成，newTable 和 table 都為最新值：5.next=null。

此時切換到線程 A，在線程 A 掛起時：e=7，next=5，newTable[3]=null。

執(zhí)行 newtable[i]=e，就將 7 放在了 table[3] 的位置，此時 next=5。接著進(jìn)行下一次循環(huán)：

e=5
next=e.next ----> next=null，從主存中取值
e.next=newTable[1] ----> e.next=5，從主存中取值
newTable[1]=e ----> newTable[1]=5
e=next ----> e=null

將 5 放置在 table[1] 位置，此時 e=null 循環(huán)結(jié)束，3 元素丟失，并形成環(huán)形鏈表。并在后續(xù)操作 hashmap 時造成死循環(huán)。

圖片

JVM內(nèi)存有哪些結(jié)構(gòu)？

根據(jù) JVM8 規(guī)范，JVM 運行時內(nèi)存共分為虛擬機棧、堆、元空間、程序計數(shù)器、本地方法棧五個部分。還有一部分內(nèi)存叫直接內(nèi)存，屬于操作系統(tǒng)的本地內(nèi)存，也是可以直接操作的。

圖片

JVM的內(nèi)存結(jié)構(gòu)主要分為以下幾個部分：

元空間：元空間的本質(zhì)和永久代類似，都是對JVM規(guī)范中方法區(qū)的實現(xiàn)。不過元空間與永久代之間最大的區(qū)別在于：元空間并不在虛擬機中，而是使用本地內(nèi)存。
Java 虛擬機棧：每個線程有一個私有的棧，隨著線程的創(chuàng)建而創(chuàng)建。棧里面存著的是一種叫“棧幀”的東西，每個方法會創(chuàng)建一個棧幀，棧幀中存放了局部變量表（基本數(shù)據(jù)類型和對象引用）、操作數(shù)棧、方法出口等信息。棧的大小可以固定也可以動態(tài)擴(kuò)展。
本地方法棧：與虛擬機棧類似，區(qū)別是虛擬機棧執(zhí)行java方法，本地方法站執(zhí)行native方法。在虛擬機規(guī)范中對本地方法棧中方法使用的語言、使用方法與數(shù)據(jù)結(jié)構(gòu)沒有強制規(guī)定，因此虛擬機可以自由實現(xiàn)它。
程序計數(shù)器：程序計數(shù)器可以看成是當(dāng)前線程所執(zhí)行的字節(jié)碼的行號指示器。在任何一個確定的時刻，一個處理器（對于多內(nèi)核來說是一個內(nèi)核）都只會執(zhí)行一條線程中的指令。因此，為了線程切換后能恢復(fù)到正確的執(zhí)行位置，每條線程都需要一個獨立的程序計數(shù)器，我們稱這類內(nèi)存區(qū)域為“線程私有”內(nèi)存。
堆內(nèi)存：堆內(nèi)存是 JVM 所有線程共享的部分，在虛擬機啟動的時候就已經(jīng)創(chuàng)建。所有的對象和數(shù)組都在堆上進(jìn)行分配。這部分空間可通過 GC 進(jìn)行回收。當(dāng)申請不到空間時會拋出 OutOfMemoryError。堆是JVM內(nèi)存占用最大，管理最復(fù)雜的一個區(qū)域。其唯一的用途就是存放對象實例：所有的對象實例及數(shù)組都在對上進(jìn)行分配。jdk1.8后，字符串常量池從永久代中剝離出來，存放在隊中。
直接內(nèi)存：直接內(nèi)存并不是虛擬機運行時數(shù)據(jù)區(qū)的一部分，也不是Java 虛擬機規(guī)范中農(nóng)定義的內(nèi)存區(qū)域。在JDK1.4 中新加入了NIO(New Input/Output)類，引入了一種基于通道(Channel)與緩沖區(qū)（Buffer）的I/O 方式，它可以使用native 函數(shù)庫直接分配堆外內(nèi)存，然后通脫一個存儲在Java堆中的DirectByteBuffer 對象作為這塊內(nèi)存的引用進(jìn)行操作。這樣能在一些場景中顯著提高性能，因為避免了在Java堆和Native堆中來回復(fù)制數(shù)據(jù)。

對象存在堆里，什么時候?qū)ο蟛辉诙牙铮?/h3>
Java對象并不一定都是分配在堆內(nèi)存上，如果JVM確定一個對象不會逃逸，它可以選擇將這個對象分配在線程的棧上而不是堆上。棧是線程私有的內(nèi)存區(qū)域，當(dāng)方法執(zhí)行結(jié)束時，棧上的數(shù)據(jù)會被自動銷毀。
棧上分配依賴于逃逸分析和標(biāo)量替換。
標(biāo)量替換：就是將對象拆解為其成員變量。例如，如果一個對象包含整數(shù)、浮點數(shù)和其他基本數(shù)據(jù)類型的字段，那么這些字段將被單獨分配到棧上。解決不會因為沒有一大塊連續(xù)空間導(dǎo)致對象內(nèi)存不夠分配的問題。
標(biāo)量：標(biāo)量即不可被進(jìn)一步分解的量，JAVA的基本數(shù)據(jù)類型就是標(biāo)量（如：int，long等基本數(shù)據(jù)類型以及reference類型等）。
聚合量：聚合量就是可以被進(jìn)一步分解的量，通常是對象，JAVA中對象就是可以被進(jìn)一步分解的聚合量，對象包含多個成員變量。
相關(guān)的JVM參數(shù)：
逃逸分析：-XX:+DoEscapeAnalysis（JDK7以后默認(rèn)開啟）
標(biāo)量替換：-XX:+EliminateAllocations（JDK7以后默認(rèn)開啟）
通過逃逸分析和棧上分配，JVM可以減少垃圾回收的頻率和開銷。這有助于提高應(yīng)用程序的性能，特別是在存在大量臨時對象的情況下，因為這些對象可以更快地釋放，而不會給垃圾回收器帶來過大的壓力。

java類加載過程介紹一下？

類從被加載到虛擬機內(nèi)存開始，到卸載出內(nèi)存為止，它的整個生命周期包括以下 7 個階段：

圖片

加載：通過類的全限定名（包名 + 類名），獲取到該類的.class文件的二進(jìn)制字節(jié)流，將二進(jìn)制字節(jié)流所代表的靜態(tài)存儲結(jié)構(gòu)，轉(zhuǎn)化為方法區(qū)運行時的數(shù)據(jù)結(jié)構(gòu)，在內(nèi)存中生成一個代表該類的java.lang.Class對象，作為方法區(qū)這個類的各種數(shù)據(jù)的訪問入口
連接：驗證、準(zhǔn)備、解析 3 個階段統(tǒng)稱為連接。

驗證：確保class文件中的字節(jié)流包含的信息，符合當(dāng)前虛擬機的要求，保證這個被加載的class類的正確性，不會危害到虛擬機的安全。驗證階段大致會完成以下四個階段的檢驗動作：文件格式校驗、元數(shù)據(jù)驗證、字節(jié)碼驗證、符號引用驗證

準(zhǔn)備：為類中的靜態(tài)字段分配內(nèi)存，并設(shè)置默認(rèn)的初始值，比如int類型初始值是0。被final修飾的static字段不會設(shè)置，因為final在編譯的時候就分配了

解析：解析階段是虛擬機將常量池的「符號引用」直接替換為「直接引用」的過程。符號引用是以一組符號來描述所引用的目標(biāo)，符號可以是任何形式的字面量，只要使用的時候可以無歧義地定位到目標(biāo)即可。直接引用可以是直接指向目標(biāo)的指針、相對偏移量或是一個能間接定位到目標(biāo)的句柄，直接引用是和虛擬機實現(xiàn)的內(nèi)存布局相關(guān)的。如果有了直接引用，那引用的目標(biāo)必定已經(jīng)存在在內(nèi)存中了。

初始化：初始化是整個類加載過程的最后一個階段，初始化階段簡單來說就是執(zhí)行類的構(gòu)造器方法（() ），要注意的是這里的構(gòu)造器方法()并不是開發(fā)者寫的，而是編譯器自動生成的。
使用：使用類或者創(chuàng)建對象
卸載：如果有下面的情況，類就會被卸載：1. 該類所有的實例都已經(jīng)被回收，也就是java堆中不存在該類的任何實例。2. 加載該類的ClassLoader已經(jīng)被回收。3. 類對應(yīng)的java.lang.Class對象沒有任何地方被引用，無法在任何地方通過反射訪問該類的方法。

雙親委派機制是什么？

雙親委派機制是一種任務(wù)委派模式，是 Java 中通過加載工具（**classloader**）加載類文件的一種具體方式。具體表現(xiàn)為

如果一個類加載器收到了類加載請求，它并不會自己先加載，而是把這個請求委托給父類的加載器去執(zhí)行。
如果父類加載器還存在其父類加載器，則進(jìn)一步向上委托，依次遞歸，請求最終將到達(dá)頂層的引導(dǎo)類加載器 BootstrapClassLoader。
如果父類加載器可以完成類加載任務(wù)，就成功返回；倘若父類加載器無法完成加載任務(wù)，子加載器才會嘗試自己去加載。
父類加載器一層一層往下分配任務(wù)，如果子類加載器能加載，則加載此類；如果將加載任務(wù)分配至系統(tǒng)類加載器（AppClassLoader）也無法加載此類，則拋出異常。

java有哪些鎖？

Java中的鎖是用于管理多線程并發(fā)訪問共享資源的關(guān)鍵機制。鎖可以確保在任意給定時間內(nèi)只有一個線程可以訪問特定的資源，從而避免數(shù)據(jù)競爭和不一致性。Java提供了多種鎖機制，可以分為以下幾類：

synchronized：Java中的synchronized關(guān)鍵字是內(nèi)置鎖機制的基礎(chǔ)，可以用于方法或代碼塊。當(dāng)一個線程進(jìn)入synchronized代碼塊或方法時，它會獲取關(guān)聯(lián)對象的鎖；當(dāng)線程離開該代碼塊或方法時，鎖會被釋放。如果其他線程嘗試獲取同一個對象的鎖，它們將被阻塞，直到鎖被釋放。其中，syncronized加鎖時有無鎖、偏向鎖、輕量級鎖和重量級鎖幾個級別。偏向鎖用于當(dāng)一個線程進(jìn)入同步塊時，如果沒有任何其他線程競爭，就會使用偏向鎖，以減少鎖的開銷。輕量級鎖使用線程棧上的數(shù)據(jù)結(jié)構(gòu)，避免了操作系統(tǒng)級別的鎖。重量級鎖則涉及操作系統(tǒng)級的互斥鎖。
ReentrantLock:java.util.concurrent.locks.ReentrantLock是一個顯式的鎖類，提供了比synchronized更高級的功能，如可中斷的鎖等待、定時鎖等待、公平鎖選項等。ReentrantLock使用lock()和unlock()方法來獲取和釋放鎖。其中，公平鎖按照線程請求鎖的順序來分配鎖，保證了鎖分配的公平性，但可能增加鎖的等待時間。非公平鎖不保證鎖分配的順序，可以減少鎖的競爭，提高性能，但可能造成某些線程的饑餓。
讀寫鎖（ReadWriteLock）：java.util.concurrent.locks.ReadWriteLock接口定義了一種鎖，允許多個讀取者同時訪問共享資源，但只允許一個寫入者。讀寫鎖通常用于讀取遠(yuǎn)多于寫入的情況，以提高并發(fā)性。
樂觀鎖和悲觀鎖：悲觀鎖（Pessimistic Locking）通常指在訪問數(shù)據(jù)前就鎖定資源，假設(shè)最壞的情況，即數(shù)據(jù)很可能被其他線程修改。synchronized和ReentrantLock都是悲觀鎖的例子。樂觀鎖（Optimistic Locking）通常不鎖定資源，而是在更新數(shù)據(jù)時檢查數(shù)據(jù)是否已被其他線程修改。樂觀鎖常使用版本號或時間戳來實現(xiàn)。
自旋鎖：自旋鎖是一種鎖機制，線程在等待鎖時會持續(xù)循環(huán)檢查鎖是否可用，而不是放棄CPU并阻塞。通常可以使用CAS來實現(xiàn)。這在鎖等待時間很短的情況下可以提高性能，但過度自旋會浪費CPU資源。

具體講一下synchronized和reentrantlock？

synchronized 和 ReentrantLock 都是 Java 中提供的可重入鎖：

用法不同：synchronized 可用來修飾普通方法、靜態(tài)方法和代碼塊，而 ReentrantLock 只能用在代碼塊上。
獲取鎖和釋放鎖方式不同：synchronized 會自動加鎖和釋放鎖，當(dāng)進(jìn)入 synchronized 修飾的代碼塊之后會自動加鎖，當(dāng)離開 synchronized 的代碼段之后會自動釋放鎖。而 ReentrantLock 需要手動加鎖和釋放鎖
鎖類型不同：synchronized 屬于非公平鎖，而 ReentrantLock 既可以是公平鎖也可以是非公平鎖。
響應(yīng)中斷不同：ReentrantLock 可以響應(yīng)中斷，解決死鎖的問題，而 synchronized 不能響應(yīng)中斷。
底層實現(xiàn)不同：synchronized 是 JVM 層面通過監(jiān)視器實現(xiàn)的，而 ReentrantLock 是基于 AQS 實現(xiàn)的。

垃圾回收有哪些算法？

標(biāo)記-清除算法：標(biāo)記-清除算法分為“標(biāo)記”和“清除”兩個階段，首先通過可達(dá)性分析，標(biāo)記出所有需要回收的對象，然后統(tǒng)一回收所有被標(biāo)記的對象。標(biāo)記-清除算法有兩個缺陷，一個是效率問題，標(biāo)記和清除的過程效率都不高，另外一個就是，清除結(jié)束后會造成大量的碎片空間。有可能會造成在申請大塊內(nèi)存的時候因為沒有足夠的連續(xù)空間導(dǎo)致再次 GC。
復(fù)制算法：為了解決碎片空間的問題，出現(xiàn)了“復(fù)制算法”。復(fù)制算法的原理是，將內(nèi)存分成兩塊，每次申請內(nèi)存時都使用其中的一塊，當(dāng)內(nèi)存不夠時，將這一塊內(nèi)存中所有存活的復(fù)制到另一塊上。然后將然后再把已使用的內(nèi)存整個清理掉。復(fù)制算法解決了空間碎片的問題。但是也帶來了新的問題。因為每次在申請內(nèi)存時，都只能使用一半的內(nèi)存空間。內(nèi)存利用率嚴(yán)重不足。
標(biāo)記-整理算法：復(fù)制算法在 GC 之后存活對象較少的情況下效率比較高，但如果存活對象比較多時，會執(zhí)行較多的復(fù)制操作，效率就會下降。而老年代的對象在 GC 之后的存活率就比較高，所以就有人提出了“標(biāo)記-整理算法”。標(biāo)記-整理算法的“標(biāo)記”過程與“標(biāo)記-清除算法”的標(biāo)記過程一致，但標(biāo)記之后不會直接清理。而是將所有存活對象都移動到內(nèi)存的一端。移動結(jié)束后直接清理掉剩余部分。
分代回收算法：分代收集是將內(nèi)存劃分成了新生代和老年代。分配的依據(jù)是對象的生存周期，或者說經(jīng)歷過的 GC 次數(shù)。對象創(chuàng)建時，一般在新生代申請內(nèi)存，當(dāng)經(jīng)歷一次 GC 之后如果對還存活，那么對象的年齡 +1。當(dāng)年齡超過一定值(默認(rèn)是 15，可以通過參數(shù) -XX:MaxTenuringThreshold 來設(shè)定)后，如果對象還存活，那么該對象會進(jìn)入老年代。

介紹一下CMS？

CMS收集器是老年代的收集器，可以配合新生代的Serial和ParNew收集器一起使用
CMS收集器以最小的停頓時間為目標(biāo)的收集器。
CMS收集器是使用“標(biāo)記-清除”算法進(jìn)行的垃圾回收，容易產(chǎn)生內(nèi)存碎片
CMS產(chǎn)生浮動垃圾過多時會退化為serial old，效率低，CMS清除垃圾時是并發(fā)清除的，這個時候，垃圾回收線程和用戶線程同時工作會產(chǎn)生浮動垃圾，也就意味著CMS垃圾回收器必須預(yù)留一部分內(nèi)存空間用于存放浮動垃圾

redis

為什么redis要重新實現(xiàn)string結(jié)構(gòu) 弄成動態(tài)的？

Redis 的 String 字符串是用 SDS 數(shù)據(jù)結(jié)構(gòu)存儲的。下圖就是 Redis 5.0 的 SDS 的數(shù)據(jù)結(jié)構(gòu)：

圖片

結(jié)構(gòu)中的每個成員變量分別介紹下：

len，記錄了字符串長度。這樣獲取字符串長度的時候，只需要返回這個成員變量值就行，時間復(fù)雜度只需要 O（1）。
alloc，分配給字符數(shù)組的空間長度。這樣在修改字符串的時候，可以通過 alloc - len 計算出剩余的空間大小，可以用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將 SDS 的空間擴(kuò)展至執(zhí)行修改所需的大小，然后才執(zhí)行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現(xiàn)前面所說的緩沖區(qū)溢出的問題。
flags，用來表示不同類型的 SDS。一共設(shè)計了 5 種類型，分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在說明區(qū)別之處。
buf[]，字符數(shù)組，用來保存實際數(shù)據(jù)。不僅可以保存字符串，也可以保存二進(jìn)制數(shù)據(jù)。

總的來說，Redis 的 SDS 結(jié)構(gòu)在原本字符數(shù)組之上，增加了三個元數(shù)據(jù)：len、alloc、flags，用來解決 C 語言字符串的缺陷。

O（1）復(fù)雜度獲取字符串長度

C 語言的字符串長度獲取 strlen 函數(shù)，需要通過遍歷的方式來統(tǒng)計字符串長度，時間復(fù)雜度是 O（N）。而 Redis 的 SDS 結(jié)構(gòu)因為加入了 len 成員變量，那么獲取字符串長度的時候，直接返回這個成員變量的值就行，所以復(fù)雜度只有 O（1）。

二進(jìn)制安全

因為 SDS 不需要用 “\0” 字符來標(biāo)識字符串結(jié)尾了，而是有個專門的 len 成員變量來記錄長度，所以可存儲包含 “\0” 的數(shù)據(jù)。但是 SDS 為了兼容部分 C 語言標(biāo)準(zhǔn)庫的函數(shù)， SDS 字符串結(jié)尾還是會加上 “\0” 字符。

因此， SDS 的 API 都是以處理二進(jìn)制的方式來處理 SDS 存放在 buf[] 里的數(shù)據(jù)，程序不會對其中的數(shù)據(jù)做任何限制，數(shù)據(jù)寫入的時候時什么樣的，它被讀取時就是什么樣的。通過使用二進(jìn)制安全的 SDS，而不是 C 字符串，使得 Redis 不僅可以保存文本數(shù)據(jù)，也可以保存任意格式的二進(jìn)制數(shù)據(jù)。

不會發(fā)生緩沖區(qū)溢出

C 語言的字符串標(biāo)準(zhǔn)庫提供的字符串操作函數(shù)，大多數(shù)（比如 strcat 追加字符串函數(shù)）都是不安全的，因為這些函數(shù)把緩沖區(qū)大小是否滿足操作需求的工作交由開發(fā)者來保證，程序內(nèi)部并不會判斷緩沖區(qū)大小是否足夠用，當(dāng)發(fā)生了緩沖區(qū)溢出就有可能造成程序異常結(jié)束。

所以，Redis 的 SDS 結(jié)構(gòu)里引入了 alloc 和 len 成員變量，這樣 SDS API 通過 alloc - len 計算，可以算出剩余可用的空間大小，這樣在對字符串做修改操作的時候，就可以由程序內(nèi)部判斷緩沖區(qū)大小是否足夠用。

而且，當(dāng)判斷出緩沖區(qū)大小不夠用時，Redis 會自動將擴(kuò)大 SDS 的空間大小，以滿足修改所需的大小。

為什么redis是單線程但速度快？

官方使用基準(zhǔn)測試的結(jié)果是，單線程的 Redis 吞吐量可以達(dá)到 10W/每秒，如下圖所示：

圖片

之所以 Redis 采用單線程（網(wǎng)絡(luò) I/O 和執(zhí)行命令）那么快，有如下幾個原因：

Redis 的大部分操作都在內(nèi)存中完成，并且采用了高效的數(shù)據(jù)結(jié)構(gòu)，因此 Redis 瓶頸可能是機器的內(nèi)存或者網(wǎng)絡(luò)帶寬，而并非 CPU，既然 CPU 不是瓶頸，那么自然就采用單線程的解決方案了；
Redis 采用單線程模型可以避免了多線程之間的競爭，省去了多線程切換帶來的時間和性能上的開銷，而且也不會導(dǎo)致死鎖問題。
Redis 采用了 I/O 多路復(fù)用機制處理大量的客戶端 Socket 請求，IO 多路復(fù)用機制是指一個線程處理多個 IO 流，就是我們經(jīng)常聽到的 select/epoll 機制。簡單來說，在 Redis 只運行單線程的情況下，該機制允許內(nèi)核中，同時存在多個監(jiān)聽 Socket 和已連接 Socket。內(nèi)核會一直監(jiān)聽這些 Socket 上的連接請求或數(shù)據(jù)請求。一旦有請求到達(dá)，就會交給 Redis 線程處理，這就實現(xiàn)了一個 Redis 線程處理多個 IO 流的效果。

redis的緩存雪崩是什么？怎么解決？

緩存雪崩：當(dāng)大量緩存數(shù)據(jù)在同一時間過期（失效）或者 Redis 故障宕機時，如果此時有大量的用戶請求，都無法在 Redis 中處理，于是全部請求都直接訪問數(shù)據(jù)庫，從而導(dǎo)致數(shù)據(jù)庫的壓力驟增，嚴(yán)重的會造成數(shù)據(jù)庫宕機，從而形成一系列連鎖反應(yīng)，造成整個系統(tǒng)崩潰，這就是緩存雪崩的問題。

圖片

緩存雪崩解決方案：

均勻設(shè)置過期時間：如果要給緩存數(shù)據(jù)設(shè)置過期時間，應(yīng)該避免將大量的數(shù)據(jù)設(shè)置成同一個過期時間。我們可以在對緩存數(shù)據(jù)設(shè)置過期時間時，給這些數(shù)據(jù)的過期時間加上一個隨機數(shù)，這樣就保證數(shù)據(jù)不會在同一時間過期。
互斥鎖：當(dāng)業(yè)務(wù)線程在處理用戶請求時，如果發(fā)現(xiàn)訪問的數(shù)據(jù)不在 Redis 里，就加個互斥鎖，保證同一時間內(nèi)只有一個請求來構(gòu)建緩存（從數(shù)據(jù)庫讀取數(shù)據(jù)，再將數(shù)據(jù)更新到 Redis 里），當(dāng)緩存構(gòu)建完成后，再釋放鎖。未能獲取互斥鎖的請求，要么等待鎖釋放后重新讀取緩存，要么就返回空值或者默認(rèn)值。實現(xiàn)互斥鎖的時候，最好設(shè)置超時時間，不然第一個請求拿到了鎖，然后這個請求發(fā)生了某種意外而一直阻塞，一直不釋放鎖，這時其他請求也一直拿不到鎖，整個系統(tǒng)就會出現(xiàn)無響應(yīng)的現(xiàn)象。
后臺更新緩存：業(yè)務(wù)線程不再負(fù)責(zé)更新緩存，緩存也不設(shè)置有效期，而是讓緩存“永久有效”，并將更新緩存的工作交由后臺線程定時更新。

mysql

mysql的隔離級別有哪些？

讀未提交（read uncommitted），指一個事務(wù)還沒提交時，它做的變更就能被其他事務(wù)看到；
讀提交（read committed），指一個事務(wù)提交之后，它做的變更才能被其他事務(wù)看到；
可重復(fù)讀（repeatable read），指一個事務(wù)執(zhí)行過程中看到的數(shù)據(jù)，一直跟這個事務(wù)啟動時看到的數(shù)據(jù)是一致的，MySQL InnoDB 引擎的默認(rèn)隔離級別；
串行化（serializable）；會對記錄加上讀寫鎖，在多個事務(wù)對這條記錄進(jìn)行讀寫操作時，如果發(fā)生了讀寫沖突的時候，后訪問的事務(wù)必須等前一個事務(wù)執(zhí)行完成，才能繼續(xù)執(zhí)行；

按隔離水平高低排序如下：

圖片

針對不同的隔離級別，并發(fā)事務(wù)時可能發(fā)生的現(xiàn)象也會不同。

圖片

也就是說：

在「讀未提交」隔離級別下，可能發(fā)生臟讀、不可重復(fù)讀和幻讀現(xiàn)象；
在「讀提交」隔離級別下，可能發(fā)生不可重復(fù)讀和幻讀現(xiàn)象，但是不可能發(fā)生臟讀現(xiàn)象；
在「可重復(fù)讀」隔離級別下，可能發(fā)生幻讀現(xiàn)象，但是不可能臟讀和不可重復(fù)讀現(xiàn)象；
在「串行化」隔離級別下，臟讀、不可重復(fù)讀和幻讀現(xiàn)象都不可能會發(fā)生。

接下來，舉個具體的例子來說明這四種隔離級別，有一張賬戶余額表，里面有一條賬戶余額為 100 萬的記錄。然后有兩個并發(fā)的事務(wù)，事務(wù) A 只負(fù)責(zé)查詢余額，事務(wù) B 則會將我的余額改成 200 萬，下面是按照時間順序執(zhí)行兩個事務(wù)的行為：

圖片

在不同隔離級別下，事務(wù) A 執(zhí)行過程中查詢到的余額可能會不同：

在「讀未提交」隔離級別下，事務(wù) B 修改余額后，雖然沒有提交事務(wù)，但是此時的余額已經(jīng)可以被事務(wù) A 看見了，于是事務(wù) A 中余額 V1 查詢的值是 200 萬，余額 V2、V3 自然也是 200 萬了；
在「讀提交」隔離級別下，事務(wù) B 修改余額后，因為沒有提交事務(wù)，所以事務(wù) A 中余額 V1 的值還是 100 萬，等事務(wù) B 提交完后，最新的余額數(shù)據(jù)才能被事務(wù) A 看見，因此額 V2、V3 都是 200 萬；
在「可重復(fù)讀」隔離級別下，事務(wù) A 只能看見啟動事務(wù)時的數(shù)據(jù)，所以余額 V1、余額 V2 的值都是 100 萬，當(dāng)事務(wù) A 提交事務(wù)后，就能看見最新的余額數(shù)據(jù)了，所以余額 V3 的值是 200 萬；
在「串行化」隔離級別下，事務(wù) B 在執(zhí)行將余額 100 萬修改為 200 萬時，由于此前事務(wù) A 執(zhí)行了讀操作，這樣就發(fā)生了讀寫沖突，于是就會被鎖住，直到事務(wù) A 提交后，事務(wù) B 才可以繼續(xù)執(zhí)行，所以從 A 的角度看，余額 V1、V2 的值是 100 萬，余額 V3 的值是 200萬。

這四種隔離級別具體是如何實現(xiàn)的呢？

對于「讀未提交」隔離級別的事務(wù)來說，因為可以讀到未提交事務(wù)修改的數(shù)據(jù)，所以直接讀取最新的數(shù)據(jù)就好了；
對于「串行化」隔離級別的事務(wù)來說，通過加讀寫鎖的方式來避免并行訪問；
對于「讀提交」和「可重復(fù)讀」隔離級別的事務(wù)來說，它們是通過 Read View來實現(xiàn)的，它們的區(qū)別在于創(chuàng)建 Read View 的時機不同，「讀提交」隔離級別是在「每個語句執(zhí)行前」都會重新生成一個 Read View，而「可重復(fù)讀」隔離級別是「啟動事務(wù)時」生成一個 Read View，然后整個事務(wù)期間都在用這個 Read View。

MVCC機制具體講一下

MVCC允許多個事務(wù)同時讀取同一行數(shù)據(jù)，而不會彼此阻塞，每個事務(wù)看到的數(shù)據(jù)版本是該事務(wù)開始時的數(shù)據(jù)版本。

這意味著，如果其他事務(wù)在此期間修改了數(shù)據(jù)，正在運行的事務(wù)仍然看到的是它開始時的數(shù)據(jù)狀態(tài)，從而實現(xiàn)了非阻塞讀操作。對于「讀提交」和「可重復(fù)讀」隔離級別的事務(wù)來說，它們是通過 Read View 來實現(xiàn)的，它們的區(qū)別在于創(chuàng)建 Read View 的時機不同，大家可以把 Read View 理解成一個數(shù)據(jù)快照，就像相機拍照那樣，定格某一時刻的風(fēng)景。

「讀提交」隔離級別是在「每個select語句執(zhí)行前」都會重新生成一個 Read View；
「可重復(fù)讀」隔離級別是執(zhí)行第一條select時，生成一個 Read View，然后整個事務(wù)期間都在用這個 Read View。

Read View 有四個重要的字段：

圖片

m_ids ：指的是在創(chuàng)建 Read View 時，當(dāng)前數(shù)據(jù)庫中「活躍事務(wù)」的事務(wù) id 列表，注意是一個列表，“活躍事務(wù)”指的就是，啟動了但還沒提交的事務(wù)。
min_trx_id ：指的是在創(chuàng)建 Read View 時，當(dāng)前數(shù)據(jù)庫中「活躍事務(wù)」中事務(wù) id 最小的事務(wù)，也就是 m_ids 的最小值。
max_trx_id ：這個并不是 m_ids 的最大值，而是創(chuàng)建 Read View 時當(dāng)前數(shù)據(jù)庫中應(yīng)該給下一個事務(wù)的 id 值，也就是全局事務(wù)中最大的事務(wù) id 值 + 1；
creator_trx_id ：指的是創(chuàng)建該 Read View 的事務(wù)的事務(wù) id。

對于使用 InnoDB 存儲引擎的數(shù)據(jù)庫表，它的聚簇索引記錄中都包含下面兩個隱藏列：

圖片

trx_id，當(dāng)一個事務(wù)對某條聚簇索引記錄進(jìn)行改動時，就會把該事務(wù)的事務(wù) id 記錄在 trx_id 隱藏列里；
roll_pointer，每次對某條聚簇索引記錄進(jìn)行改動時，都會把舊版本的記錄寫入到 undo 日志中，然后這個隱藏列是個指針，指向每一個舊版本記錄，于是就可以通過它找到修改前的記錄。

在創(chuàng)建 Read View 后，我們可以將記錄中的 trx_id 劃分這三種情況：

圖片

一個事務(wù)去訪問記錄的時候，除了自己的更新記錄總是可見之外，還有這幾種情況：

如果記錄的 trx_id 值小于 Read View 中的 min_trx_id 值，表示這個版本的記錄是在創(chuàng)建 Read View 前已經(jīng)提交的事務(wù)生成的，所以該版本的記錄對當(dāng)前事務(wù)可見。
如果記錄的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示這個版本的記錄是在創(chuàng)建 Read View 后才啟動的事務(wù)生成的，所以該版本的記錄對當(dāng)前事務(wù)不可見。
如果記錄的 trx_id 值在 Read View 的 min_trx_id 和 max_trx_id 之間，需要判斷 trx_id 是否在 m_ids 列表中：
如果記錄的 trx_id 在 m_ids 列表中，表示生成該版本記錄的活躍事務(wù)依然活躍著（還沒提交事務(wù)），所以該版本的記錄對當(dāng)前事務(wù)不可見。
如果記錄的 trx_id 不在 m_ids列表中，表示生成該版本記錄的活躍事務(wù)已經(jīng)被提交，所以該版本的記錄對當(dāng)前事務(wù)可見。

這種通過「版本鏈」來控制并發(fā)事務(wù)訪問同一個記錄時的行為就叫 MVCC（多版本并發(fā)控制）。

索引的幾種類型有哪些？

MySQL可以按照四個角度來分類索引。

按「數(shù)據(jù)結(jié)構(gòu)」分類：B+tree索引、Hash索引、Full-text索引。
按「物理存儲」分類：聚簇索引（主鍵索引）、二級索引（輔助索引）。
按「字段特性」分類：主鍵索引、唯一索引、普通索引、前綴索引。
按「字段個數(shù)」分類：單列索引、聯(lián)合索引。

InnoDB 是在 MySQL 5.5 之后成為默認(rèn)的 MySQL 存儲引擎，B+Tree 索引類型也是 MySQL 存儲引擎采用最多的索引類型。

什么時候會出現(xiàn)索引失效？

6 種會發(fā)生索引失效的情況：

當(dāng)我們使用左或者左右模糊匹配的時候，也就是 like %xx 或者 like %xx%這兩種方式都會造成索引失效；
當(dāng)我們在查詢條件中對索引列使用函數(shù)，就會導(dǎo)致索引失效。
當(dāng)我們在查詢條件中對索引列進(jìn)行表達(dá)式計算，也是無法走索引的。
MySQL 在遇到字符串和數(shù)字比較的時候，會自動把字符串轉(zhuǎn)為數(shù)字，然后再進(jìn)行比較。如果字符串是索引列，而條件語句中的輸入?yún)?shù)是數(shù)字的話，那么索引列會發(fā)生隱式類型轉(zhuǎn)換，由于隱式類型轉(zhuǎn)換是通過 CAST 函數(shù)實現(xiàn)的，等同于對索引列使用了函數(shù)，所以就會導(dǎo)致索引失效。
聯(lián)合索引要能正確使用需要遵循最左匹配原則，也就是按照最左優(yōu)先的方式進(jìn)行索引的匹配，否則就會導(dǎo)致索引失效。
在 WHERE 子句中，如果在 OR 前的條件列是索引列，而在 OR 后的條件列不是索引列，那么索引會失效。

算法

算法題目是反轉(zhuǎn)鏈表，只給了main函數(shù)要手動寫輸入輸出，用到了list但這個IDE不讓我加頭文件，寫完以后一直報錯導(dǎo)致運行不起來，最后講了一下思路。思路：在遍歷鏈表時，將當(dāng)前節(jié)點的 next 指針改為指向前一個節(jié)點。由于節(jié)點沒有引用其前一個節(jié)點，因此必須事先存儲其前一個節(jié)點。在更改引用之前，還需要存儲后一個節(jié)點。最后返回新的頭引用。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

復(fù)雜度分析：

時間復(fù)雜度：O(n)，其中 n 是鏈表的長度。需要遍歷鏈表一次。
空間復(fù)雜度：O(1)。

責(zé)任編輯：武曉燕來源：小林coding

網(wǎng)絡(luò)反轉(zhuǎn)鏈表 list