阿里二面涼了，難蹦。。。

圖解學習網站：https://xiaolincoding.com

大家好， 我是小林。

分享一位同學阿里巴巴的后端面經，共有 2 面，第一面很順利過了，可惜掛在第二面。

這兩面的知識點范圍，我?guī)痛蠹伊_列一下：

• 網絡：TCP、HTTP
• mysql：索引應用、索引結構、隔離級別、最左匹配
• redis：zset、緩存一致性
• java：HashMap、ConcurrntHashMap、ArrayList
• 數據結構：b樹、b+樹、紅黑樹
• 排序算法：快排、冒泡排序
• 手撕算法：最長公共前綴 、無重復最長字串

雖然都是比較基礎的知識，但是會問很細，沒深入學習的話，很容易扛不住。

一面八股

ZSet用過嗎 用過 zset 實現排行榜的功能。以博文點贊排名為例，小林發(fā)表了五篇博文，分別獲得贊為 200、40、100、50、150。

# arcticle:1 文章獲得了200個贊
> ZADD user:xiaolin:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章獲得了40個贊
> ZADD user:xiaolin:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章獲得了100個贊
> ZADD user:xiaolin:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章獲得了50個贊
> ZADD user:xiaolin:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章獲得了150個贊
> ZADD user:xiaolin:ranking 150 arcticle:5
(integer) 1

文章 arcticle:4 新增一個贊，可以使用 ZINCRBY 命令（為有序集合key中元素member的分值加上increment）：

> ZINCRBY user:xiaolin:ranking 1 arcticle:4
"51"

查看某篇文章的贊數，可以使用 ZSCORE 命令（返回有序集合key中元素個數）：

> ZSCORE user:xiaolin:ranking arcticle:4
"50"

獲取小林文章贊數最多的 3 篇文章，可以使用 ZREVRANGE 命令（倒序獲取有序集合 key 從start下標到stop下標的元素）：

# WITHSCORES 表示把 score 也顯示出來
> ZREVRANGE user:xiaolin:ranking 0 2 WITHSCORES
1) "arcticle:1"
2) "200"
3) "arcticle:5"
4) "150"
5) "arcticle:3"
6) "100"

獲取小林 100 贊到 200 贊的文章，可以使用 ZRANGEBYSCORE 命令（返回有序集合中指定分數區(qū)間內的成員，分數由低到高排序）：

> ZRANGEBYSCORE user:xiaolin:ranking 100 200 WITHSCORES
1) "arcticle:3"
2) "100"
3) "arcticle:5"
4) "150"
5) "arcticle:1"
6) "200"

Zset 類型的底層數據結構是由壓縮列表或跳表實現的：

• 如果有序集合的元素個數小于 128 個，并且每個元素的值小于 64 字節(jié)時，Redis 會使用壓縮列表作為 Zset 類型的底層數據結構；
• 如果有序集合的元素不滿足上面的條件，Redis 會使用跳表作為 Zset 類型的底層數據結構；

在 Redis 7.0 中，壓縮列表數據結構已經廢棄了，交由 listpack 數據結構來實現了。

ConcurrntHashMap和HashMap的底層數據結構

• HashMap：底層數據結構是數組+鏈表/紅黑樹。HashMap使用數組存儲元素，每個數組元素對應一個桶（bucket），每個桶可以存放多個鍵值對。當發(fā)生哈希沖突時，采用鏈表或者紅黑樹來解決沖突，JDK 8之后，鏈表長度過長時會將鏈表轉換為紅黑樹，以提高查找效率。
• ConcurrentHashMap：底層數據結構是分段鎖（Segment數組）+數組+鏈表/紅黑樹。ConcurrentHashMap將整個數據結構分成多個Segment（段），每個Segment相當于一個小的HashMap，擁有自己的鎖。這樣在進行寫操作時，只需要鎖住對應的Segment，而其他Segment仍然可以并發(fā)讀寫，提高了并發(fā)性能。從JDK 8開始，ConcurrentHashMap的實現已經不再使用Segment，而是采用了更加高效的方式來實現并發(fā)操作。

ConcurrntHashMap怎么實現線程安全的

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是數組加鏈表的形式實現的，而數組又分為：大數組 Segment 和小數組 HashEntry。

Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲鍵值對數據。一個 ConcurrentHashMap 里包含一個 Segment 數組，一個 Segment 里包含一個 HashEntry 數組，每個 HashEntry 是一個鏈表結構的元素。

