大家好，我是小林。

校招生通常都是一張白紙，所以校招面試過程中，面試官通常都會比較傾向問一些基礎知識，比如 Java、mysql、Redis、網絡、操作系統、數據結構與算法這些底層的原理知識，看你在學校學習的內容，你是否能夠真的掌握了。

今天就分享一個重點在數據結構考察比較多的美團Java后端面經，從常見的數據結構->Java 集合>MySQL B+樹->Redis 數據結構。所以，這是一場比較重基礎的后端面試，問題也比較多，面試時長超過 1 小時了，還挺艱難的。

數據結構

LRU是什么？如何實現？

LRU 是一種緩存淘汰算法，當緩存空間已滿時，優先淘汰最長時間未被訪問的數據。

實現的方式是哈希表+雙向鏈表結合。

LRU

具體實現步驟如下：

• 使用哈希表存儲數據的鍵值對，鍵為緩存的鍵，值為對應的節點。
• 使用雙向鏈表存儲數據節點，鏈表頭部為最近訪問的節點，鏈表尾部為最久未訪問的節點。
• 當數據被訪問時，如果數據存在于緩存中，則將對應節點移動到鏈表頭部；如果數據不存在于緩存中，則將數據添加到緩存中，同時創建一個新節點并插入到鏈表頭部。
• 當緩存空間已滿時，需要淘汰最久未訪問的節點，即鏈表尾部的節點。

上面這種思想方式，LRU 算法可以在 O(1) 的時間復雜度內實現數據的插入、查找和刪除操作。每次訪問數據時，都會將對應的節點移動到鏈表頭部，保證鏈表頭部的節點是最近訪問的數據，而鏈表尾部的節點是最久未訪問的數據。當緩存空間不足時，淘汰鏈表尾部的節點即可。

平衡二叉樹結構是怎么樣的？

平衡二叉樹是在二叉搜索樹的基礎上，平衡二叉樹還需要滿足如下條件:

• 左右兩個子樹的高度差（平衡因子）的絕對值不超過1
• 左右兩個子樹都是一棵平衡二叉樹

圖片

分析：

• 圖一是一個平衡二叉樹，它滿足平衡二叉樹的定義。
• 圖二不是平衡二叉樹，其原因并不是不滿足平衡因子的條件，而是因為它不滿足二叉搜索樹的構成條件，這提醒我們平衡二叉樹首先要是一棵二叉搜索樹。
• 圖三滿足平衡二叉樹的構成條件。
• 圖 4 中的節點 (8) 平衡因子為 3，不滿足平衡二叉樹的要求。

堆是什么？

堆是一顆完全二叉樹，這樣實現的堆也被稱為二叉堆。堆中節點的值都大于等于（或小于等于）其子節點的值，堆中如果節點的值都大于等于其子節點的值，我們把它稱為大頂堆，如果都小于等于其子節點的值，我們將其稱為小頂堆。

下圖中，1，2 是大頂堆，3 是小頂堆， 4 不是堆（不是完全二叉樹）

圖片

棧和隊列，舉個使用場景例子

圖片

What is Stack and Queue

• 棧是一種后進先出（LIFO）的數據結構，函數的調用和返回往往使用棧來管理函數調用的順序。
• 隊列是一種先進先出（FIFO）的數據結構，類似于排隊等待的隊伍，先到的人會先被服務。隊列常用于需要先進先出的場景，例如：在網絡通信或磁盤讀寫等場景中，使用隊列來管理數據的接收和發送順序，以平衡生產者和消費者之間的速度差異。

Java

HashMap 是怎么實現的？

圖片

存儲對象時，我們將K/V傳給put方法時，它調用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據當前bucket的占用情況自動調整容量(超過Load Facotr則resize為原來的2倍)。

獲取對象時，我們將K傳給get，它調用hashCode計算hash從而得到bucket位置，并進一步調用equals()方法確定鍵值對。如果發生碰撞的時候，Hashmap通過鏈表將產生碰撞沖突的元素組織起來，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。

