大家好，我是小林。

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

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

圖片

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

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

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

圖片

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

加密方式有哪些？

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

Java

知道哪些java集合？

圖片

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

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

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

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

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

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

hashmap是線程安全的嗎？

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

• JDK 1.7 HashMap 采用數(shù)組 + 鏈表的數(shù)據(jù)結(jié)構(gòu)，多線程背景下，在數(shù)組擴(kuò)容的時(shí)候，存在 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ā)場(chǎng)景使用。
• ConcurrentHashmap在JDK1.7和1.8的版本改動(dòng)比較大，1.7使用Segment+HashEntry分段鎖的方式實(shí)現(xiàn)，1.8則拋棄了Segment，改為使用CAS+synchronized+Node實(shí)現(xiàn)，同樣也加入了紅黑樹，避免鏈表過長(zhǎng)導(dǎo)致性能的問題。

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

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

這里假設(shè)

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

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

圖片

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

圖片

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

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

圖片

此時(shí)線程 A 中運(yùn)行結(jié)果如下：

圖片

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

圖片

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

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

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

此時(shí)結(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)形鏈表，并且此時(shí) e=null 循環(huán)結(jié)束。結(jié)果如下：

圖片

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

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

遵照上述分析過程，初始時(shí)：

圖片

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

圖片

此時(shí)線程 A 的運(yùn)行結(jié)果如下：

圖片

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

圖片

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

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

執(zhí)行 newtable[i]=e，就將 7 放在了 table[3] 的位置，此時(shí) 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] 位置，此時(shí) e=null 循環(huán)結(jié)束，3 元素丟失，并形成環(huán)形鏈表。并在后續(xù)操作 hashmap 時(shí)造成死循環(huán)。

圖片

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

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

圖片

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

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

對(duì)象存在堆里，什么時(shí)候?qū)ο蟛辉诙牙铮?/h3>

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

棧上分配依賴于逃逸分析和標(biāo)量替換。

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

相關(guān)的JVM參數(shù)：

• 逃逸分析：-XX:+DoEscapeAnalysis（JDK7以后默認(rèn)開啟）
• 標(biāo)量替換：-XX:+EliminateAllocations（JDK7以后默認(rèn)開啟）

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

java類加載過程介紹一下？

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

圖片

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

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

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

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

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

雙親委派機(jī)制是什么？

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

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

java有哪些鎖？

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

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

具體講一下synchronized和reentrantlock？

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

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

垃圾回收有哪些算法？

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

介紹一下CMS？

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

redis

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

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

圖片

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

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

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

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

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

二進(jìn)制安全

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

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

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

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

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

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

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

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

圖片

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

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

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

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

圖片

緩存雪崩解決方案：

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

mysql

mysql的隔離級(jí)別有哪些？

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

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

圖片

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

圖片

也就是說：

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

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

圖片

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

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

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

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

MVCC機(jī)制具體講一下

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

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

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

Read View 有四個(gè)重要的字段：

圖片

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

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

圖片

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

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

圖片

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

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

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

索引的幾種類型有哪些？

MySQL可以按照四個(gè)角度來分類索引。

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

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

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

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

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

算法

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

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ù)雜度分析：

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