JDK 1.7 ConcurrentHashMap 分段鎖技術將數據分成一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問，能夠實現真正的并發(fā)訪問。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 雖然是線程安全的，但因為它的底層實現是數組 + 鏈表的形式，所以在數據比較多的情況下訪問是很慢的，因為要遍歷整個鏈表，而 JDK 1.8 則使用了數組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實現，具體實現結構如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實現的線程安全的。添加元素時首先會判斷容器是否為空：

• 如果為空則使用  volatile  加  CAS  來初始化
• 如果容器不為空，則根據存儲的元素計算該位置是否為空。
• 如果根據存儲的元素計算結果為空，則利用  CAS  設置該節(jié)點；
• 如果根據存儲的元素計算結果不為空，則使用 synchronized  ，然后，遍歷桶中的數據，并替換或新增節(jié)點到桶中，最后再判斷是否需要轉為紅黑樹，這樣就能保證并發(fā)訪問時的線程安全了。

如果把上面的執(zhí)行用一句話歸納的話，就相當于是ConcurrentHashMap通過對頭結點加鎖來保證線程安全的，鎖的粒度相比 Segment 來說更小了，發(fā)生沖突和加鎖的頻率降低了，并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表，那么當數據量比較大的時候，查詢性能也得到了很大的提升，從之前的 O(n) 優(yōu)化到了 O(logn) 的時間復雜度。

三次握手說一下

TCP 三次握手過程

• 一開始，客戶端和服務端都處于 CLOSE 狀態(tài)。先是服務端主動監(jiān)聽某個端口，處于 LISTEN 狀態(tài)
• 客戶端會隨機初始化序號（client_isn），將此序號置于 TCP 首部的「序號」字段中，同時把 SYN 標志位置為 1，表示 SYN 報文。接著把第一個 SYN 報文發(fā)送給服務端，表示向服務端發(fā)起連接，該報文不包含應用層數據，之后客戶端處于 SYN-SENT 狀態(tài)。
• 服務端收到客戶端的 SYN 報文后，首先服務端也隨機初始化自己的序號（server_isn），將此序號填入 TCP 首部的「序號」字段中，其次把 TCP 首部的「確認應答號」字段填入 client_isn + 1, 接著把 SYN 和 ACK 標志位置為 1。最后把該報文發(fā)給客戶端，該報文也不包含應用層數據，之后服務端處于 SYN-RCVD 狀態(tài)。
• 客戶端收到服務端報文后，還要向服務端回應最后一個應答報文，首先該應答報文 TCP 首部 ACK 標志位置為 1 ，其次「確認應答號」字段填入 server_isn + 1 ，最后把報文發(fā)送給服務端，這次報文可以攜帶客戶到服務端的數據，之后客戶端處于 ESTABLISHED 狀態(tài)。
• 服務端收到客戶端的應答報文后，也進入 ESTABLISHED 狀態(tài)。

四次揮手說一下

TCP 四次揮手過程

具體過程：

• 客戶端主動調用關閉連接的函數，于是就會發(fā)送 FIN 報文，這個  FIN 報文代表客戶端不會再發(fā)送數據了，進入 FIN_WAIT_1 狀態(tài)；
• 服務端收到了 FIN 報文，然后馬上回復一個 ACK 確認報文，此時服務端進入 CLOSE_WAIT 狀態(tài)。在收到 FIN 報文的時候，TCP 協議棧會為 FIN 包插入一個文件結束符 EOF 到接收緩沖區(qū)中，服務端應用程序可以通過 read 調用來感知這個 FIN 包，這個 EOF 會被放在已排隊等候的其他已接收的數據之后，所以必須要得繼續(xù) read 接收緩沖區(qū)已接收的數據；
• 接著，當服務端在 read 數據的時候，最后自然就會讀到 EOF，接著 read() 就會返回 0，這時服務端應用程序如果有數據要發(fā)送的話，就發(fā)完數據后才調用關閉連接的函數，如果服務端應用程序沒有數據要發(fā)送的話，可以直接調用關閉連接的函數，這時服務端就會發(fā)一個 FIN 包，這個  FIN 報文代表服務端不會再發(fā)送數據了，之后處于 LAST_ACK 狀態(tài)；
• 客戶端接收到服務端的 FIN 包，并發(fā)送 ACK 確認包給服務端，此時客戶端將進入 TIME_WAIT 狀態(tài)；
• 服務端收到 ACK 確認包后，就進入了最后的 CLOSE 狀態(tài)；
• 客戶端經過 2MSL 時間之后，也進入 CLOSE 狀態(tài)；

