大家好，我是小林。

校招生通常都是一張白紙，所以校招面試過(guò)程中，面試官通常都會(huì)比較傾向問(wèn)一些基礎(chǔ)知識(shí)，比如 Java、mysql、Redis、網(wǎng)絡(luò)、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)與算法這些底層的原理知識(shí)，看你在學(xué)校學(xué)習(xí)的內(nèi)容，你是否能夠真的掌握了。

今天就分享一個(gè)重點(diǎn)在數(shù)據(jù)結(jié)構(gòu)考察比較多的美團(tuán)Java后端面經(jīng)，從常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)->Java 集合>MySQL B+樹(shù)->Redis 數(shù)據(jù)結(jié)構(gòu)。所以，這是一場(chǎng)比較重基礎(chǔ)的后端面試，問(wèn)題也比較多，面試時(shí)長(zhǎng)超過(guò) 1 小時(shí)了，還挺艱難的。

數(shù)據(jù)結(jié)構(gòu)

LRU是什么？如何實(shí)現(xiàn)？

LRU 是一種緩存淘汰算法，當(dāng)緩存空間已滿(mǎn)時(shí)，優(yōu)先淘汰最長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)的數(shù)據(jù)。

實(shí)現(xiàn)的方式是哈希表+雙向鏈表結(jié)合。

LRU

具體實(shí)現(xiàn)步驟如下：

• 使用哈希表存儲(chǔ)數(shù)據(jù)的鍵值對(duì)，鍵為緩存的鍵，值為對(duì)應(yīng)的節(jié)點(diǎn)。
• 使用雙向鏈表存儲(chǔ)數(shù)據(jù)節(jié)點(diǎn)，鏈表頭部為最近訪(fǎng)問(wèn)的節(jié)點(diǎn)，鏈表尾部為最久未訪(fǎng)問(wèn)的節(jié)點(diǎn)。
• 當(dāng)數(shù)據(jù)被訪(fǎng)問(wèn)時(shí)，如果數(shù)據(jù)存在于緩存中，則將對(duì)應(yīng)節(jié)點(diǎn)移動(dòng)到鏈表頭部；如果數(shù)據(jù)不存在于緩存中，則將數(shù)據(jù)添加到緩存中，同時(shí)創(chuàng)建一個(gè)新節(jié)點(diǎn)并插入到鏈表頭部。
• 當(dāng)緩存空間已滿(mǎn)時(shí)，需要淘汰最久未訪(fǎng)問(wèn)的節(jié)點(diǎn)，即鏈表尾部的節(jié)點(diǎn)。

上面這種思想方式，LRU 算法可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)數(shù)據(jù)的插入、查找和刪除操作。每次訪(fǎng)問(wèn)數(shù)據(jù)時(shí)，都會(huì)將對(duì)應(yīng)的節(jié)點(diǎn)移動(dòng)到鏈表頭部，保證鏈表頭部的節(jié)點(diǎn)是最近訪(fǎng)問(wèn)的數(shù)據(jù)，而鏈表尾部的節(jié)點(diǎn)是最久未訪(fǎng)問(wèn)的數(shù)據(jù)。當(dāng)緩存空間不足時(shí)，淘汰鏈表尾部的節(jié)點(diǎn)即可。

平衡二叉樹(shù)結(jié)構(gòu)是怎么樣的？

平衡二叉樹(shù)是在二叉搜索樹(shù)的基礎(chǔ)上，平衡二叉樹(shù)還需要滿(mǎn)足如下條件:

• 左右兩個(gè)子樹(shù)的高度差（平衡因子）的絕對(duì)值不超過(guò)1
• 左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)

圖片

分析：

• 圖一是一個(gè)平衡二叉樹(shù)，它滿(mǎn)足平衡二叉樹(shù)的定義。
• 圖二不是平衡二叉樹(shù)，其原因并不是不滿(mǎn)足平衡因子的條件，而是因?yàn)樗粷M(mǎn)足二叉搜索樹(shù)的構(gòu)成條件，這提醒我們平衡二叉樹(shù)首先要是一棵二叉搜索樹(shù)。
• 圖三滿(mǎn)足平衡二叉樹(shù)的構(gòu)成條件。
• 圖 4 中的節(jié)點(diǎn) (8) 平衡因子為 3，不滿(mǎn)足平衡二叉樹(shù)的要求。

