還得是騰訊,撈了我一把!
大家好，我是小林。
原來薪資開太高，也會讓人猶豫。最近知道國內(nèi)某新能源公司和跨境電商的公司校招月薪很多都開 30-35K，超過了一線BAT ，很多同學都覺得太高了，都不太敢接。給低了也不想接，給太高也不敢接，真有趣
說到校招，很多公司秋招階段沒有招滿人，就會繼續(xù)進行補錄，面試官大部分都是從簡歷池撈人起來面試，補錄的時候被撈起來面試，很大概率是能撿漏 offer 的，我接觸到很多同學其實都是在 12 月份補錄的環(huán)節(jié)中，突然就上岸大廠了。
這次分享一位 12 月末被騰訊撈起來面試的 Java 后端同學，同學穩(wěn)打穩(wěn)扎經(jīng)歷了一二面，坐等三面，我把一二面比較通用問題做了下分類和解答。
除開實習和項目問題，考察的知識內(nèi)容主要是Java 集合+Java并發(fā)+JVM+MySQL+Redis+網(wǎng)絡(luò)+操作系統(tǒng)+數(shù)據(jù)結(jié)構(gòu)與算法這幾大塊，整體上就是后端開發(fā)+計算機基礎(chǔ)。
這幾大塊是后端開發(fā)面試中比較常見的類型的，所以同學們在準備面試或者學習的時候，需要重點學習這幾大塊的原理知識，以面試問題反推復習的方向，是最高效和快速的方式。
MySQL
MySQL索引原理介紹一下
索引的作用是為了加快查詢效率，MySQL 默認存儲引擎 Innodb 的索引結(jié)構(gòu)是用了 B+樹，B+樹索引按照索引列的值進行排序，并將數(shù)據(jù)分層存儲在索引樹的節(jié)點中，這樣可以通過比較索引值，快速定位到符合條件的數(shù)據(jù)行。
B+樹
B+和B樹平衡二叉樹區(qū)別是什么？
數(shù)據(jù)庫的索引和數(shù)據(jù)都是存儲在硬盤的，我們可以把讀取一個節(jié)點當作一次磁盤 I/O 操作。
B+Tree 存儲千萬級的數(shù)據(jù)只需要 3-4 層高度就可以滿足，這意味著從千萬級的表查詢目標數(shù)據(jù)最多需要 3-4 次磁盤 I/O，所以B+Tree 相比于 B 樹和二叉樹來說，最大的優(yōu)勢在于查詢效率很高，因為即使在數(shù)據(jù)量很大的情況，查詢一個數(shù)據(jù)的磁盤 I/O 依然維持在 3-4次。
1、B+Tree vs B Tree
B+Tree 只在葉子節(jié)點存儲數(shù)據(jù)，而 B 樹 的非葉子節(jié)點也要存儲數(shù)據(jù)，所以 B+Tree 的單個節(jié)點的數(shù)據(jù)量更小，在相同的磁盤 I/O 次數(shù)下，就能查詢更多的節(jié)點。
另外，B+Tree 葉子節(jié)點采用的是雙鏈表連接，適合 MySQL 中常見的基于范圍的順序查找，而 B 樹無法做到這一點。
2、B+Tree vs 二叉樹
對于有 N 個葉子節(jié)點的 B+Tree，其搜索復雜度為O(logdN)，其中 d 表示節(jié)點允許的最大子節(jié)點個數(shù)為 d 個。
在實際的應(yīng)用當中， d 值是大于100的，這樣就保證了，即使數(shù)據(jù)達到千萬級別時，B+Tree 的高度依然維持在 3~4 層左右，也就是說一次數(shù)據(jù)查詢操作只需要做 3~4 次的磁盤 I/O 操作就能查詢到目標數(shù)據(jù)。
而二叉樹的每個父節(jié)點的兒子節(jié)點個數(shù)只能是 2 個，意味著其搜索復雜度為 O(logN)，這已經(jīng)比 B+Tree 高出不少，因此二叉樹檢索到目標數(shù)據(jù)所經(jīng)歷的磁盤 I/O 次數(shù)要更多。
3、B+Tree vs Hash
Hash 在做等值查詢的時候效率賊快，搜索復雜度為 O(1)。
但是 Hash 表不適合做范圍查詢，它更適合做等值的查詢，這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場景的原因。
mysql引擎有哪些，特點有哪些 ？
-
InnoDB：InnoDB是MySQL的默認存儲引擎，具有ACID事務(wù)支持、行級鎖、外鍵約束等特性。它適用于高并發(fā)的讀寫操作，支持較好的數(shù)據(jù)完整性和并發(fā)控制。
-
MyISAM：MyISAM是MySQL的另一種常見的存儲引擎，具有較低的存儲空間和內(nèi)存消耗，適用于大量讀操作的場景。然而，MyISAM不支持事務(wù)、行級鎖和外鍵約束，因此在并發(fā)寫入和數(shù)據(jù)完整性方面有一定的限制。
-
Memory：Memory引擎將數(shù)據(jù)存儲在內(nèi)存中，適用于對性能要求較高的讀操作，但是在服務(wù)器重啟或崩潰時數(shù)據(jù)會丟失。它不支持事務(wù)、行級鎖和外鍵約束。
Redis
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ā)布/訂閱模式，內(nèi)存淘汰機制、過期刪除機制等等。
BitMap和布隆過濾器的區(qū)別？
BitMap是用一個bit位來標記某個元素，如果該元素存在，則將對應(yīng)的比特位設(shè)置為1，否則設(shè)置為0。
BitMap
由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省BitMap適用于對大量的離散元素進行快速判斷和計數(shù)，例如IP地址統(tǒng)計、重復元素判斷等。
布隆過濾器是用于判斷一個元素是否屬于一個集合。布隆過濾器通過多個哈希函數(shù)和一個位數(shù)組來表示集合中的元素，將元素映射到位數(shù)組中的多個位上。當一個元素經(jīng)過多個哈希函數(shù)映射后，對應(yīng)的位都被置為1。
舉個例子，假設(shè)有一個位圖數(shù)組長度為 8，哈希函數(shù) 3 個的布隆過濾器。
布隆過濾器
布隆過濾器判斷一個元素是否存在時，只需要檢查對應(yīng)的位是否都為1：
- 若有任意位為0，則可以確定元素不存在；
- 若都為1，則可能存在，但存在一定的誤判概率。
查詢布隆過濾器說數(shù)據(jù)存在，并不一定證明數(shù)據(jù)庫中存在這個數(shù)據(jù)，但是查詢到數(shù)據(jù)不存在，數(shù)據(jù)庫中一定就不存在這個數(shù)據(jù)。布隆過濾器適用于對大規(guī)模數(shù)據(jù)進行快速的去重或判重操作，例如網(wǎng)絡(luò)爬蟲的URL去重、緩存的緩存命中判斷等。
Redis為什么使用跳表而不是用B+樹?
主要是從內(nèi)存占用、對范圍查找的支持、實現(xiàn)難易程度這三方面總結(jié)的原因：
- 從內(nèi)存占用上來比較，跳表比平衡樹更靈活一些。平衡樹每個節(jié)點包含 2 個指針（分別指向左右子樹），而跳表每個節(jié)點包含的指針數(shù)目平均為 1/(1-p)，具體取決于參數(shù) p 的大小。如果像 Redis里的實現(xiàn)一樣，取 p=1/4，那么平均每個節(jié)點包含 1.33 個指針，比平衡樹更有優(yōu)勢。
- 在做范圍查找的時候，跳表比平衡樹操作要簡單。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現(xiàn)。而在跳表上進行范圍查找就非常簡單，只需要在找到小值之后，對第 1 層鏈表進行若干步的遍歷就可以實現(xiàn)。
- 從算法實現(xiàn)難度上來比較，跳表比平衡樹要簡單得多。平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，邏輯復雜，而跳表的插入和刪除只需要修改相鄰節(jié)點的指針，操作簡單又快速。
Java
HashMap怎么處理哈希沖突的？
在 JDK 1.7 版本之前， HashMap 數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表，HashMap通過哈希算法將元素的鍵（Key）映射到數(shù)組中的槽位（Bucket）。如果多個鍵映射到同一個槽位，它們會以鏈表的形式存儲在同一個槽位上，因為鏈表的查詢時間是O(n)，所以沖突很嚴重，一個索引上的鏈表非常長，效率就很低了。
所以在 JDK 1.8版本的時候做了優(yōu)化，當一個鏈表的長度超過8的時候就轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)，不再使用鏈表存儲，而是使用紅黑樹，查找時使用紅黑樹，時間復雜度O（log n），可以提高查詢性能，但是在數(shù)量較少時，即數(shù)量小于6時，會將紅黑樹轉(zhuǎn)換回鏈表。
HashMap
HashMap是線程安全的嗎？
不是的，會產(chǎn)生這些并發(fā)安全問題：
- JDK 1.7 HashMap 采用數(shù)組 + 鏈表的數(shù)據(jù)結(jié)構(gòu)，多線程背景下，在數(shù)組擴容的時候，存在 Entry 鏈死循環(huán)和數(shù)據(jù)丟失問題。
- JDK 1.8 HashMap 采用數(shù)組 + 鏈表 + 紅黑二叉樹的數(shù)據(jù)結(jié)構(gòu)，優(yōu)化了 1.7 中數(shù)組擴容的方案，解決了 Entry 鏈死循環(huán)和數(shù)據(jù)丟失問題。但是多線程背景下，put 方法存在數(shù)據(jù)覆蓋的問題。
并發(fā)環(huán)境下使用Map，怎么保證線程安全？
可以改用并發(fā)安全的 map 容器，比如ConcurrentHashMap 或者 hashtable，都是能保證線程安全的。
ConcurrentHashMap怎么保證線程安全？1.7和1.8的區(qū)別？
JDK 1.7 ConcurrentHashMap
在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實現(xiàn)的，而數(shù)組又分為：大數(shù)組 Segment 和小數(shù)組 HashEntry。Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲鍵值對數(shù)據(jù)。一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組，一個 Segment 里包含一個 HashEntry 數(shù)組，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素。
JDK 1.7 ConcurrentHashMap
分段鎖技術(shù)將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。
JDK 1.8 ConcurrentHashMap
在 JDK 1.7 中，ConcurrentHashMap 雖然是線程安全的，但因為它的底層實現(xiàn)是數(shù)組 + 鏈表的形式，所以在數(shù)據(jù)比較多的情況下訪問是很慢的，因為要遍歷整個鏈表，而 JDK 1.8 則使用了數(shù)組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實現(xiàn)，具體實現(xiàn)結(jié)構(gòu)如下：
JDK 1.8 ConcurrentHashMap
JDK 1.8 ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實現(xiàn)的線程安全的。
添加元素時首先會判斷容器是否為空：
-
如果為空則使用 volatile 加 CAS 來初始化，如果容器不為空，則根據(jù)存儲的元素計算該位置是否為空。
-
- 如果根據(jù)存儲的元素計算結(jié)果為空，則利用 CAS 設(shè)置該節(jié)點；
- 如果根據(jù)存儲的元素計算結(jié)果不為空，則使用 synchronized ，然后，遍歷桶中的數(shù)據(jù)，并替換或新增節(jié)點到桶中，最后再判斷是否需要轉(zhuǎn)為紅黑樹，這樣就能保證并發(fā)訪問時的線程安全了。
如果把上面的執(zhí)行用一句話歸納的話，就相當于是ConcurrentHashMap通過對頭結(jié)點加鎖來保證線程安全的，鎖的粒度相比 Segment 來說更小了，發(fā)生沖突和加鎖的頻率降低了，并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表，那么當數(shù)據(jù)量比較大的時候，查詢性能也得到了很大的提升，從之前的 O(n) 優(yōu)化到了 O(logn) 的時間復雜度。
分段鎖是可重入的嗎？
JDK 1.7 ConcurrentHashMap中的分段鎖是用了 ReentrantLock，是一個可重入的鎖。
你怎么理解可重入鎖？
可重入鎖是指同一個線程在獲取了鎖之后，可以再次重復獲取該鎖而不會造成死鎖或其他問題。當一個線程持有鎖時，如果再次嘗試獲取該鎖，就會成功獲取而不會被阻塞。
ReentrantLock實現(xiàn)可重入鎖的機制是基于線程持有鎖的計數(shù)器。
-
當一個線程第一次獲取鎖時，計數(shù)器會加1，表示該線程持有了鎖。在此之后，如果同一個線程再次獲取鎖，計數(shù)器會再次加1。每次線程成功獲取鎖時，都會將計數(shù)器加1。
-
當線程釋放鎖時，計數(shù)器會相應(yīng)地減1。只有當計數(shù)器減到0時，鎖才會完全釋放，其他線程才有機會獲取鎖。
這種計數(shù)器的設(shè)計使得同一個線程可以多次獲取同一個鎖，而不會造成死鎖或其他問題。每次獲取鎖時，計數(shù)器加1；每次釋放鎖時，計數(shù)器減1。只有當計數(shù)器減到0時，鎖才會完全釋放。
ReentrantLock通過這種計數(shù)器的方式，實現(xiàn)了可重入鎖的機制。它允許同一個線程多次獲取同一個鎖，并且能夠正確地處理鎖的獲取和釋放，避免了死鎖和其他并發(fā)問題。
什么是公平鎖和非公平鎖？
-
公平鎖： 指多個線程按照申請鎖的順序來獲取鎖，線程直接進入隊列中排隊，隊列中的第一個線程才能獲得鎖。公平鎖的優(yōu)點在于各個線程公平平等，每個線程等待一段時間后，都有執(zhí)行的機會，而它的缺點就在于整體執(zhí)行速度更慢，吞吐量更小。
-
非公平鎖： 多個線程加鎖時直接嘗試獲取鎖，能搶到鎖到直接占有鎖，搶不到才會到等待隊列的隊尾等待。非公平鎖的優(yōu)勢就在于整體執(zhí)行速度更快，吞吐量更大，但同時也可能產(chǎn)生線程饑餓問題，也就是說如果一直有線程插隊，那么在等待隊列中的線程可能長時間得不到運行。
非公平鎖吞吐量為什么比公平鎖大？
-
公平鎖執(zhí)行流程：獲取鎖時，先將線程自己添加到等待隊列的隊尾并休眠，當某線程用完鎖之后，會去喚醒等待隊列中隊首的線程嘗試去獲取鎖，鎖的使用順序也就是隊列中的先后順序，在整個過程中，線程會從運行狀態(tài)切換到休眠狀態(tài)，再從休眠狀態(tài)恢復成運行狀態(tài)，但線程每次休眠和恢復都需要從用戶態(tài)轉(zhuǎn)換成內(nèi)核態(tài)，而這個狀態(tài)的轉(zhuǎn)換是比較慢的，所以公平鎖的執(zhí)行速度會比較慢。
-
非公平鎖執(zhí)行流程：當線程獲取鎖時，會先通過 CAS 嘗試獲取鎖，如果獲取成功就直接擁有鎖，如果獲取鎖失敗才會進入等待隊列，等待下次嘗試獲取鎖。這樣做的好處是，獲取鎖不用遵循先到先得的規(guī)則，從而避免了線程休眠和恢復的操作，這樣就加速了程序的執(zhí)行效率。
JVM
JVM內(nèi)存結(jié)構(gòu)有哪些？
JVM的內(nèi)存結(jié)構(gòu)主要分為以下幾個部分：
- 程序計數(shù)器（Program Counter Register）：每個線程都有一個程序計數(shù)器。當線程執(zhí)行 Java 方法時，程序計數(shù)器保存當前執(zhí)行指令的地址，以便在 JVM 調(diào)用其他方法或恢復線程執(zhí)行時重新回到正確的位置。
- Java 虛擬機棧（Java Virtual Machine Stacks）：每個線程都有一個虛擬機棧。虛擬機棧保存著方法執(zhí)行期間的局部變量、操作數(shù)棧、方法出口等信息。線程每調(diào)用一個 Java 方法時，會創(chuàng)建一個棧幀（Stack Frame），棧幀包含著該方法的局部變量、操作數(shù)棧、方法返回地址等信息。棧幀在方法執(zhí)行結(jié)束后會被彈出。
- 本地方法棧（Native Method Stack）：與 Java 虛擬機棧類似，但是為本地方法服務(wù)。
- Java 堆（Java Heap）：Java 堆是 Java 虛擬機中最大的一塊內(nèi)存區(qū)域，用于存儲各種類型的對象實例，也是垃圾收集器的主要工作區(qū)域，Java 堆根據(jù)對象存活時間的不同，Java 堆還被分為年輕代、老年代兩個區(qū)域，年輕代還被進一步劃分為 Eden 區(qū)、From Survivor 0、To Survivor 1 區(qū)。
- 方法區(qū)（Method Area）：方法區(qū)也是所有線程共享的部分，它用于存儲類的加載信息、靜態(tài)變量、常量池、方法字節(jié)碼等數(shù)據(jù)。在 Java 8 及以前的版本中，方法區(qū)被實現(xiàn)為永久代（Permanent Generation），在 Java 8 中被改為元空間（Metaspace）。
JVM為什么把堆區(qū)進一步的劃分？
Java 堆還被分為年輕代、老年代兩個區(qū)域，年輕代還被進一步劃分為 Eden 區(qū)、From Survivor 0、To Survivor 1 區(qū)。
不同的區(qū)域存放不同生命周期的對象，這樣可以根據(jù)不同的區(qū)域使用不同的垃圾回收算法，更具有針對性。
jvm-memory
當有對象需要分配時，一個對象永遠優(yōu)先被分配在年輕代的 Eden 區(qū)，等到 Eden 區(qū)域內(nèi)存不夠時，Java 虛擬機會啟動垃圾回收。此時 Eden 區(qū)中沒有被引用的對象的內(nèi)存就會被回收，而一些存活時間較長的對象則會進入到老年代。在 JVM 中有一個名為 -XX:MaxTenuringThreshold 的參數(shù)專門用來設(shè)置晉升到老年代所需要經(jīng)歷的 GC 次數(shù)，即在年輕代的對象經(jīng)過了指定次數(shù)的 GC 后，將在下次 GC 時進入老年代。
之所以要在堆區(qū)進一步劃分，主要是為了提高垃圾回收的效率。虛擬機中的對象必然有存活時間長的對象，也有存活時間短的對象，這是一個普遍存在的正態(tài)分布規(guī)律。如果我們將其混在一起，那么因為存活時間短的對象有很多，那么勢必導致較為頻繁的垃圾回收。而垃圾回收時不得不對所有內(nèi)存都進行掃描，但其實有一部分對象，它們存活時間很長，對他們進行掃描完全是浪費時間
String保存在哪里呢？
String 保存在字符串常量池中，不同于其他對象，它的值是不可變的，且可以被多個引用共享。
說一下JVM加載一個類的過程
類從被加載到虛擬機內(nèi)存開始，到卸載出內(nèi)存為止，它的整個生命周期包括以下 7 個階段：
- 加載
- 驗證
- 準備
- 解析
- 初始化
- 使用
- 卸載
驗證、準備、解析 3 個階段統(tǒng)稱為連接。
Load Class
JVM 中類的裝載是由類加載器，也就是ClassLoader，和它的子類來實現(xiàn)的，Java 中的類加載器是一個重要的 Java 運行時系統(tǒng)組件，它負責在運行時查找和裝入類文件中的類。
由于 Java 的跨平臺性， 經(jīng)過編譯的 Java 源程序并不是一個可執(zhí)行程序， 而是一個或多個類文件。當 Java 程序需要使用某個類時，JVM 會確保這個類已經(jīng)被加載、連接（ 驗證、 準備和解析）和初始化。
類的加載是指把類的.class 文件中的數(shù)據(jù)讀入到內(nèi)存中，通常是創(chuàng)建一個字節(jié)數(shù)組讀入.class 文件，然后產(chǎn)生與所加載類對應(yīng)的 Class 對象。加載完成后， Class 對象還不完整， 所以此時的類還不可用。當類被加載后就進入連接階段， 這一階段包括驗證、準備（ 為靜態(tài)變量分配內(nèi)存并設(shè)置默認的初始值） 和解析（ 將符號引用替換為直接引用） 三個步驟。
最后 JVM 對類進行初始化，包括：1)如果類存在直接的父類并且這個類還沒有被初始化，那么就先初始化父類；2)如果類中存在初始化語句， 就依次執(zhí)行這些初始化語句。
網(wǎng)絡(luò)
tcp滑動窗口是怎么實現(xiàn)的？
發(fā)送方的滑動窗口
我們先來看看發(fā)送方的窗口，下圖就是發(fā)送方緩存的數(shù)據(jù)，根據(jù)處理的情況分成四個部分，其中深藍色方框是發(fā)送窗口，紫色方框是可用窗口：
- #1 是已發(fā)送并收到 ACK確認的數(shù)據(jù)：1~31 字節(jié)
- #2 是已發(fā)送但未收到 ACK確認的數(shù)據(jù)：32~45 字節(jié)
- #3 是未發(fā)送但總大小在接收方處理范圍內(nèi)（接收方還有空間）：46~51字節(jié)
- #4 是未發(fā)送但總大小超過接收方處理范圍（接收方?jīng)]有空間）：52字節(jié)以后
在下圖，當發(fā)送方把數(shù)據(jù)「全部」都一下發(fā)送出去后，可用窗口的大小就為 0 了，表明可用窗口耗盡，在沒收到 ACK 確認之前是無法繼續(xù)發(fā)送數(shù)據(jù)了。
可用窗口耗盡
在下圖，當收到之前發(fā)送的數(shù)據(jù) 32~36 字節(jié)的 ACK 確認應(yīng)答后，如果發(fā)送窗口的大小沒有變化，則滑動窗口往右邊移動 5 個字節(jié)，因為有 5 個字節(jié)的數(shù)據(jù)被應(yīng)答確認，接下來 52~56 字節(jié)又變成了可用窗口，那么后續(xù)也就可以發(fā)送 52~56 這 5 個字節(jié)的數(shù)據(jù)了。
32 ~ 36 字節(jié)已確認
程序是如何表示發(fā)送方的四個部分的呢？
TCP 滑動窗口方案使用三個指針來跟蹤在四個傳輸類別中的每一個類別中的字節(jié)。其中兩個指針是絕對指針（指特定的序列號），一個是相對指針（需要做偏移）。
SND.WND、SND.UN、SND.NXT
-
SND.WND：表示發(fā)送窗口的大小（大小是由接收方指定的）； -
SND.UNA（Send Unacknoleged）：是一個絕對指針，它指向的是已發(fā)送但未收到確認的第一個字節(jié)的序列號，也就是 #2 的第一個字節(jié)。 -
SND.NXT：也是一個絕對指針，它指向未發(fā)送但可發(fā)送范圍的第一個字節(jié)的序列號，也就是 #3 的第一個字節(jié)。 - 指向 #4 的第一個字節(jié)是個相對指針，它需要
SND.UNA指針加上SND.WND大小的偏移量，就可以指向 #4 的第一個字節(jié)了。
那么可用窗口大小的計算就可以是：
可用窗口大小 = SND.WND -（SND.NXT - SND.UNA）
接收方的滑動窗口
接下來我們看看接收方的窗口，接收窗口相對簡單一些，根據(jù)處理的情況劃分成三個部分：
- #1 + #2 是已成功接收并確認的數(shù)據(jù)（等待應(yīng)用進程讀取）；
- #3 是未收到數(shù)據(jù)但可以接收的數(shù)據(jù)；
- #4 未收到數(shù)據(jù)并不可以接收的數(shù)據(jù)；
接收窗口
其中三個接收部分，使用兩個指針進行劃分:
-
RCV.WND：表示接收窗口的大小，它會通告給發(fā)送方。 -
RCV.NXT：是一個指針，它指向期望從發(fā)送方發(fā)送來的下一個數(shù)據(jù)字節(jié)的序列號，也就是 #3 的第一個字節(jié)。 - 指向 #4 的第一個字節(jié)是個相對指針，它需要
RCV.NXT指針加上RCV.WND大小的偏移量，就可以指向 #4 的第一個字節(jié)了。
tcp粘包怎么解決？
粘包的問題出現(xiàn)是因為不知道一個用戶消息的邊界在哪，如果知道了邊界在哪，接收方就可以通過邊界來劃分出有效的用戶消息。
一般有三種方式分包的方式：
- 固定長度的消息；
- 特殊字符作為邊界；
- 自定義消息結(jié)構(gòu)。
固定長度的消息
這種是最簡單方法，即每個用戶消息都是固定長度的，比如規(guī)定一個消息的長度是 64 個字節(jié)，當接收方接滿 64 個字節(jié)，就認為這個內(nèi)容是一個完整且有效的消息。
但是這種方式靈活性不高，實際中很少用。
特殊字符作為邊界
我們可以在兩個用戶消息之間插入一個特殊的字符串，這樣接收方在接收數(shù)據(jù)時，讀到了這個特殊字符，就把認為已經(jīng)讀完一個完整的消息。
HTTP 是一個非常好的例子。
HTTP 通過設(shè)置回車符、換行符作為 HTTP 報文協(xié)議的邊界。
有一點要注意，這個作為邊界點的特殊字符，如果剛好消息內(nèi)容里有這個特殊字符，我們要對這個字符轉(zhuǎn)義，避免被接收方當作消息的邊界點而解析到無效的數(shù)據(jù)。
自定義消息結(jié)構(gòu)
我們可以自定義一個消息結(jié)構(gòu)，由包頭和數(shù)據(jù)組成，其中包頭包是固定大小的，而且包頭里有一個字段來說明緊隨其后的數(shù)據(jù)有多大。
比如這個消息結(jié)構(gòu)體，首先 4 個字節(jié)大小的變量來表示數(shù)據(jù)長度，真正的數(shù)據(jù)則在后面。
struct {
u_int32_t message_length;
char message_data[];
} message;
當接收方接收到包頭的大小（比如 4 個字節(jié)）后，就解析包頭的內(nèi)容，于是就可以知道數(shù)據(jù)的長度，然后接下來就繼續(xù)讀取數(shù)據(jù)，直到讀滿數(shù)據(jù)的長度，就可以組裝成一個完整到用戶消息來處理了。
HTTP1.1和2.0的區(qū)別是什么？
HTTP/2 相比 HTTP/1.1 性能上的改進：
- 頭部壓縮
- 二進制格式
- 并發(fā)傳輸
- 服務(wù)器主動推送資源
1. 頭部壓縮
HTTP/2 會壓縮頭（Header）如果你同時發(fā)出多個請求，他們的頭是一樣的或是相似的，那么，協(xié)議會幫你消除重復的部分。
這就是所謂的 HPACK 算法：在客戶端和服務(wù)器同時維護一張頭信息表，所有字段都會存入這個表，生成一個索引號，以后就不發(fā)送同樣字段了，只發(fā)送索引號，這樣就提高速度了。
2. 二進制格式
HTTP/2 不再像 HTTP/1.1 里的純文本形式的報文，而是全面采用了二進制格式，頭信息和數(shù)據(jù)體都是二進制，并且統(tǒng)稱為幀（frame）：頭信息幀（Headers Frame）和數(shù)據(jù)幀（Data Frame）。
HTTP/1 與 HTTP/2
這樣雖然對人不友好，但是對計算機非常友好，因為計算機只懂二進制，那么收到報文后，無需再將明文的報文轉(zhuǎn)成二進制，而是直接解析二進制報文，這增加了數(shù)據(jù)傳輸?shù)男?/strong>。
3. 并發(fā)傳輸
我們都知道 HTTP/1.1 的實現(xiàn)是基于請求-響應(yīng)模型的。同一個連接中，HTTP 完成一個事務(wù)（請求與響應(yīng)），才能處理下一個事務(wù)，也就是說在發(fā)出請求等待響應(yīng)的過程中，是沒辦法做其他事情的，如果響應(yīng)遲遲不來，那么后續(xù)的請求是無法發(fā)送的，也造成了隊頭阻塞的問題。
而 HTTP/2 就很牛逼了，引出了 Stream 概念，多個 Stream 復用在一條 TCP 連接。
從上圖可以看到，1 個 TCP 連接包含多個 Stream，Stream 里可以包含 1 個或多個 Message，Message 對應(yīng) HTTP/1 中的請求或響應(yīng)，由 HTTP 頭部和包體構(gòu)成。Message 里包含一條或者多個 Frame，F(xiàn)rame 是 HTTP/2 最小單位，以二進制壓縮格式存放 HTTP/1 中的內(nèi)容（頭部和包體）。
針對不同的 HTTP 請求用獨一無二的 Stream ID 來區(qū)分，接收端可以通過 Stream ID 有序組裝成 HTTP 消息，不同 Stream 的幀是可以亂序發(fā)送的，因此可以并發(fā)不同的 Stream ，也就是 HTTP/2 可以并行交錯地發(fā)送請求和響應(yīng)。
比如下圖，服務(wù)端并行交錯地發(fā)送了兩個響應(yīng)：Stream 1 和 Stream 3，這兩個 Stream 都是跑在一個 TCP 連接上，客戶端收到后，會根據(jù)相同的 Stream ID 有序組裝成 HTTP 消息。
4、服務(wù)器推送
HTTP/2 還在一定程度上改善了傳統(tǒng)的「請求 - 應(yīng)答」工作模式，服務(wù)端不再是被動地響應(yīng)，可以主動向客戶端發(fā)送消息。
客戶端和服務(wù)器雙方都可以建立 Stream， Stream ID 也是有區(qū)別的，客戶端建立的 Stream 必須是奇數(shù)號，而服務(wù)器建立的 Stream 必須是偶數(shù)號。
比如下圖，Stream 1 是客戶端向服務(wù)端請求的資源，屬于客戶端建立的 Stream，所以該 Stream 的 ID 是奇數(shù)（數(shù)字 1）；Stream 2 和 4 都是服務(wù)端主動向客戶端推送的資源，屬于服務(wù)端建立的 Stream，所以這兩個 Stream 的 ID 是偶數(shù)（數(shù)字 2 和 4）。
再比如，客戶端通過 HTTP/1.1 請求從服務(wù)器那獲取到了 HTML 文件，而 HTML 可能還需要依賴 CSS 來渲染頁面，這時客戶端還要再發(fā)起獲取 CSS 文件的請求，需要兩次消息往返，如下圖左邊部分：
如上圖右邊部分，在 HTTP/2 中，客戶端在訪問 HTML 時，服務(wù)器可以直接主動推送 CSS 文件，減少了消息傳遞的次數(shù)。
操作系統(tǒng)
講講IO多路復用的實現(xiàn)原理，select和epoll的區(qū)別是什么？
I/O 的多路復用，可以只在一個進程里處理多個文件的 I/O，Linux 下有三種提供 I/O 多路復用的 API，分別是：select、poll、epoll。
select 和 poll 并沒有本質(zhì)區(qū)別，它們內(nèi)部都是使用「線性結(jié)構(gòu)」來存儲進程關(guān)注的 Socket 集合。
在使用的時候，首先需要把關(guān)注的 Socket 集合通過 select/poll 系統(tǒng)調(diào)用從用戶態(tài)拷貝到內(nèi)核態(tài)，然后由內(nèi)核檢測事件，當有網(wǎng)絡(luò)事件產(chǎn)生時，內(nèi)核需要遍歷進程關(guān)注 Socket 集合，找到對應(yīng)的 Socket，并設(shè)置其狀態(tài)為可讀/可寫，然后把整個 Socket 集合從內(nèi)核態(tài)拷貝到用戶態(tài)，用戶態(tài)還要繼續(xù)遍歷整個 Socket 集合找到可讀/可寫的 Socket，然后對其處理。
很明顯發(fā)現(xiàn)，select 和 poll 的缺陷在于，當客戶端越多，也就是 Socket 集合越大，Socket 集合的遍歷和拷貝會帶來很大的開銷，因此也很難應(yīng)對 C10K。
epoll 是解決 C10K 問題的利器，通過兩個方面解決了 select/poll 的問題。
- epoll 在內(nèi)核里使用「紅黑樹」來關(guān)注進程所有待檢測的 Socket，紅黑樹是個高效的數(shù)據(jù)結(jié)構(gòu)，增刪改一般時間復雜度是 O(logn)，通過對這棵黑紅樹的管理，不需要像 select/poll 在每次操作時都傳入整個 Socket 集合，減少了內(nèi)核和用戶空間大量的數(shù)據(jù)拷貝和內(nèi)存分配。
- epoll 使用事件驅(qū)動的機制，內(nèi)核里維護了一個「鏈表」來記錄就緒事件，只將有事件發(fā)生的 Socket 集合傳遞給應(yīng)用程序，不需要像 select/poll 那樣輪詢掃描整個集合（包含有和無事件的 Socket ），大大提高了檢測的效率。
算法
- 手撕lru算法
- 判斷一棵二叉搜索樹
歷史好文： 后端突擊訓練營，又開始卷了！ 不想卷了，沖國企去了！！
準備很久，還是被小紅書虐了。。。
米哈游穩(wěn)住了！問的很基礎(chǔ)！