HashMap 擴容過程中鏈表如何遷移到新的位置？

擴容分為2步：

• 第1步是對哈希表長度的擴展（2倍）
• 第2步是將舊哈希表中的數據放到新的哈希表中。

因為我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置。

如我們從16擴展為32時，具體的變化如下所示：

rehash

因此元素在重新計算hash之后，因為n變為2倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

resize

因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。可以看看下圖為16擴充為32的resize示意圖：

resize16-32

這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。

HashMap  為什么線程不安全？

兩個線程執行put()操作時，可能導致數據覆蓋。

假設A、B兩個線程同時執行put()操作，且兩個key都指向同一個buekct，那么此時兩個結點，都會做頭插法。當線程A和線程B都獲取到了bucket的頭結點后，若此時線程A的時間片用完，線程B將其新數據完成了頭插法操作，此時輪到線程A操作，但這時線程A所據有的舊頭結點已經過時了（并未包含線程B剛插入的新結點），線程A再做頭插法操作，就會抹掉B剛剛新增的結點，導致數據丟失。

CurrentHashMap 怎么保證線程安全的？

在JDK7版本及以前，**ConcurrentHashMap**類使用了分段鎖的技術（segment + Lock），但在jdk8之后，也做了較大改動，使用回了synchronized修飾符。

JDK1.8中的ConcurrentHashMap不再使用Segment分段鎖，而是以table數組的頭結點作為synchronized的鎖。

ConcurrentHashMap保證線程安全主要有三個地方。

• 使用volatile保證當Node中的值變化時對于其他線程是可見的
• 使用table數組的頭結點作為synchronized的鎖來保證寫操作的安全
• 頭結點為null時，使用CAS操作來保證數據能正確的寫入。

MySQL

MySQL為什么InnoDB是默認引擎？

InnoDB引擎在事務支持、并發性能、崩潰恢復等方面具有優勢，因此被MySQL選擇為默認的存儲引擎。

• 事務支持：InnoDB引擎提供了對事務的支持，可以進行ACID（原子性、一致性、隔離性、持久性）屬性的操作。Myisam存儲引擎是不支持事務的。
• 并發性能：InnoDB引擎采用了行級鎖定的機制，可以提供更好的并發性能，Myisam存儲引擎只支持表鎖，鎖的粒度比較大。
• 崩潰恢復：InnoDB引引擎通過 redolog 日志實現了崩潰恢復，可以在數據庫發生異常情況（如斷電）時，通過日志文件進行恢復，保證數據的持久性和一致性。Myisam是不支持崩潰恢復的。

MySQL為什么使用B+ 樹？

MySQL 是會將數據持久化在硬盤，而存儲功能是由 MySQL 存儲引擎實現的，所以討論 MySQL 使用哪種數據結構作為索引，實際上是在討論存儲引使用哪種數據結構作為索引，InnoDB 是 MySQL 默認的存儲引擎，它就是采用了 B+ 樹作為索引的數據結構。

要設計一個 MySQL 的索引數據結構，不僅僅考慮數據結構增刪改的時間復雜度，更重要的是要考慮磁盤 I/0 的操作次數。因為索引和記錄都是存放在硬盤，硬盤是一個非常慢的存儲設備，我們在查詢數據的時候，最好能在盡可能少的磁盤 I/0 的操作次數內完成。

二分查找樹雖然是一個天然的二分結構，能很好的利用二分查找快速定位數據，但是它存在一種極端的情況，每當插入的元素都是樹內最大的元素，就會導致二分查找樹退化成一個鏈表，此時查詢復雜度就會從 O(logn)降低為 O(n)。

為了解決二分查找樹退化成鏈表的問題，就出現了自平衡二叉樹，保證了查詢操作的時間復雜度就會一直維持在 O(logn) 。但是它本質上還是一個二叉樹，每個節點只能有 2 個子節點，隨著元素的增多，樹的高度會越來越高。