堆是什么？

堆是一顆完全二叉樹(shù)，這樣實(shí)現(xiàn)的堆也被稱(chēng)為二叉堆。堆中節(jié)點(diǎn)的值都大于等于（或小于等于）其子節(jié)點(diǎn)的值，堆中如果節(jié)點(diǎn)的值都大于等于其子節(jié)點(diǎn)的值，我們把它稱(chēng)為大頂堆，如果都小于等于其子節(jié)點(diǎn)的值，我們將其稱(chēng)為小頂堆。

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

圖片

棧和隊(duì)列，舉個(gè)使用場(chǎng)景例子

圖片

What is Stack and Queue

• 棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，函數(shù)的調(diào)用和返回往往使用棧來(lái)管理函數(shù)調(diào)用的順序。
• 隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，類(lèi)似于排隊(duì)等待的隊(duì)伍，先到的人會(huì)先被服務(wù)。隊(duì)列常用于需要先進(jìn)先出的場(chǎng)景，例如：在網(wǎng)絡(luò)通信或磁盤(pán)讀寫(xiě)等場(chǎng)景中，使用隊(duì)列來(lái)管理數(shù)據(jù)的接收和發(fā)送順序，以平衡生產(chǎn)者和消費(fèi)者之間的速度差異。

Java

HashMap 是怎么實(shí)現(xiàn)的？

圖片

存儲(chǔ)對(duì)象時(shí)，我們將K/V傳給put方法時(shí)，它調(diào)用hashCode計(jì)算hash從而得到bucket位置，進(jìn)一步存儲(chǔ)，HashMap會(huì)根據(jù)當(dāng)前bucket的占用情況自動(dòng)調(diào)整容量(超過(guò)Load Facotr則resize為原來(lái)的2倍)。

獲取對(duì)象時(shí)，我們將K傳給get，它調(diào)用hashCode計(jì)算hash從而得到bucket位置，并進(jìn)一步調(diào)用equals()方法確定鍵值對(duì)。如果發(fā)生碰撞的時(shí)候，Hashmap通過(guò)鏈表將產(chǎn)生碰撞沖突的元素組織起來(lái)，在Java 8中，如果一個(gè)bucket中碰撞沖突的元素超過(guò)某個(gè)限制(默認(rèn)是8)，則使用紅黑樹(shù)來(lái)替換鏈表，從而提高速度。

HashMap 擴(kuò)容過(guò)程中鏈表如何遷移到新的位置？

擴(kuò)容分為2步：

• 第1步是對(duì)哈希表長(zhǎng)度的擴(kuò)展（2倍）
• 第2步是將舊哈希表中的數(shù)據(jù)放到新的哈希表中。

因?yàn)槲覀兪褂玫氖?次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來(lái)2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。

如我們從16擴(kuò)展為32時(shí)，具體的變化如下所示：

rehash

因此元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會(huì)發(fā)生這樣的變化：

resize

因此，我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要重新計(jì)算hash，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了，是0的話(huà)索引沒(méi)變，是1的話(huà)索引變成“原索引+oldCap”。可以看看下圖為16擴(kuò)充為32的resize示意圖：

resize16-32

這個(gè)設(shè)計(jì)確實(shí)非常的巧妙，既省去了重新計(jì)算hash值的時(shí)間，而且同時(shí)，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過(guò)程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了。

HashMap  為什么線(xiàn)程不安全？

兩個(gè)線(xiàn)程執(zhí)行put()操作時(shí)，可能導(dǎo)致數(shù)據(jù)覆蓋。

假設(shè)A、B兩個(gè)線(xiàn)程同時(shí)執(zhí)行put()操作，且兩個(gè)key都指向同一個(gè)buekct，那么此時(shí)兩個(gè)結(jié)點(diǎn)，都會(huì)做頭插法。當(dāng)線(xiàn)程A和線(xiàn)程B都獲取到了bucket的頭結(jié)點(diǎn)后，若此時(shí)線(xiàn)程A的時(shí)間片用完，線(xiàn)程B將其新數(shù)據(jù)完成了頭插法操作，此時(shí)輪到線(xiàn)程A操作，但這時(shí)線(xiàn)程A所據(jù)有的舊頭結(jié)點(diǎn)已經(jīng)過(guò)時(shí)了（并未包含線(xiàn)程B剛插入的新結(jié)點(diǎn)），線(xiàn)程A再做頭插法操作，就會(huì)抹掉B剛剛新增的結(jié)點(diǎn)，導(dǎo)致數(shù)據(jù)丟失。

