大家好，我是小林。

今天來分析字節(jié)跳動校招后端開發(fā)面經(jīng)，同學的技術(shù)棧是 Java 后端，問八股文比較多，一共經(jīng)歷了一二三面，每一場面試的強度還是蠻高，每次都是 1 個小時+。

我把這幾場面試中比較有代表性的題目抽離出來給大家解析一波，給準備春招的同學做一個參考和學習，雖然是校招的面試，但是有些問題，其實社招也經(jīng)常問的。

知識一學就忘原因，就是缺少溫故的過程，通過面試題的方式回顧系列的知識，也是一種高效的方式。

這次面經(jīng)的考點，我簡單羅列一下：

• 操作系統(tǒng)：進程調(diào)度
• 網(wǎng)絡(luò)：HTTP、HTTPS
• Java：線程狀態(tài)、多線程、volatile、synchronized
• Redis：數(shù)據(jù)結(jié)構(gòu)、跳表、性能、場景應(yīng)用、緩存一致性
• MySQL：事務(wù)、隔離級別、日志、索引、間隙鎖、最左匹配原則
• 算法：每一輪 1 個算法

Redis

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

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

圖片

圖片

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

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

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

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

Zset 使用了什么數(shù)據(jù)結(jié)構(gòu)？

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

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

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

SkipList 了解嗎？

鏈表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進過來的，實現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長什么樣呢？我這里舉個例子，下圖展示了一個層級為 3 的跳表。

圖片

圖中頭節(jié)點有 L0~L2 三個頭指針，分別指向了不同層級的節(jié)點，然后每個層級的節(jié)點都通過指針連接起來：

• L0 層級共有 5 個節(jié)點，分別是節(jié)點1、2、3、4、5；
• L1 層級共有 3 個節(jié)點，分別是節(jié)點 2、3、5；
• L2 層級只有 1 個節(jié)點，也就是節(jié)點 3 。

如果我們要在鏈表中查找節(jié)點 4 這個元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點 4，因為可以在頭節(jié)點直接從 L2 層級跳到節(jié)點 3，然后再往前遍歷找到節(jié)點 4。

可以看到，這個查找過程就是在多個層級上跳來跳去，最后定位到元素。當數(shù)據(jù)量很大時，跳表的查找復(fù)雜度就是 O(logN)。

跳表的時間復(fù)雜度是多少？

跳表中查找一個元素的時間復(fù)雜度為O(logn)，空間復(fù)雜度是 O(n)。

為什么 MysSQL 不用 SkipList？

B+樹的高度在3層時存儲的數(shù)據(jù)可能已達千萬級別，但對于跳表而言同樣去維護千萬的數(shù)據(jù)量那么所造成的跳表層數(shù)過高而導致的磁盤io次數(shù)增多，也就是使用B+樹在存儲同樣的數(shù)據(jù)下磁盤io次數(shù)更少。

Redis 使用場景?

Redis 是一種基于內(nèi)存的數(shù)據(jù)庫，對數(shù)據(jù)的讀寫操作都是在內(nèi)存中完成，因此讀寫速度非?？欤Ｓ糜诰彺?，消息隊列、分布式鎖等場景。

圖片

Redis用途

Redis 提供了多種數(shù)據(jù)類型來支持不同的業(yè)務(wù)場景，比如 String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合)、Bitmaps（位圖）、HyperLogLog（基數(shù)統(tǒng)計）、GEO（地理信息）、Stream（流），并且對數(shù)據(jù)類型的操作都是原子性的，因為執(zhí)行命令由單線程負責的，不存在并發(fā)競爭的問題。

除此之外，Redis 還支持事務(wù) 、持久化、Lua 腳本、多種集群方案（主從復(fù)制模式、哨兵模式、切片機群模式）、發(fā)布/訂閱模式，內(nèi)存淘汰機制、過期刪除機制等等。

Redis 性能好的原因是什么？

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

圖片

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

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

Redis 和 MySQL 如何保證一致性

