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

參考文章：樹(shù)、二叉樹(shù)(完全二叉樹(shù)、滿(mǎn)二叉樹(shù))概念圖解

① 滿(mǎn)二叉樹(shù)

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

② 完全二叉樹(shù)

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

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

③ 二叉查找樹(shù)

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

④ 紅黑樹(shù)

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

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

⑤ 平衡二叉樹(shù)

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

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

2、IP地址分類(lèi)

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

• A類(lèi)地址：以0開(kāi)頭
• B類(lèi)地址：以10開(kāi)頭
• C類(lèi)地址：以110開(kāi)頭
• D類(lèi)地址：以1110開(kāi)頭
• E類(lèi)地址：以1111開(kāi)頭，保留地址

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

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

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

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

4、SYN攻擊是什么？

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

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

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

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

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

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

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

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

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

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

② wait/notify/notifyAll 都是對(duì)象鎖級(jí)別的操作，如果把 wait/notify/notifyAll 方法定義在 Thread 類(lèi)中，會(huì)帶來(lái)很大的局限性：

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

簡(jiǎn)單的說(shuō)，由于wait，notify和notifyAll都是鎖級(jí)別的操作，所以把他們定義在 Object 類(lèi)中因?yàn)殒i屬于對(duì)象。

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

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

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

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

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

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

9、如果提交時(shí)，線(xiàn)程池隊(duì)列滿(mǎn)，會(huì)發(fā)生什么？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

最新評(píng)論