圖解學(xué)習(xí)網(wǎng)站： xiaolincoding.com

大家好，我是小林。

校招生通常都是一張白紙，所以校招面試過程中，面試官通常都會(huì)比較傾向問一些基礎(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)，從常見的數(shù)據(jù)結(jié)構(gòu)->Java 集合>MySQL B+樹->Redis 數(shù)據(jù)結(jié)構(gòu)。所以，這是一場比較重基礎(chǔ)的后端面試，問題也比較多，面試時(shí)長超過 1 小時(shí)了，還挺艱難的。

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

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

LRU 是一種緩存淘汰算法，當(dāng)緩存空間已滿時(shí)，優(yōu)先淘汰最長時(shí)間未被訪問的數(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)，鏈表頭部為最近訪問的節(jié)點(diǎn)，鏈表尾部為最久未訪問的節(jié)點(diǎn)。

• 當(dāng)數(shù)據(jù)被訪問時(shí)，如果數(shù)據(jù)存在于緩存中，則將對(duì)應(yīng)節(jié)點(diǎn)移動(dòng)到鏈表頭部；如果數(shù)據(jù)不存在于緩存中，則將數(shù)據(jù)添加到緩存中，同時(shí)創(chuàng)建一個(gè)新節(jié)點(diǎn)并插入到鏈表頭部。

• 當(dāng)緩存空間已滿時(shí)，需要淘汰最久未訪問的節(jié)點(diǎn)，即鏈表尾部的節(jié)點(diǎn)。

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

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

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

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

img

分析：

• 圖一是一個(gè)平衡二叉樹，它滿足平衡二叉樹的定義。

• 圖二不是平衡二叉樹，其原因并不是不滿足平衡因子的條件，而是因?yàn)樗粷M足二叉搜索樹的構(gòu)成條件，這提醒我們平衡二叉樹首先要是一棵二叉搜索樹。

• 圖三滿足平衡二叉樹的構(gòu)成條件。

• 圖 4 中的節(jié)點(diǎn) (8) 平衡因子為 3，不滿足平衡二叉樹的要求。

堆是什么？

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

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

img

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

What is Stack and Queue

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

Java

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

img

存儲(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)整容量(超過Load Facotr則resize為原來的2倍)。

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

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

擴(kuò)容分為2步：

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

因?yàn)槲覀兪褂玫氖?次冪的擴(kuò)展(指長度擴(kuò)為原來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，只需要看看原來的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”?？梢钥纯聪聢D為16擴(kuò)充為32的resize示意圖：

resize16-32

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

HashMap  為什么線程不安全？

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

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

CurrentHashMap 怎么保證線程安全的？

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

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

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

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

MySQL

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

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

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

MySQL為什么使用B+ 樹？

MySQL 是會(huì)將數(shù)據(jù)持久化在硬盤，而存儲(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ù)據(jù)結(jié)構(gòu)。

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

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

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

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

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

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

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

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

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

圖片

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

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

Innodb 根據(jù)索引類型不同，分為聚集和二級(jí)索引。他們區(qū)別在于，聚集索引的葉子節(jié)點(diǎn)存放的是實(shí)際數(shù)據(jù)，所有完整的用戶記錄都存放在聚集索引的葉子節(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ù)讀寫并發(fā)的問題，因?yàn)?select 快照讀是不會(huì)加鎖的。

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

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

img

一個(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ù)可見。

更新是如何保證一致的？

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

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

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

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

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

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

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

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

可以通過慢查詢?nèi)罩緛矶ㄎ宦?sql 語句。

索引失效的情況有哪些？

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ì)失效。

Redis

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

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

img img

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

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

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

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

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

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

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

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

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

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

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

img

壓縮列表在表頭有三個(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è)元素，可以通過表頭三個(gè)字段（zllen）的長度直接定位，復(fù)雜度是 O(1)。而查找其他元素時(shí)，就沒有這么高效了，只能逐個(gè)查找，此時(shí)的復(fù)雜度就是 O(N) 了，因此壓縮列表不適合保存過多的元素。

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

img

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

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

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

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

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

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

第一次同步的過程如下：

圖片

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

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

圖片

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

通過什么復(fù)制？

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

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

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

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

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

linux

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

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

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

top命令會(huì)展示什么東西，里面每一項(xiàng)都是呈現(xiàn)什么樣的數(shù)據(jù)？

主要會(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、用戶、CPU占用率、內(nèi)存占用率、進(jìn)程狀態(tài)、啟動(dòng)時(shí)間和進(jìn)程命令。

算法題

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

其他

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

歷史好文： 我們又出成績了?。?/a>
還是銀行面試舒服些...
百度提前批，有點(diǎn)難度！
終于字節(jié)約面，可惜沒把握住....