為什么四次揮手之后要等2MSL?

MSL 是 Maximum Segment Lifetime，報文最大生存時間，它是任何報文在網絡上存在的最長時間，超過這個時間報文將被丟棄。因為 TCP 報文基于是 IP 協議的，而 IP 頭中有一個 TTL 字段，是 IP 數據報可以經過的最大路由數，每經過一個處理他的路由器此值就減 1，當此值為 0 則數據報將被丟棄，同時發(fā)送 ICMP 報文通知源主機。

MSL 與 TTL 的區(qū)別：MSL 的單位是時間，而 TTL 是經過路由跳數。所以 MSL 應該要大于等于 TTL 消耗為 0 的時間，以確保報文已被自然消亡。

TTL 的值一般是 64，Linux 將 MSL 設置為 30 秒，意味著 Linux 認為數據報文經過 64 個路由器的時間不會超過 30 秒，如果超過了，就認為報文已經消失在網絡中了。

TIME_WAIT 等待 2 倍的 MSL，比較合理的解釋是：網絡中可能存在來自發(fā)送方的數據包，當這些發(fā)送方的數據包被接收方處理后又會向對方發(fā)送響應，所以一來一回需要等待 2 倍的時間。

比如，如果被動關閉方沒有收到斷開連接的最后的 ACK 報文，就會觸發(fā)超時重發(fā) FIN 報文，另一方接收到 FIN 后，會重發(fā) ACK 給被動關閉方， 一來一去正好 2 個 MSL。

可以看到 2MSL時長 這其實是相當于至少允許報文丟失一次。比如，若 ACK 在一個 MSL 內丟失，這樣被動方重發(fā)的 FIN 會在第 2 個 MSL 內到達，TIME_WAIT 狀態(tài)的連接可以應對。

HTTP進行TCP連接之后，在什么情況下會中斷

• 當服務端或者客戶端執(zhí)行 close 系統調用的時候，會發(fā)送FIN報文，就會進行四次揮手的過程
• 當發(fā)送方發(fā)送了數據之后，接收方超過一段時間沒有響應ACK報文，發(fā)送方重傳數據達到最大次數的時候，就會斷開TCP連接
• 當HTTP長時間沒有進行請求和響應的時候，超過一定的時間，就會釋放連接

HTTP、SOCKET和TCP的區(qū)別

HTTP是應用層協議，定義了客戶端和服務器之間交換的數據格式和規(guī)則；Socket是通信的一端，提供了網絡通信的接口；TCP是傳輸層協議，負責在網絡中建立可靠的數據傳輸連接。它們在網絡通信中扮演不同的角色和層次。

• HTTP是一種用于傳輸超文本數據的應用層協議，用于在客戶端和服務器之間傳輸和顯示Web頁面。
• Socket是計算機網絡中的一種抽象，用于描述通信鏈路的一端，提供了底層的通信接口，可實現不同計算機之間的數據交換。
• TCP是一種面向連接的、可靠的傳輸層協議，負責在通信的兩端之間建立可靠的數據傳輸連接。

說說MySQL索引

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

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

  聚簇索引數據結構

聚簇索引數據結構是B+樹，B+Tree 是一種多叉樹，葉子節(jié)點才存放數據，非葉子節(jié)點只存放索引，而且每個節(jié)點里的數據是按主鍵順序存放的。每一層父節(jié)點的索引值都會出現在下層子節(jié)點的索引值中，因此在葉子節(jié)點中，包括了所有的索引值信息，并且每一個葉子節(jié)點都有兩個指針，分別指向下一個葉子節(jié)點和上一個葉子節(jié)點，形成一個雙向鏈表。

聚簇索引的 B+Tree 如圖所示：

對于聚簇索引，它的數據存放在哪

數據存儲到葉子節(jié)點，非葉子節(jié)點只有索引。

