1、滿二叉樹、完全二叉樹、平衡二叉樹、紅黑樹、二叉搜索樹的區(qū)別？

參考文章：樹、二叉樹(完全二叉樹、滿二叉樹)概念圖解

① 滿二叉樹

高度為 h，由 2^h-1個節(jié)點(diǎn)構(gòu)成的二叉樹稱為滿二叉樹。

② 完全二叉樹

完全二叉樹是由滿二叉樹而引出來的，若二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)(即1~h-1層為一個滿二叉樹)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。

堆一般都是用完全二叉樹來實(shí)現(xiàn)的。

③ 二叉查找樹

二叉查找樹是二叉樹中最常用的一種類型，是為了實(shí)現(xiàn)快速查找的，不僅僅支持快速查找一個數(shù)，還支持快速插入和刪除數(shù)據(jù)。二叉查找樹的這些性能都依賴于二叉查找樹的特殊結(jié)構(gòu)，二叉查找樹的要求，在樹中的任意一個節(jié)點(diǎn)，其左子樹中的每個節(jié)點(diǎn)的值，都要小于這個節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)的值都要大于這個節(jié)點(diǎn)的值。

④ 紅黑樹

紅黑樹的優(yōu)勢在于它是一棵平衡二叉查找樹，對于普通的二叉查找樹（非平衡二叉查找樹）在極端情況下可能會退化為鏈表的結(jié)構(gòu)，例如，當(dāng)我們依次插入 3、4、5、6、7、8 這些數(shù)據(jù)時，二叉樹會退化為如下鏈表結(jié)構(gòu)：

紅黑樹是一種弱平衡二叉樹（只有黑色節(jié)點(diǎn)完美平衡，紅色節(jié)點(diǎn)不一定平衡），是特殊的二叉查找樹（平衡二叉查找樹）。

⑤ 平衡二叉樹

AVL樹是帶有平衡條件的二叉查找樹，一般是用平衡因子差值判斷是否平衡并通過旋轉(zhuǎn)來實(shí)現(xiàn)平衡，左右子樹樹高不超過 1，和紅黑樹相比，AVL樹是嚴(yán)格的平衡二叉樹，平衡條件必須滿足（所有節(jié)點(diǎn)的左右子樹高度差的絕對值不超過1）。

不管我們是執(zhí)行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉(zhuǎn)來保持平衡，而旋轉(zhuǎn)是非常耗時的，由此我們可以知道 AVL 樹適合用于插入與刪除次數(shù)比較少，但查找多的情況。

2、IP地址分類

ABCDE五類，A、B、C為基本類，D、E作為多播和保留使用，為特殊地址。

• A類地址：以0開頭
• B類地址：以10開頭
• C類地址：以110開頭
• D類地址：以1110開頭
• E類地址：以1111開頭，保留地址

3、三次握手過程中可以攜帶數(shù)據(jù)嗎？

第三次握手時可以攜帶數(shù)據(jù)，但是第一、二次不行。

原因：設(shè)想這樣的場景，若第一次握手可以攜帶數(shù)據(jù)，有人要惡意攻擊服務(wù)器，則他每次都可以在第一次握手中的SYN報(bào)文中放入大量數(shù)據(jù)，會讓服務(wù)器花費(fèi)很多時間、空間來處理報(bào)文。

也就是說：第一次握手無法放數(shù)據(jù)，保證了服務(wù)器的安全性。而第三次握手時，已經(jīng)代表成功的建立了連接，從客戶端攜帶數(shù)據(jù)到服務(wù)器也是被理解的。

4、SYN攻擊是什么？

概念：Client在短時間偽造大量不存在的ip地址，向Server不斷發(fā)送SYN包，Server則回復(fù)確認(rèn)包，并等待Client確認(rèn)，這些包將長時間占用未連接隊(duì)列，導(dǎo)致其他正常的SYN請求因?yàn)殛?duì)列滿被丟棄，從而引起網(wǎng)絡(luò)擁塞甚至系統(tǒng)癱瘓（Dos/DDoS攻擊）