可以采用「先更新數(shù)據(jù)庫，再刪除緩存」的更新策略+過期時間來兜底。

我們用「讀 + 寫」請求的并發(fā)的場景來分析。

假如某個用戶數(shù)據(jù)在緩存中不存在，請求 A 讀取數(shù)據(jù)時從數(shù)據(jù)庫中查詢到年齡為 20，在未寫入緩存中時另一個請求 B 更新數(shù)據(jù)。它更新數(shù)據(jù)庫中的年齡為 21，并且清空緩存。這時請求 A 把從數(shù)據(jù)庫中讀到的年齡為 20 的數(shù)據(jù)寫入到緩存中。

圖片

最終，該用戶年齡在緩存中是 20（舊值），在數(shù)據(jù)庫中是 21（新值），緩存和數(shù)據(jù)庫數(shù)據(jù)不一致。

從上面的理論上分析，先更新數(shù)據(jù)庫，再刪除緩存也是會出現(xiàn)數(shù)據(jù)不一致性的問題，但是在實際中，這個問題出現(xiàn)的概率并不高。

因為緩存的寫入通常要遠遠快于數(shù)據(jù)庫的寫入，所以在實際中很難出現(xiàn)請求 B 已經(jīng)更新了數(shù)據(jù)庫并且刪除了緩存，請求 A 才更新完緩存的情況。

而一旦請求 A 早于請求 B 刪除緩存之前更新了緩存，那么接下來的請求就會因為緩存不命中而從數(shù)據(jù)庫中重新讀取數(shù)據(jù)，所以不會出現(xiàn)這種不一致的情況。

所以，「先更新數(shù)據(jù)庫 + 再刪除緩存」的方案，是可以保證數(shù)據(jù)一致性的。

而且為了確保萬無一失，還給緩存數(shù)據(jù)加上了「過期時間」，就算在這期間存在緩存數(shù)據(jù)不一致，有過期時間來兜底，這樣也能達到最終一致。

MySQL

事務(wù)有哪些特性?

事務(wù) 4 個特性，分別如下：

• 原子性（Atomicity）：一個事務(wù)中的所有操作，要么全部完成，要么全部不完成，不會結(jié)束在中間某個環(huán)節(jié)，而且事務(wù)在執(zhí)行過程中發(fā)生錯誤，會被回滾到事務(wù)開始前的狀態(tài)，就像這個事務(wù)從來沒有執(zhí)行過一樣，就好比買一件商品，購買成功時，則給商家付了錢，商品到手；購買失敗時，則商品在商家手中，消費者的錢也沒花出去。
• 一致性（Consistency）：是指事務(wù)操作前和操作后，數(shù)據(jù)滿足完整性約束，數(shù)據(jù)庫保持一致性狀態(tài)。比如，用戶 A 和用戶 B 在銀行分別有 800 元和 600 元，總共 1400 元，用戶 A 給用戶 B 轉(zhuǎn)賬 200 元，分為兩個步驟，從 A 的賬戶扣除 200 元和對 B 的賬戶增加 200 元。一致性就是要求上述步驟操作后，最后的結(jié)果是用戶 A 還有 600 元，用戶 B 有 800 元，總共 1400 元，而不會出現(xiàn)用戶 A 扣除了 200 元，但用戶 B 未增加的情況（該情況，用戶 A 和 B 均為 600 元，總共 1200 元）。
• 隔離性（Isolation）：數(shù)據(jù)庫允許多個并發(fā)事務(wù)同時對其數(shù)據(jù)進行讀寫和修改的能力，隔離性可以防止多個事務(wù)并發(fā)執(zhí)行時由于交叉執(zhí)行而導致數(shù)據(jù)的不一致，因為多個事務(wù)同時使用相同的數(shù)據(jù)時，不會相互干擾，每個事務(wù)都有一個完整的數(shù)據(jù)空間，對其他并發(fā)事務(wù)是隔離的。也就是說，消費者購買商品這個事務(wù)，是不影響其他消費者購買的。
• 持久性（Durability）：事務(wù)處理結(jié)束后，對數(shù)據(jù)的修改就是永久的，即便系統(tǒng)故障也不會丟失。