CurrentHashMap 怎么保證線(xiàn)程安全的？

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

JDK1.8中的ConcurrentHashMap不再使用Segment分段鎖，而是以table數(shù)組的頭結(jié)點(diǎn)作為synchronized的鎖。

ConcurrentHashMap保證線(xiàn)程安全主要有三個(gè)地方。

• 使用volatile保證當(dāng)Node中的值變化時(shí)對(duì)于其他線(xiàn)程是可見(jiàn)的
• 使用table數(shù)組的頭結(jié)點(diǎn)作為synchronized的鎖來(lái)保證寫(xiě)操作的安全
• 頭結(jié)點(diǎn)為null時(shí)，使用CAS操作來(lái)保證數(shù)據(jù)能正確的寫(xiě)入。

MySQL

MySQL為什么InnoDB是默認(rèn)引擎？

InnoDB引擎在事務(wù)支持、并發(fā)性能、崩潰恢復(fù)等方面具有優(yōu)勢(shì)，因此被MySQL選擇為默認(rèn)的存儲(chǔ)引擎。

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

MySQL為什么使用B+ 樹(shù)？

MySQL 是會(huì)將數(shù)據(jù)持久化在硬盤(pán)，而存儲(chǔ)功能是由 MySQL 存儲(chǔ)引擎實(shí)現(xiàn)的，所以討論 MySQL 使用哪種數(shù)據(jù)結(jié)構(gòu)作為索引，實(shí)際上是在討論存儲(chǔ)引使用哪種數(shù)據(jù)結(jié)構(gòu)作為索引，InnoDB 是 MySQL 默認(rèn)的存儲(chǔ)引擎，它就是采用了 B+ 樹(shù)作為索引的數(shù)據(jù)結(jié)構(gòu)。

要設(shè)計(jì)一個(gè) MySQL 的索引數(shù)據(jù)結(jié)構(gòu)，不僅僅考慮數(shù)據(jù)結(jié)構(gòu)增刪改的時(shí)間復(fù)雜度，更重要的是要考慮磁盤(pán) I/0 的操作次數(shù)。因?yàn)樗饕陀涗浂际谴娣旁谟脖P(pán)，硬盤(pán)是一個(gè)非常慢的存儲(chǔ)設(shè)備，我們?cè)诓樵?xún)數(shù)據(jù)的時(shí)候，最好能在盡可能少的磁盤(pán) I/0 的操作次數(shù)內(nèi)完成。

二分查找樹(shù)雖然是一個(gè)天然的二分結(jié)構(gòu)，能很好的利用二分查找快速定位數(shù)據(jù)，但是它存在一種極端的情況，每當(dāng)插入的元素都是樹(shù)內(nèi)最大的元素，就會(huì)導(dǎo)致二分查找樹(shù)退化成一個(gè)鏈表，此時(shí)查詢(xún)復(fù)雜度就會(huì)從 O(logn)降低為 O(n)。

為了解決二分查找樹(shù)退化成鏈表的問(wèn)題，就出現(xiàn)了自平衡二叉樹(shù)，保證了查詢(xún)操作的時(shí)間復(fù)雜度就會(huì)一直維持在 O(logn) 。但是它本質(zhì)上還是一個(gè)二叉樹(shù)，每個(gè)節(jié)點(diǎn)只能有 2 個(gè)子節(jié)點(diǎn)，隨著元素的增多，樹(shù)的高度會(huì)越來(lái)越高。

而樹(shù)的高度決定于磁盤(pán) I/O 操作的次數(shù)，因?yàn)闃?shù)是存儲(chǔ)在磁盤(pán)中的，訪(fǎng)問(wèn)每個(gè)節(jié)點(diǎn)，都對(duì)應(yīng)一次磁盤(pán) I/O 操作，也就是說(shuō)樹(shù)的高度就等于每次查詢(xún)數(shù)據(jù)時(shí)磁盤(pán) IO 操作的次數(shù)，所以樹(shù)的高度越高，就會(huì)影響查詢(xún)性能。