你使用索引有什么經驗嗎？

索引最大的好處是提高查詢速度，但是索引也是有缺點的，比如：

• 需要占用物理空間，數量越大，占用空間越大；
• 創(chuàng)建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增大；
• 會降低表的增刪改的效率，因為每次增刪改索引，B+ 樹為了維護索引有序性，都需要進行動態(tài)維護。

所以，索引不是萬能鑰匙，它也是根據場景來使用的。

什么時候適用索引？

• 字段有唯一性限制的，比如商品編碼；
• 經常用于 WHERE 查詢條件的字段，這樣能夠提高整個表的查詢速度，如果查詢條件不是一個字段，可以建立聯合索引。
• 經常用于 GROUP BY 和 ORDER BY 的字段，這樣在查詢的時候就不需要再去做一次排序了，因為我們都已經知道了建立索引之后在 B+Tree 中的記錄都是排序好的。

什么時候不需要創(chuàng)建索引？

• WHERE 條件，GROUP BY，ORDER BY 里用不到的字段，索引的價值是快速定位，如果起不到定位的字段通常是不需要創(chuàng)建索引的，因為索引是會占用物理空間的。
• 字段中存在大量重復數據，不需要創(chuàng)建索引，比如性別字段，只有男女，如果數據庫表中，男女的記錄分布均勻，那么無論搜索哪個值都可能得到一半的數據。在這些情況下，還不如不要索引，因為 MySQL 還有一個查詢優(yōu)化器，查詢優(yōu)化器發(fā)現某個值出現在表的數據行中的百分比很高的時候，它一般會忽略索引，進行全表掃描。
• 表數據太少的時候，不需要創(chuàng)建索引；
• 經常更新的字段不用創(chuàng)建索引，比如不要對電商項目的用戶余額建立索引，因為索引字段頻繁修改，由于要維護 B+Tree的有序性，那么就需要頻繁的重建索引，這個過程是會影響數據庫性能的。

說說最左匹配原則，給你一個聯合索引（a,b,c） a, ab , abc , bc , ac走索引嗎

使用聯合索引時，存在最左匹配原則，也就是按照最左優(yōu)先的方式進行索引的匹配。在使用聯合索引進行查詢的時候，如果不遵循「最左匹配原則」，聯合索引會失效，這樣就無法利用到索引快速查詢的特性了。

(a, b, c) 聯合索引，是先按 a 排序，在 a 相同的情況再按 b 排序，在 b 相同的情況再按 c 排序。所以，b 和 c 是全局無序，局部相對有序的，這樣在沒有遵循最左匹配原則的情況下，是無法利用到索引的。

• where a=?，符合最左匹配原則，能走索引。
• where a = ? and b = ?，符合最左匹配原則，能走索引。
• where  a = ? and b = ? and c = ?，  符合最左匹配原則，能走索引。
• where  b = ? and c = ? ，不符合最左匹配原則，不能走索引。
• where  a = ? and c = ? ，能走走索引，但是只有 a 字段能走索引，c 字段無法走索引，不過 c 字段可以利用索引下推。

數據庫和緩存的一致性如何保證

對于讀數據，我會選擇旁路緩存策略，如果 cache 不命中，會從 db 加載數據到 cache。

對于寫數據，我會選擇更新 db 后，再刪除緩存。

針對刪除緩存異常的情況，我還會對 key 設置過期時間兜底，只要過期時間一到，過期的 key 就會被刪除了。

除此之外，還有兩種方式應對刪除緩存失敗的情況。

消息隊列方案

我們可以引入消息隊列，將第二個操作（刪除緩存）要操作的數據加入到消息隊列，由消費者來操作數據。

• 如果應用刪除緩存失敗，可以從消息隊列中重新讀取數據，然后再次刪除緩存，這個就是重試機制。當然，如果重試超過的一定次數，還是沒有成功，我們就需要向業(yè)務層發(fā)送報錯信息了。
• 如果刪除緩存成功，就要把數據從消息隊列中移除，避免重復操作，否則就繼續(xù)重試。

舉個例子，來說明重試機制的過程。

訂閱 MySQL binlog，再操作緩存

「先更新數據庫，再刪緩存」的策略的第一步是更新數據庫，那么更新數據庫成功，就會產生一條變更日志，記錄在 binlog 里。