而樹的高度決定于磁盤 I/O 操作的次數，因為樹是存儲在磁盤中的，訪問每個節點，都對應一次磁盤 I/O 操作，也就是說樹的高度就等于每次查詢數據時磁盤 IO 操作的次數，所以樹的高度越高，就會影響查詢性能。

B 樹和 B+ 都是通過多叉樹的方式，會將樹的高度變矮，所以這兩個數據結構非常適合檢索存于磁盤中的數據。

但是 MySQL 默認的存儲引擎 InnoDB 采用的是 B+ 作為索引的數據結構。原因有：

• B+ 樹的非葉子節點不存放實際的記錄數據，僅存放索引，因此數據量相同的情況下，相比存儲即存索引又存記錄的 B 樹，B+樹的非葉子節點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節點的磁盤 I/O次數會更少。
• B+ 樹有大量的冗余節點（所有非葉子節點都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，比如刪除根節點的時候，不會像 B 樹那樣會發生復雜的樹的變化；
• B+ 樹葉子節點之間用鏈表連接了起來，有利于范圍查詢，而 B 樹要實現范圍查詢，因此只能通過樹的遍歷來完成范圍查詢，這會涉及多個節點的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。

B+樹的葉子節點鏈表是單向還是雙向？

雙向的，為了實現倒序遍歷或者排序。

圖片

Innodb 使用的 B+ 樹有一些特別的點，比如：

• B+ 樹的葉子節點之間是用「雙向鏈表」進行連接，這樣的好處是既能向右遍歷，也能向左遍歷。
• B+ 樹點節點內容是數據頁，數據頁里存放了用戶的記錄以及各種信息，每個數據頁默認大小是 16 KB。

Innodb 根據索引類型不同，分為聚集和二級索引。他們區別在于，聚集索引的葉子節點存放的是實際數據，所有完整的用戶記錄都存放在聚集索引的葉子節點，而二級索引的葉子節點存放的是主鍵值，而不是實際數據。

因為表的數據都是存放在聚集索引的葉子節點里，所以 InnoDB 存儲引擎一定會為表創建一個聚集索引，且由于數據在物理上只會保存一份，所以聚簇索引只能有一個，而二級索引可以創建多個。

MVCC是什么？作用？

MVCC 是多版本并發控制，MVCC保證了事務之間的隔離性，事務只能看到已經提交的數據版本，從而保證了數據的一致性，并且避免了事務讀寫并發的問題，因為 select 快照讀是不會加鎖的。

可重復讀隔離級別是開啟事務，執行第一個 select 查詢的時候，會創建 Read View，然后整個事務期間都在用這個 Read View。讀提交隔離級別是在每次select 查詢時，都會生成一個新的 Read View。

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

圖片

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

• 如果記錄的 trx_id 值小于 Read View 中的 min_trx_id 值，表示這個版本的記錄是在創建 Read View 前已經提交的事務生成的，所以該版本的記錄對當前事務可見。
• 如果記錄的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示這個版本的記錄是在創建 Read View 后才啟動的事務生成的，所以該版本的記錄對當前事務不可見。
• 如果記錄的 trx_id 值在 Read View 的 min_trx_id 和 max_trx_id之間，需要判斷 trx_id 是否在 m_ids 列表中：

• 如果記錄的 trx_id 在 m_ids 列表中，表示生成該版本記錄的活躍事務依然活躍著（還沒提交事務），所以該版本的記錄對當前事務不可見。
• 如果記錄的 trx_id 不在 m_ids列表中，表示生成該版本記錄的活躍事務已經被提交，所以該版本的記錄對當前事務可見。

更新是如何保證一致的？

更新屬于當前讀，會加X型的行級鎖，是通過鎖來保證一致性的。

比如，事務 A 執行對一條 id = 1 的記錄進行了更新，其他事務如果想更新或者刪除這條記錄的話，會發生阻塞，只有當事務 a 提交了事務才會釋放鎖。

如何回滾一條記錄？undo log具體怎么回滾?

事務執行過程中，執行 rollback 語句就能回滾事務了。

每當 InnoDB 引擎對一條記錄進行操作（修改、刪除、新增）時，要把回滾時需要的信息都記錄到 undo log 里，比如：

