1.實(shí)現(xiàn)一個(gè)保證迭代順序的HashMap。
答：Java里面有個(gè)容器LinkedHashMap, 它能實(shí)現(xiàn)按照插入的順序輸出結(jié)果。
它的原理也是維護(hù)一張表，但它是鏈表，并且hashmap中維護(hù)指向鏈表的指針，這樣可以快速定位鏈表中的元素進(jìn)行刪除。
它的時(shí)間復(fù)雜度也是O(n), 空間上要比上面少些
2.說一說排序算法，穩(wěn)定性，復(fù)雜度。
排序算法比較表格
| 排序算法 | 平均時(shí)間復(fù)雜度 | 最壞時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 是否穩(wěn)定 |
|---|---|---|---|---|
| 冒泡排序 | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | 是 |
| 選擇排序 | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | 不是 |
| 直接插入排序 | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | 是 |
| 歸并排序 | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O（n）O（n） | 是 |
| 快速排序 | O(nlogn)O(nlogn) | O（n2）O（n2） | O（logn）O（logn） | 不是 |
| 堆排序 | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O（1）O（1） | 不是 |
| 希爾排序 | O(nlogn)O(nlogn) | O（ns）O（ns） | O（1）O（1） | 不是 |
| 計(jì)數(shù)排序 | O(n+k)O(n+k) | O(n+k)O(n+k) | O(n+k)O(n+k) | 是 |
| 基數(shù)排序 | O(N?M)O(N?M) | O(N?M)O(N?M) | O(M)O(M) | 是 |
原理理解
1 冒泡排序
2 選擇排序
3 插入排序
4 歸并排序
5 快速排序
6 堆排序
注意！?。?shù)組從1開始，1~n
7 希爾排序
8 桶排序（基數(shù)排序和基數(shù)排序的思想）
[圖片上傳中...(image-19ec86-1553847936802-7)]
9 計(jì)數(shù)排序
圖解
10 基數(shù)排序
對(duì)a[n]按照個(gè)位0~9進(jìn)行桶排序：
對(duì)b[n]進(jìn)行累加得到c[n]，用于b[n]中重復(fù)元素計(jì)數(shù)
！?。[n]中的元素為temp中的位置?。。√S的用++補(bǔ)上：
temp數(shù)組為排序后的數(shù)組，寫回a[n]。temp為按順序倒出桶中的數(shù)據(jù)（聯(lián)合b[n],c[n],a[n]得到），重復(fù)元素按順序輸出：
3.TCP如何保證可靠傳輸？三次握手過程？
答：TCP發(fā)送的報(bào)文段是交給IP層傳送的，但I(xiàn)P層只能提供盡最大努力交付的服務(wù)，也就是說，TCP下面的網(wǎng)絡(luò)所提供的是不可靠的傳輸。因此，TCP采用了一些適當(dāng)?shù)拇胧﹣硖峁┛煽康膫鬏?，使得兩個(gè)傳輸層直接的通信變得可靠。
TCP為了提供可靠傳輸：
（1）首先，采用三次握手來建立TCP連接，四次握手來釋放TCP連接，從而保證建立的傳輸信道是可靠的。
（2）其次，TCP采用了連續(xù)ARQ協(xié)議（回退N，Go-back-N；超時(shí)自動(dòng)重傳）來保證數(shù)據(jù)傳輸?shù)恼_性，使用滑動(dòng)窗口協(xié)議來保證接收方能夠及時(shí)處理所接收到的數(shù)據(jù)，進(jìn)行流量控制。
（3）最后，TCP使用慢開始、擁塞避免、快重傳和快恢復(fù)來進(jìn)行擁塞控制，避免網(wǎng)絡(luò)擁塞。
三次握手：
TCP需要三次握手才能建立連接，整個(gè)過程如下圖所示：
假設(shè)A運(yùn)行的是TCP客戶端進(jìn)程，而B運(yùn)行的是TCP服務(wù)端進(jìn)程。最開始的時(shí)候兩端的TCP進(jìn)程都處于ClOSED（關(guān)閉）狀態(tài)。
這時(shí)候，A主動(dòng)打開連接，而B被動(dòng)打開連接，B在打開連接之后進(jìn)入LISTEN（收聽）狀態(tài)。
（1）第一次握手
A的TCP客戶進(jìn)程向B發(fā)出建立連接請(qǐng)求報(bào)文段，其中SYN（同步位）=1，ACK（確認(rèn)位）=0，seq（序號(hào)）=x。
TCP規(guī)定，當(dāng)報(bào)文段的SYN=1且ACK=0時(shí)，表明這是一個(gè)請(qǐng)求建立連接的；SYN報(bào)文段（SYN=1的報(bào)文段）不能攜帶數(shù)據(jù)，但是要消耗掉一個(gè)序號(hào)。
在A發(fā)送完畢之后，A的TCP客戶端進(jìn)程進(jìn)入SYN-SENT（同步已發(fā)送）狀態(tài)。
（2）第二次握手
B在收到連接請(qǐng)求報(bào)文段之后，如果同意建立連接，則向A發(fā)送確認(rèn)報(bào)文段。其中SYN=1，ACK=1，ack（確認(rèn)號(hào)）=x+1，同時(shí)設(shè)置自己的初始序號(hào)seq=y。
TCP規(guī)定，當(dāng)報(bào)文段的SYN=1且ACK=1時(shí)，表明這是一個(gè)同一建立連接響應(yīng)報(bào)文段；這個(gè)報(bào)文段也不能攜帶數(shù)據(jù)，同樣需要消耗掉一個(gè)序號(hào)。
在B發(fā)送完畢之后，B的TCP服務(wù)端進(jìn)程進(jìn)入SYN-RCVD（同步收到）狀態(tài)。
（3）第三次握手
A在收到B的確認(rèn)報(bào)文段之后，還需要向B給出確認(rèn)報(bào)文段。其中ACK=1，seq=x+1，ack=y+1。
TCP規(guī)定，這個(gè)ACK報(bào)文段可以攜帶數(shù)據(jù)；如果不攜帶數(shù)據(jù)則不消耗序號(hào)，即A下一個(gè)數(shù)據(jù)報(bào)文段的序號(hào)仍然是seq=x+1。
在A發(fā)送完畢之后，A的TCP客戶端進(jìn)程進(jìn)入ESTABLISHED（已建立連接）狀態(tài)；B在接收到A的確認(rèn)報(bào)文段之后，B的服務(wù)端進(jìn)程也進(jìn)入ESTABLISHED（已建立連接）狀態(tài)。
二、三次握手的原因
為什么A還需要發(fā)送一次確認(rèn)，進(jìn)行第三次握手呢？主要是為了防止已失效的請(qǐng)求連接報(bào)文段突然又傳送到了B，因而產(chǎn)生錯(cuò)誤。
原因如下：
先假如出現(xiàn)了一種異常情況，即A發(fā)出的第一個(gè)連接請(qǐng)求報(bào)文段因?yàn)樵谀承┚W(wǎng)絡(luò)節(jié)點(diǎn)上滯留了。由于超時(shí)重傳，于是A又向B發(fā)起請(qǐng)求并成功建立了連接，在傳輸完數(shù)據(jù)之后，AB同之間釋放了連接。
而在A和B已經(jīng)釋放連接之后，那個(gè)在網(wǎng)絡(luò)上滯留的報(bào)文段又達(dá)到了B。這時(shí)候，B接收到報(bào)文以為是A發(fā)起的新的一次建立連接的請(qǐng)求，于是就向A發(fā)出確認(rèn)建立連接報(bào)文段。而A此時(shí)并沒有發(fā)起建立連接的請(qǐng)求，于是不予理睬。但是B以為新的連接已經(jīng)建立，一直等待A發(fā)送數(shù)據(jù)，于是B的許多資源就浪費(fèi)了。