于是我們就可以通過訂閱 binlog 日志，拿到具體要操作的數據，然后再執(zhí)行緩存刪除，阿里巴巴開源的 Canal 中間件就是基于這個實現的。

Canal 模擬 MySQL 主從復制的交互協議，把自己偽裝成一個 MySQL 的從節(jié)點，向 MySQL 主節(jié)點發(fā)送 dump 請求，MySQL 收到請求后，就會開始推送 Binlog 給 Canal，Canal 解析 Binlog 字節(jié)流之后，轉換為便于讀取的結構化數據，供下游程序訂閱使用。

下圖是 Canal 的工作原理：

所以，如果要想保證「先更新數據庫，再刪緩存」策略第二個操作能執(zhí)行成功，我們可以使用「消息隊列來重試緩存的刪除」，或者「訂閱 MySQL binlog 再操作緩存」，這兩種方法有一個共同的特點，都是采用異步操作緩存。

算法

• 最長公共前綴
• 無重復最長字串

二面八股

說說聚簇索引和非聚簇索引的區(qū)別？

• 聚簇索引的葉子節(jié)點存放的是實際數據，所有完整的用戶記錄都存放在聚簇索引的葉子節(jié)點；
• 非聚簇索引的葉子節(jié)點存放的是主鍵值，而不是實際數據。

如果某個查詢語句使用了二級索引（非聚簇索引），但是查詢的數據不是主鍵值，這時在二級索引找到主鍵值后，需要去聚簇索引中獲得數據行，這個過程就叫作「回表」，也就是說要查兩個 B+ 樹才能查到數據。

不過，當查詢的數據是主鍵值時，因為只在二級索引（非聚簇索引）就能查詢到，不用再去聚簇索引查，這個過程就叫作「索引覆蓋」，也就是只需要查一個 B+ 樹就能找到數據。

說說B+樹和B樹的區(qū)別

• 在B+樹中，數據都存儲在葉子節(jié)點上，而非葉子節(jié)點只存儲索引信息；而B樹的非葉子節(jié)點既存儲索引信息也存儲部分數據。
• B+樹的葉子節(jié)點使用鏈表相連，便于范圍查詢和順序訪問；B樹的葉子節(jié)點沒有鏈表連接。
• B+樹的查找性能更穩(wěn)定，每次查找都需要查找到葉子節(jié)點；而B樹的查找可能會在非葉子節(jié)點找到數據，性能相對不穩(wěn)定。

說說B+樹非葉子節(jié)點分裂流

InnoDB 創(chuàng)建主鍵索引默認為聚簇索引，數據被存放在了 B+Tree 的葉子節(jié)點上。也就是說，同一個葉子節(jié)點內的各個數據是按主鍵順序存放的，因此，每當有一條新的數據插入時，數據庫會根據主鍵將其插入到對應的葉子節(jié)點中。

如果我們使用自增主鍵，那么每次插入的新數據就會按順序添加到當前索引節(jié)點的位置，不需要移動已有的數據，當頁面寫滿，就會自動開辟一個新頁面。因為每次插入一條新記錄，都是追加操作，不需要重新移動數據，因此這種插入數據的方法效率非常高。

如果我們使用非自增主鍵，由于每次插入主鍵的索引值都是隨機的，因此每次插入新的數據時，就可能會插入到現有數據頁中間的某個位置，這將不得不移動其它數據來滿足新數據的插入，甚至需要從一個頁面復制數據到另外一個頁面，我們通常將這種情況稱為頁分裂。頁分裂還有可能會造成大量的內存碎片，導致索引結構不緊湊，從而影響查詢效率。

舉個例子，假設某個數據頁中的數據是1、3、5、9，且數據頁滿了，現在準備插入一個數據7，則需要把數據頁分割為兩個數據頁：

出現頁分裂時，需要將一個頁的記錄移動到另外一個頁，性能會受到影響，同時頁空間的利用率下降，造成存儲空間的浪費。

而如果記錄是順序插入的，例如插入數據11，則只需開辟新的數據頁，也就不會發(fā)生頁分裂：

因此，在使用 InnoDB 存儲引擎時，如果沒有特別的業(yè)務需求，建議使用自增字段作為主鍵。

select * from xxx where a = x  b= x  order by c   怎么建立索引