• 在插入一條記錄時，要把這條記錄的主鍵值記下來，這樣之后回滾時只需要把這個主鍵值對應的記錄刪掉就好了；
• 在刪除一條記錄時，要把這條記錄中的內容都記下來，這樣之后回滾時再把由這些內容組成的記錄插入到表中就好了；
• 在更新一條記錄時，要把被更新的列的舊值記下來，這樣之后回滾時再把這些列更新為舊值就好了。

在發生回滾時，就讀取 undo log 里的數據，然后做原先相反操作。比如當 delete 一條記錄時，undo log 中會把記錄中的內容都記下來，然后執行回滾操作的時候，就讀取 undo log 里的數據，然后進行 insert 操作。

如何查詢慢sql產生的原因?

可以通過慢查詢日志來定位慢 sql 語句。

索引失效的情況有哪些？

6 種會發生索引失效的情況：

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

Redis

redis數據結構有哪些？

Redis 提供了豐富的數據類型，常見的有五種數據類型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

圖片

img

圖片

隨著 Redis 版本的更新，后面又支持了四種數據類型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五種數據類型的應用場景：

• String 類型的應用場景：緩存對象、常規計數、分布式鎖、共享 session 信息等。
• List 類型的應用場景：消息隊列（但是有兩個問題：1. 生產者需要自行實現全局唯一 ID；2. 不能以消費組形式消費數據）等。
• Hash 類型：緩存對象、購物車等。
• Set 類型：聚合計算（并集、交集、差集）場景，比如點贊、共同關注、抽獎活動等。
• Zset 類型：排序場景，比如排行榜、電話和姓名排序等。

Redis 后續版本又支持四種數據類型，它們的應用場景如下：

• BitMap（2.2 版新增）：二值狀態統計的場景，比如簽到、判斷用戶登陸狀態、連續簽到用戶總數等；
• HyperLogLog（2.8 版新增）：海量數據基數統計的場景，比如百萬級網頁 UV 計數等；
• GEO（3.2 版新增）：存儲地理位置信息的場景，比如滴滴叫車；
• Stream（5.0 版新增）：消息隊列，相比于基于 List 類型實現的消息隊列，有這兩個特有的特性：自動生成全局唯一消息ID，支持以消費組形式消費數據。

zset 是怎么實現的？

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

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

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

為什么數據量小的時候用壓縮列表？

因為壓縮列表一種內存緊湊的數據結構，可以節約內存。

壓縮列表是 Redis 為了節約內存而開發的，它是由連續內存塊組成的順序型數據結構，有點類似于數組。

圖片

壓縮列表在表頭有三個字段：

• zlbytes，記錄整個壓縮列表占用對內存字節數；
• zltail，記錄壓縮列表「尾部」節點距離起始地址由多少字節，也就是列表尾的偏移量；
• zllen，記錄壓縮列表包含的節點數量；
• zlend，標記壓縮列表的結束點，固定值 0xFF（十進制255）。

在壓縮列表中，如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段（zllen）的長度直接定位，復雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復雜度就是 O(N) 了，因此壓縮列表不適合保存過多的元素。

另外，壓縮列表節點（entry）的構成如下：

圖片

壓縮列表節點包含三部分內容：

• prevlen，記錄了「前一個節點」的長度，目的是為了實現從后向前遍歷；
• encoding，記錄了當前節點實際數據的「類型和長度」，類型主要有兩種：字符串和整數。
• data，記錄了當前節點的實際數據，類型和長度都由 encoding 決定；

當我們往壓縮列表中插入數據時，壓縮列表就會根據數據類型是字符串還是整數，以及數據的大小，會使用不同空間大小的 prevlen 和 encoding 這兩個元素里保存的信息，這種根據數據大小和類型進行不同的空間大小分配的設計思想，正是 Redis 為了節省內存而采用的。

壓縮列表和跳躍表的區別？