B 樹(shù)和 B+ 都是通過(guò)多叉樹(shù)的方式，會(huì)將樹(shù)的高度變矮，所以這兩個(gè)數(shù)據(jù)結(jié)構(gòu)非常適合檢索存于磁盤(pán)中的數(shù)據(jù)。

但是 MySQL 默認(rèn)的存儲(chǔ)引擎 InnoDB 采用的是 B+ 作為索引的數(shù)據(jù)結(jié)構(gòu)。原因有：

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

B+樹(shù)的葉子節(jié)點(diǎn)鏈表是單向還是雙向？

雙向的，為了實(shí)現(xiàn)倒序遍歷或者排序。

圖片

Innodb 使用的 B+ 樹(shù)有一些特別的點(diǎn)，比如：

• B+ 樹(shù)的葉子節(jié)點(diǎn)之間是用「雙向鏈表」進(jìn)行連接，這樣的好處是既能向右遍歷，也能向左遍歷。
• B+ 樹(shù)點(diǎn)節(jié)點(diǎn)內(nèi)容是數(shù)據(jù)頁(yè)，數(shù)據(jù)頁(yè)里存放了用戶(hù)的記錄以及各種信息，每個(gè)數(shù)據(jù)頁(yè)默認(rèn)大小是 16 KB。

Innodb 根據(jù)索引類(lèi)型不同，分為聚集和二級(jí)索引。他們區(qū)別在于，聚集索引的葉子節(jié)點(diǎn)存放的是實(shí)際數(shù)據(jù)，所有完整的用戶(hù)記錄都存放在聚集索引的葉子節(jié)點(diǎn)，而二級(jí)索引的葉子節(jié)點(diǎn)存放的是主鍵值，而不是實(shí)際數(shù)據(jù)。

因?yàn)楸淼臄?shù)據(jù)都是存放在聚集索引的葉子節(jié)點(diǎn)里，所以 InnoDB 存儲(chǔ)引擎一定會(huì)為表創(chuàng)建一個(gè)聚集索引，且由于數(shù)據(jù)在物理上只會(huì)保存一份，所以聚簇索引只能有一個(gè)，而二級(jí)索引可以創(chuàng)建多個(gè)。

MVCC是什么？作用？

MVCC 是多版本并發(fā)控制，MVCC保證了事務(wù)之間的隔離性，事務(wù)只能看到已經(jīng)提交的數(shù)據(jù)版本，從而保證了數(shù)據(jù)的一致性，并且避免了事務(wù)讀寫(xiě)并發(fā)的問(wèn)題，因?yàn)?select 快照讀是不會(huì)加鎖的。

可重復(fù)讀隔離級(jí)別是開(kāi)啟事務(wù)，執(zhí)行第一個(gè) select 查詢(xún)的時(shí)候，會(huì)創(chuàng)建 Read View，然后整個(gè)事務(wù)期間都在用這個(gè) Read View。讀提交隔離級(jí)別是在每次select 查詢(xún)時(shí)，都會(huì)生成一個(gè)新的 Read View。

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

圖片

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

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

• 如果記錄的 trx_id 在 m_ids 列表中，表示生成該版本記錄的活躍事務(wù)依然活躍著（還沒(méi)提交事務(wù)），所以該版本的記錄對(duì)當(dāng)前事務(wù)不可見(jiàn)。
• 如果記錄的 trx_id 不在 m_ids列表中，表示生成該版本記錄的活躍事務(wù)已經(jīng)被提交，所以該版本的記錄對(duì)當(dāng)前事務(wù)可見(jiàn)。

更新是如何保證一致的？

更新屬于當(dāng)前讀，會(huì)加X(jué)型的行級(jí)鎖，是通過(guò)鎖來(lái)保證一致性的。

比如，事務(wù) A 執(zhí)行對(duì)一條 id = 1 的記錄進(jìn)行了更新，其他事務(wù)如果想更新或者刪除這條記錄的話(huà)，會(huì)發(fā)生阻塞，只有當(dāng)事務(wù) a 提交了事務(wù)才會(huì)釋放鎖。

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

事務(wù)執(zhí)行過(guò)程中，執(zhí)行 rollback 語(yǔ)句就能回滾事務(wù)了。

每當(dāng) InnoDB 引擎對(duì)一條記錄進(jìn)行操作（修改、刪除、新增）時(shí)，要把回滾時(shí)需要的信息都記錄到 undo log 里，比如：