可以建立（a，b，c）聯合索引，這樣三個字段都能利用索引，并且 c 字段還能利用索引的有序性，避免了額外排序。

數據庫事務隔離級別

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

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

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

說說幻讀

在一個事務內多次查詢某個符合查詢條件的「記錄數量」，如果出現前后兩次查詢到的記錄數量不一樣的情況，就意味著發(fā)生了「幻讀」現象。

假設有 A 和 B 這兩個事務同時在處理，事務 A 先開始從數據庫查詢賬戶余額大于 100 萬的記錄，發(fā)現共有 5 條，然后事務 B 也按相同的搜索條件也是查詢出了 5 條記錄。

接下來，事務 A 插入了一條余額超過 100 萬的賬號，并提交了事務，此時數據庫超過 100 萬余額的賬號個數就變?yōu)?6。

然后事務 B 再次查詢賬戶余額大于 100 萬的記錄，此時查詢到的記錄數量有 6 條，發(fā)現和前一次讀到的記錄數量不一樣了，就感覺發(fā)生了幻覺一樣，這種現象就被稱為幻讀。

說說快排流程，時間復雜度

快速排序的流程如下：

• 從數組中選擇一個基準元素（通常是數組中間位置的元素）。
• 將數組分成兩部分，小于基準元素的放在左邊，大于基準元素的放在右邊。
• 遞歸地對左右兩部分進行快速排序。

快速排序的時間復雜度為O(n log n)，其中n為數組的長度。最壞情況下時間復雜度為O(n^2)，發(fā)生在每次選擇的基準元素都是最大或最小值時。平均情況下時間復雜度為O(n log n)，效率較高。

快排為什么時間復雜度最差是O（n^2）

主要是因為在每次劃分時選擇的基準元素不合適導致的。當每次選擇的基準元素都是當前子數組中的最大或最小元素時，就會導致每次劃分只能減少一個元素，而不是均勻地分成兩部分，從而造成時間復雜度達到O(n^2)。

這種情況通常發(fā)生在數組已經有序或基本有序的情況下。為了避免最壞情況發(fā)生，可以通過隨機選擇基準元素或者使用三數取中法等策略來提高快速排序的性能。

快排這么強，那冒泡排序還有必要嗎？

冒泡排序在一些特定場景下仍然有其優(yōu)勢，比如：

• 對于小規(guī)模數據或基本有序的數據，冒泡排序可能比快速排序更簡單、更直觀。
• 冒泡排序是穩(wěn)定排序算法，相對于快速排序的不穩(wěn)定性，在某些情況下可能更適合要求穩(wěn)定性的場景。
• 冒泡排序是原地排序算法，不需要額外的空間，適合空間復雜度要求嚴格的場景。

說說紅黑樹

紅黑樹是一種自平衡的二叉查找樹，

具有以下特點：

1. 每個節(jié)點要么是紅色，要么是黑色。
2. 根節(jié)點是黑色。
3. 每個葉子節(jié)點（NIL節(jié)點）是黑色。
4. 如果一個節(jié)點是紅色，則其子節(jié)點必須是黑色。
5. 從任一節(jié)點到其每個葉子節(jié)點的所有路徑都包含相同數目的黑色節(jié)點。

紅黑樹的自平衡性質可以保證在進行插入、刪除等操作后，樹的高度保持在O(log n)內，從而保持了較高的查找、插入和刪除效率。

下面是紅黑樹插入節(jié)點的過程，這左旋右旋的操作，就是為了自平衡。

說說紅黑樹怎么左旋右旋

左旋和右旋是兩種基本的旋轉操作，用于保持紅黑樹的平衡。下面簡單描述一下左旋和右旋的操作步驟：

左旋操作：

1. 將當前節(jié)點的右子節(jié)點作為新的根節(jié)點。
2. 將新根節(jié)點的左子節(jié)點移動為當前節(jié)點的右子節(jié)點。
3. 如果當前節(jié)點有父節(jié)點，將當前節(jié)點的父節(jié)點更新為新根節(jié)點的父節(jié)點；否則，將新根節(jié)點設置為樹的根節(jié)點。
4. 更新新根節(jié)點和其子節(jié)點的父節(jié)點關系。