如何檢測：當(dāng)看到大量半連接狀態(tài)，且源地址 IP 為隨機(jī)時，即可斷定為一次 SYN 攻擊（Linux中的netstat命令）。

解決辦法：縮短SYN包的過期時間，過濾網(wǎng)關(guān)防護(hù)、防火墻等。

5、線程調(diào)度策略？

分時調(diào)度模型、搶占式調(diào)度模型。

搶占式調(diào)度 指的是每條線程執(zhí)行的時間、線程的切換都由系統(tǒng)控制，系統(tǒng)控制指的是在系統(tǒng)某種運(yùn)行機(jī)制下，每條線程可能分同樣的執(zhí)行時間片，也可能是某些線程執(zhí)行的時間片較長，甚至某些線程得不到執(zhí)行的時間片。在這種機(jī)制下，一個線程的堵塞不會導(dǎo)致整個進(jìn)程堵塞。

**協(xié)同式調(diào)度 **指的是某一線程執(zhí)行完后主動通知系統(tǒng)切換到另一線程上執(zhí)行，這種模式就像接力賽一樣，一個人跑完自己的路程就把接力棒交接給下一個人，下個人繼續(xù)往下跑。線程的執(zhí)行時間由線程本身控制，線程切換可以預(yù)知，不存在多線程同步問題，但它有一個致命弱點(diǎn)：如果一個線程編寫有問題，運(yùn)行到一半就一直 堵塞，那么可能導(dǎo)致整個系統(tǒng)崩潰。

JVM采用搶占式調(diào)度模型。

6、為什么wait、notify定義在Object中？

① JAVA提供的鎖是對象級的 (每個對象都有一把稱之為monitor監(jiān)控器的鎖)，而不是線程級的，每個對象都有鎖，通過線程可以獲取鎖，一個線程可以獲取多個鎖。Object 是所有對象的頂級父類，因此統(tǒng)一把對象鎖設(shè)置為 Object 對象，這樣 Jvm 就會很容易知道應(yīng)該從哪個對象鎖的等待池中喚醒線程。否則它根本不知道要操作的是哪一個。

② wait/notify/notifyAll 都是對象鎖級別的操作，如果把 wait/notify/notifyAll 方法定義在 Thread 類中，會帶來很大的局限性：

•  比如一個線程可能持有多把鎖，以便實(shí)現(xiàn)相互配合的復(fù)雜邏輯，假設(shè)此時 wait() 方法定義到 Thread 類中，這會遇到下面兩個問題：
• 如何實(shí)現(xiàn)讓一個線程持有多把鎖呢？
• 又如何明確線程等待的是那把鎖呢？

簡單的說，由于wait，notify和notifyAll都是鎖級別的操作，所以把他們定義在 Object 類中因?yàn)殒i屬于對象。

7、為什么wait，notify必須在同步方法或同步塊中被調(diào)用？

因?yàn)椋?code>wait() 方法調(diào)用時，會釋放對象鎖，那么一個線程調(diào)用 wait()的前提條件是，它必須擁有該對象鎖，隨后釋放并等待，若達(dá)到了 notify()后，再進(jìn)入鎖。

8、yield() 和 sleep() 區(qū)別？

（1） sleep()方法給其他線程運(yùn)行機(jī)會時不考慮線程的優(yōu)先級，因此會給低優(yōu)先級的線程以運(yùn)行的機(jī)會；yield()方法只會給相同優(yōu)先級或更高優(yōu)先級的線程以運(yùn)行的機(jī)會；

（2） 線程執(zhí)行 sleep() 方法后轉(zhuǎn)入阻塞（blocked）狀態(tài)，而執(zhí)行 yield() 方法后轉(zhuǎn)入就緒（ready）狀態(tài)；