隔離性有哪些隔離級別?

四個隔離級別如下：

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

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

圖片

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

圖片

也就是說：

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

MySQL 默認用的哪個級別?

MySQL 默認隔離級別是「可重復(fù)讀」，可以很大程度上避免幻讀現(xiàn)象的發(fā)生（注意是很大程度避免，并不是徹底避免），所以 MySQL 并不會使用「串行化」隔離級別來避免幻讀現(xiàn)象的發(fā)生，因為使用「串行化」隔離級別會影響性能。

間隙鎖的原理

Gap Lock 稱為間隙鎖，只存在于可重復(fù)讀隔離級別，目的是為了解決可重復(fù)讀隔離級別下幻讀的現(xiàn)象。

假設(shè)，表中有一個范圍 id 為（3，5）間隙鎖，那么其他事務(wù)就無法插入 id = 4 這條記錄了，這樣就有效的防止幻讀現(xiàn)象的發(fā)生。

img

間隙鎖雖然存在 X 型間隙鎖和 S 型間隙鎖，但是并沒有什么區(qū)別，間隙鎖之間是兼容的，即兩個事務(wù)可以同時持有包含共同間隙范圍的間隙鎖，并不存在互斥關(guān)系，因為間隙鎖的目的是防止插入幻影記錄而提出的。

什么時候會加間隙鎖?

當我們用唯一索引進行等值查詢的時候，查詢的記錄不存在的時候，在索引樹找到第一條大于該查詢記錄的記錄后，將該記錄的索引中的 next-key lock 會退化成「間隙鎖」。

假設(shè)事務(wù) A 執(zhí)行了這條等值查詢語句，查詢的記錄是「不存在」于表中的。

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from user where id = 2 for update;
Empty set (0.03 sec)

接下來，通過 select * from performance_schema.data_locks\G; 這條語句，查看事務(wù)執(zhí)行 SQL 過程中加了什么鎖。

圖片

從上圖可以看到，共加了兩個鎖，分別是：

• 表鎖：X 類型的意向鎖；
• 行鎖：X 類型的間隙鎖；

因此，此時事務(wù) A 在 id = 5 記錄的主鍵索引上加的是間隙鎖，鎖住的范圍是 (1, 5)。

圖片

接下來，如果有其他事務(wù)插入 id 值為 2、3、4 這一些記錄的話，這些插入語句都會發(fā)生阻塞。

注意，如果其他事務(wù)插入的 id = 1 或者 id = 5 的記錄話，并不會發(fā)生阻塞，而是報主鍵沖突的錯誤，因為表中已經(jīng)存在 id = 1 和 id = 5 的記錄了。

比如，下面這個例子：

img

因為事務(wù) A 在 id = 5 記錄的主鍵索引上加了范圍為 (1, 5) 的 X 型間隙鎖，所以事務(wù) B 在插入一條 id 為 3 的記錄時會被阻塞住，即無法插入 id = 3 的記錄。

MySQL 如何保證原子性?

通過 undo log 來保證原子性的。

undo log 是一種用于撤銷回退的日志。在事務(wù)沒提交之前，MySQL 會先記錄更新前的數(shù)據(jù)到 undo log 日志文件里面，當事務(wù)回滾時，可以利用 undo log 來進行回滾。如下圖：

回滾事務(wù)

undo log 撤銷過程具體是怎么撤銷的?

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

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

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

怎么決定建立哪些索引?

什么時候適用索引？

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

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

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

最左匹配是什么，舉個例子？

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

比如，如果創(chuàng)建了一個 (a, b, c) 聯(lián)合索引，如果查詢條件是以下這幾種，就可以匹配上聯(lián)合索引：

• where a=1；
• where a=1 and b=2 and c=3；
• where a=1 and b=2；

需要注意的是，因為有查詢優(yōu)化器，所以 a 字段在 where 子句的順序并不重要。