接下來看下圖片展示，首先斷開節(jié)點PL與右子節(jié)點G的關系，同時將其右子節(jié)點的引用指向節(jié)點C2；然后斷開節(jié)點G與左子節(jié)點C2的關系，同時將G的左子節(jié)點的應用指向節(jié)點PL。

接下來再放下 gif 圖，希望能幫助大家更好地理解左旋

右旋操作與左旋操作對稱，具體步驟如下：

1. 將當前節(jié)點的左子節(jié)點作為新的根節(jié)點。
2. 將新根節(jié)點的右子節(jié)點移動為當前節(jié)點的左子節(jié)點。
3. 如果當前節(jié)點有父節(jié)點，將當前節(jié)點的父節(jié)點更新為新根節(jié)點的父節(jié)點；否則，將新根節(jié)點設置為樹的根節(jié)點。
4. 更新新根節(jié)點和其子節(jié)點的父節(jié)點關系。

首先斷開節(jié)點G與左子節(jié)點PL的關系，同時將其左子節(jié)點的引用指向節(jié)點C2；然后斷開節(jié)點PL與右子節(jié)點C2的關系，同時將PL的右子節(jié)點的應用指向節(jié)點G。

右旋的gif展示（圖片來自網絡）:

說說hashmap擴容，說說負載因子

hashmap擴容

HashMap 擴容的目的是為了減少哈希沖突，Java中hashmap擴容過程如下圖：

當進行 put 操作導致整個哈希表的負載因子因此到達閾值后，會進入一個阻塞的擴容流程中，先通過復制一個兩杯容量的entry數組，然后將原有entry中的元素進行遍歷執(zhí)行rehash，jdk1.8使用的是2次冪的擴展(指長度擴為原來2倍)。

所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置。因此在執(zhí)行rehash的時候只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。

負載因子

HashMap 負載因子 loadFactor 的默認值是 0.75，當 HashMap 中的元素個數超過了容量的 75% 時，就會進行擴容。

默認負載因子為 0.75，是因為它提供了空間和時間復雜度之間的良好平衡。

負載因子太低會導致大量的空桶浪費空間，負載因子太高會導致大量的碰撞，降低性能。0.75 的負載因子在這兩個因素之間取得了良好的平衡。

說說擴容之后的退化問題

HashMap在發(fā)生擴容時，會重新計算元素的存放位置，可能導致原本分布均勻的元素在新的容量下發(fā)生“退化”，即多個元素映射到同一個桶（bucket）上，使得鏈表長度過長，影響了HashMap的性能。這種情況下，HashMap的查找、插入和刪除操作的時間復雜度可能會由原本的O(1)上升到O(n)，嚴重影響了HashMap的效率。

為了解決HashMap擴容后的退化問題，通常采用以下方法：

1. 提高負載因子（load factor）：在發(fā)生擴容之前，可以提前擴容，使得哈希表中的元素數量與桶的數量的比值在擴容后不會過高，減少退化的可能性。
2. 使用紅黑樹：在JDK 8中，當鏈表長度過長時，會將鏈表轉換為紅黑樹，以減少查找時間，提高性能。

說說ArrayList的擴容

ArrayList在添加元素時，如果當前元素個數已經達到了內部數組的容量上限，就會觸發(fā)擴容操作。ArrayList的擴容操作主要包括以下幾個步驟：

• 計算新的容量：一般情況下，新的容量會擴大為原容量的1.5倍（在JDK 10之后，擴容策略做了調整），然后檢查是否超過了最大容量限制。
• 創(chuàng)建新的數組：根據計算得到的新容量，創(chuàng)建一個新的更大的數組。
• 將元素復制：將原來數組中的元素逐個復制到新數組中。
• 更新引用：將ArrayList內部指向原數組的引用指向新數組。
• 完成擴容：擴容完成后，可以繼續(xù)添加新元素。

ArrayList的擴容操作涉及到數組的復制和內存的重新分配，所以在頻繁添加大量元素時，擴容操作可能會影響性能。為了減少擴容帶來的性能損耗，可以在初始化ArrayList時預分配足夠大的容量，避免頻繁觸發(fā)擴容操作。

為什么ArrayList擴容是1.5倍

1.5 可以充分利用移位操作，減少浮點數或者運算時間和運算次數。

// 新容量計算
int newCapacity = oldCapacity + (oldCapacity >> 1);