大家好，我是小林。

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

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

圖片

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

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

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

圖片

計算機網(wǎng)絡

加密方式有哪些？

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

Java

知道哪些java集合？

圖片

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

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

Set不允許存在重復的元素，與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)，使用雙向鏈表維護元素插入順序。
• TreeSet通過TreeMap實現(xiàn)的，添加元素到集合時按照比較規(guī)則將其插入合適的位置，保證插入后的集合仍然有序。

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

• HashMap：JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突），JDK1.8 以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）時，將鏈表轉化為紅黑樹，以減少搜索時間
• LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現(xià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ù)結構，多線程背景下，在數(shù)組擴容的時候，存在 Entry 鏈死循環(huán)和數(shù)據(jù)丟失問題。
• JDK 1.8 HashMap 采用數(shù)組 + 鏈表 + 紅黑二叉樹的數(shù)據(jù)結構，優(yōu)化了 1.7 中數(shù)組擴容的方案，解決了 Entry 鏈死循環(huán)和數(shù)據(jù)丟失問題。但是多線程背景下，put 方法存在數(shù)據(jù)覆蓋的問題。

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

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

為什么hashmap擴容的時候不安全？

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

這里假設

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

未 resize 前的數(shù)據(jù)結構如下：

圖片

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

圖片

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

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

圖片

此時線程 A 中運行結果如下：

圖片

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

圖片

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

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

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

此時結果如下：

圖片

繼續(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

結果如下：

圖片

再次進行循環(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)結束。結果如下：

圖片

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

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

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

圖片

線程 A 和線程 B 進行 put 操作，同樣線程 A 掛起：

圖片

此時線程 A 的運行結果如下：

圖片

此時線程 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。接著進行下一次循環(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)結束，3 元素丟失，并形成環(huán)形鏈表。并在后續(xù)操作 hashmap 時造成死循環(huán)。

圖片

JVM內存有哪些結構？

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

圖片

JVM的內存結構主要分為以下幾個部分：

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

對象存在堆里，什么時候對象不在堆里？

Java對象并不一定都是分配在堆內存上，如果JVM確定一個對象不會逃逸，它可以選擇將這個對象分配在線程的棧上而不是堆上。棧是線程私有的內存區(qū)域，當方法執(zhí)行結束時，棧上的數(shù)據(jù)會被自動銷毀。

棧上分配依賴于逃逸分析和標量替換。

• 標量替換：就是將對象拆解為其成員變量。例如，如果一個對象包含整數(shù)、浮點數(shù)和其他基本數(shù)據(jù)類型的字段，那么這些字段將被單獨分配到棧上。解決不會因為沒有一大塊連續(xù)空間導致對象內存不夠分配的問題。
• 標量：標量即不可被進一步分解的量，JAVA的基本數(shù)據(jù)類型就是標量（如：int，long等基本數(shù)據(jù)類型以及reference類型等）。
• 聚合量：聚合量就是可以被進一步分解的量，通常是對象，JAVA中對象就是可以被進一步分解的聚合量，對象包含多個成員變量。

相關的JVM參數(shù)：

• 逃逸分析：-XX:+DoEscapeAnalysis（JDK7以后默認開啟）
• 標量替換：-XX:+EliminateAllocations（JDK7以后默認開啟）

通過逃逸分析和棧上分配，JVM可以減少垃圾回收的頻率和開銷。這有助于提高應用程序的性能，特別是在存在大量臨時對象的情況下，因為這些對象可以更快地釋放，而不會給垃圾回收器帶來過大的壓力。

java類加載過程介紹一下？

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

圖片

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

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

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

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

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

雙親委派機制是什么？

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

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

java有哪些鎖？

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

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

具體講一下synchronized和reentrantlock？

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

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

垃圾回收有哪些算法？

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

介紹一下CMS？

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

redis

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

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

圖片

結構中的每個成員變量分別介紹下：

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

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

O（1）復雜度獲取字符串長度

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

二進制安全

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

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

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

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

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

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

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

官方使用基準測試的結果是，單線程的 Redis 吞吐量可以達到 10W/每秒，如下圖所示：

圖片

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

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

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

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

圖片

緩存雪崩解決方案：

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

mysql

mysql的隔離級別有哪些？

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

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

圖片

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

圖片

也就是說：

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

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

圖片

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

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

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

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

MVCC機制具體講一下

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

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

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

Read View 有四個重要的字段：

圖片

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

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

圖片

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

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

圖片

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

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

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

索引的幾種類型有哪些？

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

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

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

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

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

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

算法

算法題目是反轉鏈表，只給了main函數(shù)要手動寫輸入輸出，用到了list但這個IDE不讓我加頭文件，寫完以后一直報錯導致運行不起來，最后講了一下思路。思路：在遍歷鏈表時，將當前節(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;
    }
}

復雜度分析：

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