但是，如果查詢條件是以下這幾種，因為不符合最左匹配原則，所以就無法匹配上聯(lián)合索引，聯(lián)合索引就會失效:

• where b=2；
• where c=3；
• where b=2 and c=3；

上面這些查詢條件之所以會失效，是因為(a, b, c) 聯(lián)合索引，是先按 a 排序，在 a 相同的情況再按 b 排序，在 b 相同的情況再按 c 排序。所以，b 和 c 是全局無序，局部相對有序的，這樣在沒有遵循最左匹配原則的情況下，是無法利用到索引的。

我這里舉聯(lián)合索引（a，b）的例子，該聯(lián)合索引的 B+ Tree 如下（圖中葉子節(jié)點之間我畫了單向鏈表，但是實際上是雙向鏈表，原圖我找不到了，修改不了，偷個懶我不重畫了，大家腦補成雙向鏈表就行）。

可以看到，a 是全局有序的（1, 2, 2, 3, 4, 5, 6, 7 ,8），而 b 是全局是無序的（12，7，8，2，3，8，10，5，2）。因此，直接執(zhí)行where b = 2這種查詢條件沒有辦法利用聯(lián)合索引的，利用索引的前提是索引里的 key 是有序的。

只有在 a 相同的情況才，b 才是有序的，比如 a 等于 2 的時候，b 的值為（7，8），這時就是有序的，這個有序狀態(tài)是局部的，因此，執(zhí)行where a = 2 and b = 7是 a 和 b 字段能用到聯(lián)合索引的，也就是聯(lián)合索引生效了。

Java

Java 里面線程有哪些狀態(tài)?

源自《Java并發(fā)編程藝術(shù)》

java.lang.Thread.State枚舉類中定義了六種線程的狀態(tài)，可以調(diào)用線程Thread中的getState()方法獲取當前線程的狀態(tài)。

wait 狀態(tài)下的線程如何進行恢復(fù)到 running 狀態(tài)?

• 等待的線程被其他線程對象喚醒，notify()和notifyAll()。
• 如果線程沒有獲取到鎖則會直接進入 Waiting 狀態(tài)，其實這種本質(zhì)上它就是執(zhí)行了 LockSupport.park() 方法進入了Waiting 狀態(tài)，那么解鎖的時候會執(zhí)行LockSupport.unpark(Thread)，與上面park方法對應(yīng)，給出許可證，解除等待狀態(tài)。

notify 和 notifyAll 的區(qū)別?

同樣是喚醒等待的線程，同樣最多只有一個線程能獲得鎖，同樣不能控制哪個線程獲得鎖。

區(qū)別在于：

• notify：喚醒一個線程，其他線程依然處于wait的等待喚醒狀態(tài)，如果被喚醒的線程結(jié)束時沒調(diào)用notify，其他線程就永遠沒人去喚醒，只能等待超時，或者被中斷
• notifyAll：所有線程退出wait的狀態(tài)，開始競爭鎖，但只有一個線程能搶到，這個線程執(zhí)行完后，其他線程又會有一個幸運兒脫穎而出得到鎖

notify 選擇哪個線程?

notify在源碼的注釋中說到notify選擇喚醒的線程是任意的，但是依賴于具體實現(xiàn)的jvm。

圖片

notify源碼

JVM有很多實現(xiàn)，比較流行的就是hotspot，hotspot對notofy()的實現(xiàn)并不是我們以為的隨機喚醒,，而是“先進先出”的順序喚醒。

如何停止一個線程的運行?

主要有這些方法：

• 異常法停止：線程調(diào)用interrupt()方法后，在線程的run方法中判斷當前對象的interrupted()狀態(tài)，如果是中斷狀態(tài)則拋出異常，達到中斷線程的效果。
• 在沉睡中停止：先將線程sleep，然后調(diào)用interrupt標記中斷狀態(tài)，interrupt會將阻塞狀態(tài)的線程中斷。會拋出中斷異常，達到停止線程的效果
• stop()暴力停止：線程調(diào)用stop()方法會被暴力停止，方法已棄用，該方法會有不好的后果：強制讓線程停止有可能使一些請理性的工作得不到完成。
• 使用return停止線程：調(diào)用interrupt標記為中斷狀態(tài)后，在run方法中判斷當前線程狀態(tài)，如果為中斷狀態(tài)則return，能達到停止線程的效果。