• 在插入一條記錄時(shí)，要把這條記錄的主鍵值記下來(lái)，這樣之后回滾時(shí)只需要把這個(gè)主鍵值對(duì)應(yīng)的記錄刪掉就好了；
• 在刪除一條記錄時(shí)，要把這條記錄中的內(nèi)容都記下來(lái)，這樣之后回滾時(shí)再把由這些內(nèi)容組成的記錄插入到表中就好了；
• 在更新一條記錄時(shí)，要把被更新的列的舊值記下來(lái)，這樣之后回滾時(shí)再把這些列更新為舊值就好了。

在發(fā)生回滾時(shí)，就讀取 undo log 里的數(shù)據(jù)，然后做原先相反操作。比如當(dāng) delete 一條記錄時(shí)，undo log 中會(huì)把記錄中的內(nèi)容都記下來(lái)，然后執(zhí)行回滾操作的時(shí)候，就讀取 undo log 里的數(shù)據(jù)，然后進(jìn)行 insert 操作。

如何查詢(xún)慢sql產(chǎn)生的原因?

可以通過(guò)慢查詢(xún)?nèi)罩緛?lái)定位慢 sql 語(yǔ)句。

索引失效的情況有哪些？

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

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

Redis

redis數(shù)據(jù)結(jié)構(gòu)有哪些？

Redis 提供了豐富的數(shù)據(jù)類(lèi)型，常見(jiàn)的有五種數(shù)據(jù)類(lèi)型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

圖片

img

圖片

隨著 Redis 版本的更新，后面又支持了四種數(shù)據(jù)類(lèi)型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五種數(shù)據(jù)類(lèi)型的應(yīng)用場(chǎng)景：

• String 類(lèi)型的應(yīng)用場(chǎng)景：緩存對(duì)象、常規(guī)計(jì)數(shù)、分布式鎖、共享 session 信息等。
• List 類(lèi)型的應(yīng)用場(chǎng)景：消息隊(duì)列（但是有兩個(gè)問(wèn)題：1. 生產(chǎn)者需要自行實(shí)現(xiàn)全局唯一 ID；2. 不能以消費(fèi)組形式消費(fèi)數(shù)據(jù)）等。
• Hash 類(lèi)型：緩存對(duì)象、購(gòu)物車(chē)等。
• Set 類(lèi)型：聚合計(jì)算（并集、交集、差集）場(chǎng)景，比如點(diǎn)贊、共同關(guān)注、抽獎(jiǎng)活動(dòng)等。
• Zset 類(lèi)型：排序場(chǎng)景，比如排行榜、電話(huà)和姓名排序等。

Redis 后續(xù)版本又支持四種數(shù)據(jù)類(lèi)型，它們的應(yīng)用場(chǎng)景如下：

• BitMap（2.2 版新增）：二值狀態(tài)統(tǒng)計(jì)的場(chǎng)景，比如簽到、判斷用戶(hù)登陸狀態(tài)、連續(xù)簽到用戶(hù)總數(shù)等；
• HyperLogLog（2.8 版新增）：海量數(shù)據(jù)基數(shù)統(tǒng)計(jì)的場(chǎng)景，比如百萬(wàn)級(jí)網(wǎng)頁(yè) UV 計(jì)數(shù)等；
• GEO（3.2 版新增）：存儲(chǔ)地理位置信息的場(chǎng)景，比如滴滴叫車(chē)；
• Stream（5.0 版新增）：消息隊(duì)列，相比于基于 List 類(lèi)型實(shí)現(xiàn)的消息隊(duì)列，有這兩個(gè)特有的特性：自動(dòng)生成全局唯一消息ID，支持以消費(fèi)組形式消費(fèi)數(shù)據(jù)。

zset 是怎么實(shí)現(xiàn)的？

Zset 類(lèi)型的底層數(shù)據(jù)結(jié)構(gòu)是由壓縮列表或跳表實(shí)現(xiàn)的：

• 如果有序集合的元素個(gè)數(shù)小于 128 個(gè)，并且每個(gè)元素的值小于 64 字節(jié)時(shí)，Redis 會(huì)使用壓縮列表作為 Zset 類(lèi)型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果有序集合的元素不滿(mǎn)足上面的條件，Redis 會(huì)使用跳表作為 Zset 類(lèi)型的底層數(shù)據(jù)結(jié)構(gòu)，并且還會(huì)使用哈希表。