• 存儲方式區別：壓縮列表是一種緊湊的線性連續存儲結構，通過將多個元素依次存儲在一塊連續的內存中，節省了內存空間。而跳躍表則是一種基于鏈表的數據結構，通過多層次的索引結構（跳躍層）來加速查找。
• 時間復雜度區別：在讀取或修改操作方面，壓縮列表的時間復雜度為O(n)，其中n是元素數量。因為壓縮列表需要線性掃描來定位元素。而跳躍表的讀取或修改操作的時間復雜度為O(log n)，通過跳躍層和鏈表的結構，可以快速定位到目標元素。
• 內存占用區別：壓縮列表具有較小的內存占用，對于較小的有序集合，可以更節省內存空間。而跳躍表則需要更多的內存空間來存儲索引結構，因此在空間占用方面相對較大。

redis主從復制的過程？

第一次同步的過程如下：

圖片

• 第一階段是建立鏈接、協商同步；
• 第二階段是主服務器同步數據給從服務器；
• 第三階段是主服務器發送新寫操作命令給從服務器

主從服務器在完成第一次同步后，就會基于長連接進行命令傳播。

圖片

后續主服務器可以通過這個連接繼續將寫操作命令傳播給從服務器，然后從服務器執行該命令，使得與主服務器的數據庫狀態相同。

通過什么復制？

全量復制階段是復制 rdb 文件。

增量復制命令存在哪里？

存放在 repl_backlog_buffer  緩沖區，在主服務器進行命令傳播時，不僅會將寫命令發送給從服務器，還會將寫命令寫入到 repl_backlog_buffer 緩沖區里，因此 這個緩沖區里會保存著最近傳播的寫命令。

圖片

RDB、AOF優缺點有哪些？

• RDB 是一個緊湊的二進制文件，相對較小，可以節省磁盤空間。。AOF文件是一個文本文件，記錄了每個寫操作，因此相對于RDB文件來說，AOF文件更大，因此RDB 在恢復大數據集時的速度比AOF 的恢復速度要快。
• Rob 的缺陷在于數據丟失的風險更大，如果Redis在最后一次快照之后發生故障，可能會丟失一部分數據。而 AOF以日志的方式記錄每個寫操作，數據的安全性會更高。

linux

ps命令里都有哪些選項，ps展示哪些東西？

圖片

ps命令展示內容：

• PID：進程ID。
• PPID：父進程ID。
• USER：進程所屬用戶。
• %CPU：CPU占用率。
• %MEM：內存占用率。
• VSZ：虛擬內存大小。
• RSS：物理內存大小。
• TTY：終端設備。
• STAT：進程狀態。
• START：進程啟動時間。
• TIME：進程累計CPU占用時間。
• COMMAND：進程命令或可執行文件。

ps命令選項：

• -a：顯示所有進程，包括其他用戶的進程。
• -u：顯示用戶相關的進程信息。
• -x：顯示沒有控制終端的進程。
• -e：顯示所有進程，等同于-a選項。
• -f：顯示詳細的進程信息，包括進程的父進程、運行狀態等。
• -l：顯示長格式的進程信息，包括進程的PID、PPID、CPU占用率等。
• -r：顯示正在運行的進程。
• -o：自定義輸出格式。

圖片

主要會展示：

• Load average（平均負載）：顯示系統在最近1分鐘、5分鐘和15分鐘內的平均負載情況。
• Tasks（任務）：顯示當前運行、睡眠、停止和僵尸狀態的進程數量。
• CPU usage（CPU使用情況）：顯示CPU的總體使用率以及每個CPU核心的使用率。
• Memory usage（內存使用情況）：顯示物理內存的總量、已使用量、空閑量、緩沖區和緩存區的使用量。
• Swap usage（交換空間使用情況）：顯示交換空間的總量、已使用量和剩余量。
• 進程列表：顯示當前運行的進程列表，包括進程的PID、用戶、CPU占用率、內存占用率、進程狀態、啟動時間和進程命令。

算法題

• 手撕算法：尋找第k大元素

其他

• 實習項目介紹
• 通過什么方式學習