調(diào)用 interrupt 是如何讓線程拋出異常的?

每個線程都一個與之關(guān)聯(lián)的布爾屬性來表示其中斷狀態(tài)，中斷狀態(tài)的初始值為false，當一個線程被其它線程調(diào)用Thread.interrupt()方法中斷時，會根據(jù)實際情況做出響應(yīng)。

• 如果該線程正在執(zhí)行低級別的可中斷方法（如Thread.sleep()、Thread.join()或Object.wait()），則會解除阻塞并拋出InterruptedException異常。
• 否則Thread.interrupt()僅設(shè)置線程的中斷狀態(tài)，在該被中斷的線程中稍后可通過輪詢中斷狀態(tài)來決定是否要停止當前正在執(zhí)行的任務(wù)。

如果是靠變量來停止線程，缺點是什么?

缺點是中斷可能不夠及時，循環(huán)判斷時會到下一個循環(huán)才能判斷出來。

class InterruptFlag {
  // 自定義的中斷標識符
  private static volatile boolean isInterrupt = false;

  public static void main(String[] args) throws InterruptedException {
    // 創(chuàng)建可中斷的線程實例
    Thread thread = new Thread(() -> {
      while (!isInterrupt) { // 如果 isInterrupt=true 則停止線程
        System.out.println("thread 執(zhí)行步驟1：線程即將進入休眠狀態(tài)");
        try {
          // 休眠 1s
          Thread.sleep(1000);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
        System.out.println("thread 執(zhí)行步驟2：線程執(zhí)行了任務(wù)");
      }
    });
    
    thread.start(); // 啟動線程
    // 休眠 100ms，等待 thread 線程運行起來
    Thread.sleep(100);
    System.out.println("主線程：試圖終止線程 thread");
    // 修改中斷標識符，中斷線程
    isInterrupt = true;
  }
}

當終止線程后，執(zhí)行步驟2依然會被執(zhí)行，這就是缺點。

volatile 保證原子性嗎？

volatile關(guān)鍵字并沒有保證我們的變量的原子性，volatile是Java虛擬機提供的一種輕量級的同步機制，主要有這三個特性：

• 保證可見性
• 不保證原子性
• 禁止指令重排

那我們要如何保證原子性?

可以通過synchronized來保證原子性。

synchronized 支持重入嗎？如何實現(xiàn)的?

synchronized是基于原子性的內(nèi)部鎖機制，是可重入的，因此在一個線程調(diào)用synchronized方法的同時在其方法體內(nèi)部調(diào)用該對象另一個synchronized方法，也就是說一個線程得到一個對象鎖后再次請求該對象鎖，是允許的，這就是synchronized的可重入性。

synchronized底層是利用計算機系統(tǒng)mutex Lock實現(xiàn)的。每一個可重入鎖都會關(guān)聯(lián)一個線程ID和一個鎖狀態(tài)status。

當一個線程請求方法時，會去檢查鎖狀態(tài)。

1. 如果鎖狀態(tài)是0，代表該鎖沒有被占用，使用CAS操作獲取鎖，將線程ID替換成自己的線程ID。
2. 如果鎖狀態(tài)不是0，代表有線程在訪問該方法。此時，如果線程ID是自己的線程ID，如果是可重入鎖，會將status自增1，然后獲取到該鎖，進而執(zhí)行相應(yīng)的方法；如果是非重入鎖，就會進入阻塞隊列等待。

在釋放鎖時，

1. 如果是可重入鎖的，每一次退出方法，就會將status減1，直至status的值為0，最后釋放該鎖。
2. 如果非可重入鎖的，線程退出方法，直接就會釋放該鎖。

網(wǎng)絡(luò)

HTTP 與 HTTPS 協(xié)議的區(qū)別？

HTTP 與 HTTPS 網(wǎng)絡(luò)層

• HTTP 是超文本傳輸協(xié)議，信息是明文傳輸，存在安全風險的問題。HTTPS 則解決 HTTP 不安全的缺陷，在 TCP 和 HTTP 網(wǎng)絡(luò)層之間加入了 SSL/TLS 安全協(xié)議，使得報文能夠加密傳輸。
• HTTP 連接建立相對簡單， TCP 三次握手之后便可進行 HTTP 的報文傳輸。而 HTTPS 在 TCP 三次握手之后，還需進行 SSL/TLS 的握手過程，才可進入加密報文傳輸。
• 兩者的默認端口不一樣，HTTP 默認端口號是 80，HTTPS 默認端口號是 443。
• HTTPS 協(xié)議需要向 CA（證書權(quán)威機構(gòu)）申請數(shù)字證書，來保證服務(wù)器的身份是可信的。

操作系統(tǒng)

有哪些進程調(diào)度算法 ?

01 先來先服務(wù)調(diào)度算法

最簡單的一個調(diào)度算法，就是非搶占式的先來先服務(wù)（*First Come First Serve, FCFS*）算法了。

FCFS 調(diào)度算法

顧名思義，先來后到，每次從就緒隊列選擇最先進入隊列的進程，然后一直運行，直到進程退出或被阻塞，才會繼續(xù)從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業(yè)先運行了，那么后面的短作業(yè)等待的時間就會很長，不利于短作業(yè)。

FCFS 對長作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

02 最短作業(yè)優(yōu)先調(diào)度算法

最短作業(yè)優(yōu)先（*Shortest Job First, SJF*）調(diào)度算法同樣也是顧名思義，它會優(yōu)先選擇運行時間最短的進程來運行，這有助于提高系統(tǒng)的吞吐量。

SJF 調(diào)度算法

這顯然對長作業(yè)不利，很容易造成一種極端現(xiàn)象。

比如，一個長作業(yè)在就緒隊列等待運行，而這個就緒隊列有非常多的短作業(yè)，那么就會使得長作業(yè)不斷的往后推，周轉(zhuǎn)時間變長，致使長作業(yè)長期不會被運行。

03 高響應(yīng)比優(yōu)先調(diào)度算法

前面的「先來先服務(wù)調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒有很好的權(quán)衡短作業(yè)和長作業(yè)。

那么，高響應(yīng)比優(yōu)先 （*Highest Response Ratio Next, HRRN*）調(diào)度算法主要是權(quán)衡了短作業(yè)和長作業(yè)。

每次進行進程調(diào)度時，先計算「響應(yīng)比優(yōu)先級」，然后把「響應(yīng)比優(yōu)先級」最高的進程投入運行，「響應(yīng)比優(yōu)先級」的計算公式：

圖片

從上面的公式，可以發(fā)現(xiàn)：

• 如果兩個進程的「等待時間」相同時，「要求的服務(wù)時間」越短，「響應(yīng)比」就越高，這樣短作業(yè)的進程容易被選中運行；
• 如果兩個進程「要求的服務(wù)時間」相同時，「等待時間」越長，「響應(yīng)比」就越高，這就兼顧到了長作業(yè)進程，因為進程的響應(yīng)比可以隨時間等待的增加而提高，當其等待時間足夠長時，其響應(yīng)比便可以升到很高，從而獲得運行的機會；

04 時間片輪轉(zhuǎn)調(diào)度算法

最古老、最簡單、最公平且使用最廣的算法就是時間片輪轉(zhuǎn)（*Round Robin, RR*）調(diào)度算法。

RR 調(diào)度算法

每個進程被分配一個時間段，稱為時間片（*Quantum*），即允許該進程在該時間段中運行。

• 如果時間片用完，進程還在運行，那么將會把此進程從 CPU 釋放出來，并把 CPU 分配給另外一個進程；
• 如果該進程在時間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進行切換；

另外，時間片的長度就是一個很關(guān)鍵的點：

• 如果時間片設(shè)得太短會導致過多的進程上下文切換，降低了 CPU 效率；
• 如果設(shè)得太長又可能引起對短作業(yè)進程的響應(yīng)時間變長。將

一般來說，時間片設(shè)為 20ms~50ms 通常是一個比較合理的折中值。

05 最高優(yōu)先級調(diào)度算法

前面的「時間片輪轉(zhuǎn)算法」做了個假設(shè)，即讓所有的進程同等重要，也不偏袒誰，大家的運行時間都一樣。

但是，對于多用戶計算機系統(tǒng)就有不同的看法了，它們希望調(diào)度是有優(yōu)先級的，即希望調(diào)度程序能從就緒隊列中選擇最高優(yōu)先級的進程進行運行，這稱為最高優(yōu)先級（*Highest Priority First，HPF*）調(diào)度算法。

進程的優(yōu)先級可以分為，靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級：

• 靜態(tài)優(yōu)先級：創(chuàng)建進程時候，就已經(jīng)確定了優(yōu)先級了，然后整個運行時間優(yōu)先級都不會變化；
• 動態(tài)優(yōu)先級：根據(jù)進程的動態(tài)變化調(diào)整優(yōu)先級，比如如果進程運行時間增加，則降低其優(yōu)先級，如果進程等待時間（就緒隊列的等待時間）增加，則升高其優(yōu)先級，也就是隨著時間的推移增加等待進程的優(yōu)先級。

該算法也有兩種處理優(yōu)先級高的方法，非搶占式和搶占式：

• 非搶占式：當就緒隊列中出現(xiàn)優(yōu)先級高的進程，運行完當前進程，再選擇優(yōu)先級高的進程。
• 搶占式：當就緒隊列中出現(xiàn)優(yōu)先級高的進程，當前進程掛起，調(diào)度優(yōu)先級高的進程運行。

但是依然有缺點，可能會導致低優(yōu)先級的進程永遠不會運行。

06 多級反饋隊列調(diào)度算法

多級反饋隊列（*Multilevel Feedback Queue*）調(diào)度算法是「時間片輪轉(zhuǎn)算法」和「最高優(yōu)先級算法」的綜合和發(fā)展。

顧名思義：

• 「多級」表示有多個隊列，每個隊列優(yōu)先級從高到低，同時優(yōu)先級越高時間片越短。
• 「反饋」表示如果有新的進程加入優(yōu)先級高的隊列時，立刻停止當前正在運行的進程，轉(zhuǎn)而去運行優(yōu)先級高的隊列；

多級反饋隊列

來看看，它是如何工作的：

• 設(shè)置了多個隊列，賦予每個隊列不同的優(yōu)先級，每個隊列優(yōu)先級從高到低，同時優(yōu)先級越高時間片越短；
• 新的進程會被放入到第一級隊列的末尾，按先來先服務(wù)的原則排隊等待被調(diào)度，如果在第一級隊列規(guī)定的時間片沒運行完成，則將其轉(zhuǎn)入到第二級隊列的末尾，以此類推，直至完成；
• 當較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程運行。如果進程運行時，有新進程進入較高優(yōu)先級的隊列，則停止當前運行的進程并將其移入到原隊列末尾，接著讓較高優(yōu)先級的進程運行；

可以發(fā)現(xiàn)，對于短作業(yè)可能可以在第一級隊列很快被處理完。對于長作業(yè)，如果在第一級隊列處理不完，可以移入下次隊列等待被執(zhí)行，雖然等待的時間變長了，但是運行時間也變更長了，所以該算法很好的兼顧了長短作業(yè)，同時有較好的響應(yīng)時間。

算法

• 給定鏈表 1 -> 2 -> ... -> n-1 -> n，使用 O(1) 空間復(fù)雜度使其變?yōu)?1 -> n -> 2 -> n-1 -> ...
• 只記得有關(guān)滑動窗口，應(yīng)該是力扣 TOP 100 的