在 Redis 7.0 中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)了。

為什么數(shù)據(jù)量小的時(shí)候用壓縮列表？

因?yàn)閴嚎s列表一種內(nèi)存緊湊的數(shù)據(jù)結(jié)構(gòu)，可以節(jié)約內(nèi)存。

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開(kāi)發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)類(lèi)似于數(shù)組。

圖片

壓縮列表在表頭有三個(gè)字段：

• zlbytes，記錄整個(gè)壓縮列表占用對(duì)內(nèi)存字節(jié)數(shù)；
• zltail，記錄壓縮列表「尾部」節(jié)點(diǎn)距離起始地址由多少字節(jié)，也就是列表尾的偏移量；
• zllen，記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量；
• zlend，標(biāo)記壓縮列表的結(jié)束點(diǎn)，固定值 0xFF（十進(jìn)制255）。

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

另外，壓縮列表節(jié)點(diǎn)（entry）的構(gòu)成如下：

圖片

壓縮列表節(jié)點(diǎn)包含三部分內(nèi)容：

• prevlen，記錄了「前一個(gè)節(jié)點(diǎn)」的長(zhǎng)度，目的是為了實(shí)現(xiàn)從后向前遍歷；
• encoding，記錄了當(dāng)前節(jié)點(diǎn)實(shí)際數(shù)據(jù)的「類(lèi)型和長(zhǎng)度」，類(lèi)型主要有兩種：字符串和整數(shù)。
• data，記錄了當(dāng)前節(jié)點(diǎn)的實(shí)際數(shù)據(jù)，類(lèi)型和長(zhǎng)度都由 encoding 決定；

當(dāng)我們往壓縮列表中插入數(shù)據(jù)時(shí)，壓縮列表就會(huì)根據(jù)數(shù)據(jù)類(lèi)型是字符串還是整數(shù)，以及數(shù)據(jù)的大小，會(huì)使用不同空間大小的 prevlen 和 encoding 這兩個(gè)元素里保存的信息，這種根據(jù)數(shù)據(jù)大小和類(lèi)型進(jìn)行不同的空間大小分配的設(shè)計(jì)思想，正是 Redis 為了節(jié)省內(nèi)存而采用的。

壓縮列表和跳躍表的區(qū)別？

• 存儲(chǔ)方式區(qū)別：壓縮列表是一種緊湊的線(xiàn)性連續(xù)存儲(chǔ)結(jié)構(gòu)，通過(guò)將多個(gè)元素依次存儲(chǔ)在一塊連續(xù)的內(nèi)存中，節(jié)省了內(nèi)存空間。而跳躍表則是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，通過(guò)多層次的索引結(jié)構(gòu)（跳躍層）來(lái)加速查找。
• 時(shí)間復(fù)雜度區(qū)別：在讀取或修改操作方面，壓縮列表的時(shí)間復(fù)雜度為O(n)，其中n是元素?cái)?shù)量。因?yàn)閴嚎s列表需要線(xiàn)性?huà)呙鑱?lái)定位元素。而跳躍表的讀取或修改操作的時(shí)間復(fù)雜度為O(log n)，通過(guò)跳躍層和鏈表的結(jié)構(gòu)，可以快速定位到目標(biāo)元素。
• 內(nèi)存占用區(qū)別：壓縮列表具有較小的內(nèi)存占用，對(duì)于較小的有序集合，可以更節(jié)省內(nèi)存空間。而跳躍表則需要更多的內(nèi)存空間來(lái)存儲(chǔ)索引結(jié)構(gòu)，因此在空間占用方面相對(duì)較大。

redis主從復(fù)制的過(guò)程？

第一次同步的過(guò)程如下：

圖片

• 第一階段是建立鏈接、協(xié)商同步；
• 第二階段是主服務(wù)器同步數(shù)據(jù)給從服務(wù)器；
• 第三階段是主服務(wù)器發(fā)送新寫(xiě)操作命令給從服務(wù)器

主從服務(wù)器在完成第一次同步后，就會(huì)基于長(zhǎng)連接進(jìn)行命令傳播。

圖片

后續(xù)主服務(wù)器可以通過(guò)這個(gè)連接繼續(xù)將寫(xiě)操作命令傳播給從服務(wù)器，然后從服務(wù)器執(zhí)行該命令，使得與主服務(wù)器的數(shù)據(jù)庫(kù)狀態(tài)相同。