（3）sleep() 方法使用時，需要聲明拋出 InterruptedException，而 yield() 方法不需要聲明任何異常；

9、如果提交時，線程池隊(duì)列滿，會發(fā)生什么？

（1）如果使用的是無界隊(duì)列 LinkedBlockingQueue，那么，可以繼續(xù)添加任務(wù)到阻塞隊(duì)列中等待執(zhí)行，因?yàn)?nbsp;LinkedBlockingQueue 可以近乎認(rèn)為是一個無窮大的隊(duì)列，可以無限存放任務(wù)。

（2）如果使用的是有界隊(duì)列 比如 ArrayBlockingQueue，任務(wù)首先會被添加到 ArrayBlockingQueue 中，ArrayBlockingQueue 滿了，會根據(jù) maximumPoolSize 的值增加線程數(shù)量，如果增加了線程數(shù)量還是處理不過來，ArrayBlockingQueue 繼續(xù)滿，那么則會使用拒絕策略 RejectedExecutionHandler 處理滿了的任務(wù)，默認(rèn)是中止策略 AbortPolicy。

10、JVM調(diào)優(yōu)參數(shù)參考

注：這2點(diǎn)僅是簡單的作為參考，之后會專門去研究一下這塊知識區(qū)，寫文章分享給大家

① 對堆的參數(shù)調(diào)整

• 通過 -Xms -Xmx 限定堆的最小值、最大值，為了防止垃圾收集器在最小、最大之間收縮堆而產(chǎn)生額外的時間，通常把最大、最小設(shè)置為相同的值。
• 年輕代和年老代將根據(jù)默認(rèn)的比例（1：2）分配堆內(nèi)存，考慮到年輕代需要頻繁的進(jìn)行垃圾回收（堆的空余空間比率不斷變化，會導(dǎo)致堆內(nèi)存大小取值的不斷調(diào)整，觸發(fā)閾值為 40%、70%）我們通常會把 -XX:newSize -XX:MaxNewSize 設(shè)置為同樣大小。

年輕代和年老代設(shè)置多大才算合理?

1）更大的年輕代必然導(dǎo)致更小的年老代，大的年輕代會延長普通 GC 的周期，但會增加每次 GC 的時間；小的年老代會導(dǎo)致更頻繁的Full GC。

2）更小的年輕代必然導(dǎo)致更大年老代，小的年輕代會導(dǎo)致普通 GC 很頻繁，但每次的 GC 時間會更短；大的年老代會減少Full GC的頻率。

如何選擇應(yīng)該依賴應(yīng)用程序對象生命周期的分布情況： 如果應(yīng)用存在大量的臨時對象，應(yīng)該選擇更大的年輕代；如果存在相對較多的持久對象，年老代應(yīng)該適當(dāng)增大。但很多應(yīng)用都沒有這樣明顯的特性。

在抉擇時應(yīng)該根 據(jù)以下兩點(diǎn)：

• 本著 Full GC 盡量少的原則，讓年老代盡量緩存常用對象，JVM 的默認(rèn)比例 1：2 也是這個道理 。
• 通過觀察應(yīng)用一段時間，看其他在峰值時年老代會占多少內(nèi)存，在不影響 Full GC 的前提下，根據(jù)實(shí)際情況加大年輕代，比如可以把比例控制在 1：1。但應(yīng)該給年老代至少預(yù)留 1/3 的增長空間。

 ② 對棧的參數(shù)調(diào)整

每個線程默認(rèn)會開啟 1M 的堆棧，用于存放棧幀、調(diào)用參數(shù)、局部變量等，對大多數(shù)應(yīng)用而言這個默認(rèn)值太大了，一般 256K 就足用。

理論上，在內(nèi)存不變的情況下，減少每個線程的堆棧，可以產(chǎn)生更多的線程，但這實(shí)際上還受限于操作系統(tǒng)。

總結(jié)

本篇文章就到這里了，希望可以給你帶來一些幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論