通過(guò)什么復(fù)制？

全量復(fù)制階段是復(fù)制 rdb 文件。

增量復(fù)制命令存在哪里？

存放在 repl_backlog_buffer  緩沖區(qū)，在主服務(wù)器進(jìn)行命令傳播時(shí)，不僅會(huì)將寫(xiě)命令發(fā)送給從服務(wù)器，還會(huì)將寫(xiě)命令寫(xiě)入到 repl_backlog_buffer 緩沖區(qū)里，因此 這個(gè)緩沖區(qū)里會(huì)保存著最近傳播的寫(xiě)命令。

圖片

RDB、AOF優(yōu)缺點(diǎn)有哪些？

• RDB 是一個(gè)緊湊的二進(jìn)制文件，相對(duì)較小，可以節(jié)省磁盤(pán)空間。。AOF文件是一個(gè)文本文件，記錄了每個(gè)寫(xiě)操作，因此相對(duì)于RDB文件來(lái)說(shuō)，AOF文件更大，因此RDB 在恢復(fù)大數(shù)據(jù)集時(shí)的速度比AOF 的恢復(fù)速度要快。
• Rob 的缺陷在于數(shù)據(jù)丟失的風(fēng)險(xiǎn)更大，如果Redis在最后一次快照之后發(fā)生故障，可能會(huì)丟失一部分?jǐn)?shù)據(jù)。而 AOF以日志的方式記錄每個(gè)寫(xiě)操作，數(shù)據(jù)的安全性會(huì)更高。

linux

ps命令里都有哪些選項(xiàng)，ps展示哪些東西？

圖片

ps命令展示內(nèi)容：

• PID：進(jìn)程ID。
• PPID：父進(jìn)程ID。
• USER：進(jìn)程所屬用戶(hù)。
• %CPU：CPU占用率。
• %MEM：內(nèi)存占用率。
• VSZ：虛擬內(nèi)存大小。
• RSS：物理內(nèi)存大小。
• TTY：終端設(shè)備。
• STAT：進(jìn)程狀態(tài)。
• START：進(jìn)程啟動(dòng)時(shí)間。
• TIME：進(jìn)程累計(jì)CPU占用時(shí)間。
• COMMAND：進(jìn)程命令或可執(zhí)行文件。

ps命令選項(xiàng)：

• -a：顯示所有進(jìn)程，包括其他用戶(hù)的進(jìn)程。
• -u：顯示用戶(hù)相關(guān)的進(jìn)程信息。
• -x：顯示沒(méi)有控制終端的進(jìn)程。
• -e：顯示所有進(jìn)程，等同于-a選項(xiàng)。
• -f：顯示詳細(xì)的進(jìn)程信息，包括進(jìn)程的父進(jìn)程、運(yùn)行狀態(tài)等。
• -l：顯示長(zhǎng)格式的進(jìn)程信息，包括進(jìn)程的PID、PPID、CPU占用率等。
• -r：顯示正在運(yùn)行的進(jìn)程。
• -o：自定義輸出格式。

圖片

主要會(huì)展示：

• Load average（平均負(fù)載）：顯示系統(tǒng)在最近1分鐘、5分鐘和15分鐘內(nèi)的平均負(fù)載情況。
• Tasks（任務(wù)）：顯示當(dāng)前運(yùn)行、睡眠、停止和僵尸狀態(tài)的進(jìn)程數(shù)量。
• CPU usage（CPU使用情況）：顯示CPU的總體使用率以及每個(gè)CPU核心的使用率。
• Memory usage（內(nèi)存使用情況）：顯示物理內(nèi)存的總量、已使用量、空閑量、緩沖區(qū)和緩存區(qū)的使用量。
• Swap usage（交換空間使用情況）：顯示交換空間的總量、已使用量和剩余量。
• 進(jìn)程列表：顯示當(dāng)前運(yùn)行的進(jìn)程列表，包括進(jìn)程的PID、用戶(hù)、CPU占用率、內(nèi)存占用率、進(jìn)程狀態(tài)、啟動(dòng)時(shí)間和進(jìn)程命令。

算法題

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

其他

• 實(shí)習(xí)項(xiàng)目介紹
• 通過(guò)什么方式學(xué)習(xí)