為了使不同計(jì)算機(jī)廠家生產(chǎn)的計(jì)算機(jī)能夠相互通信，以便在更大的范圍內(nèi)建立計(jì)算機(jī)網(wǎng)絡(luò)，國際標(biāo)準(zhǔn)化組織（ISO）在1978年提出了“開放系統(tǒng)互聯(lián)參考模型”，即著名的OSI/RM模型（Open System Interconnection/Reference Model）。它將計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)的通信協(xié)議劃分為七層，自下而上依次為：物理層（Physics Layer）、數(shù)據(jù)鏈路層（Data Link Layer）、網(wǎng)絡(luò)層（Network Layer）、傳輸層（Transport Layer）、會(huì)話層（Session Layer）、表示層（Presentation Layer）、應(yīng)用層（Application Layer）。其中第四層完成數(shù)據(jù)傳送服務(wù)，上面三層面向用戶。

除了標(biāo)準(zhǔn)的OSI七層模型以外，常見的網(wǎng)絡(luò)層次劃分還有TCP/IP四層協(xié)議以及TCP/IP五層協(xié)議，它們之間的對(duì)應(yīng)關(guān)系如下圖所示：

2、TCP／IP協(xié)議、三次握手和四次握手

TCP/IP協(xié)議是Internet最基本的協(xié)議、Internet國際互聯(lián)網(wǎng)絡(luò)的基礎(chǔ)，由網(wǎng)絡(luò)層的IP協(xié)議和傳輸層的TCP協(xié)議組成。通俗而言：TCP負(fù)責(zé)發(fā)現(xiàn)傳輸?shù)膯栴}，一有問題就發(fā)出信號(hào)，要求重新傳輸，直到所有數(shù)據(jù)安全正確地傳輸?shù)侥康牡亍６鳬P是給因特網(wǎng)的每一臺(tái)聯(lián)網(wǎng)設(shè)備規(guī)定一個(gè)地址。

TCP協(xié)議中有著名的三次握手和四次握手規(guī)則，如下圖所示：

注：seq:''sequance''序列號(hào)；ack:''acknowledge''確認(rèn)號(hào)；SYN:''synchronize''請(qǐng)求同步標(biāo)志；；ACK:''acknowledge''確認(rèn)標(biāo)志''；FIN：''Finally''結(jié)束標(biāo)志。

TCP連接建立過程
首先Client端發(fā)送連接請(qǐng)求報(bào)文，Server段接受連接后回復(fù)ACK報(bào)文，并為這次連接分配資源。Client端接收到ACK報(bào)文后也向Server段發(fā)生ACK報(bào)文，并分配資源，這樣TCP連接就建立了。

TCP連接斷開過程
假設(shè)Client端發(fā)起中斷連接請(qǐng)求，也就是發(fā)送FIN報(bào)文。Server端接到FIN報(bào)文后，意思是說''我Client端沒有數(shù)據(jù)要發(fā)給你了''，但是如果你還有數(shù)據(jù)沒有發(fā)送完成，則不必急著關(guān)閉Socket，可以繼續(xù)發(fā)送數(shù)據(jù)。所以你先發(fā)送ACK，''告訴Client端，你的請(qǐng)求我收到了，但是我還沒準(zhǔn)備好，請(qǐng)繼續(xù)你等我的消息''。這個(gè)時(shí)候Client端就進(jìn)入FIN_WAIT狀態(tài)，繼續(xù)等待Server端的FIN報(bào)文。當(dāng)Server端確定數(shù)據(jù)已發(fā)送完成，則向Client端發(fā)送FIN報(bào)文，''告訴Client端，好了，我這邊數(shù)據(jù)發(fā)完了，準(zhǔn)備好關(guān)閉連接了''。Client端收到FIN報(bào)文后，''就知道可以關(guān)閉連接了，但是他還是不相信網(wǎng)絡(luò)，怕Server端不知道要關(guān)閉，所以發(fā)送ACK后進(jìn)入TIME_WAIT狀態(tài)，如果Server端沒有收到ACK則可以重傳?！?，Server端收到ACK后，''就知道可以斷開連接了''。Client端等待了2MSL后依然沒有收到回復(fù)，則證明Server端已正常關(guān)閉，那好，我Client端也可以關(guān)閉連接了。Ok，TCP連接就這樣關(guān)閉了！

為什么要三次握手？
在只有兩次“握手”的情形下，假設(shè)Client想跟Server建立連接，但是卻因?yàn)橹型具B接請(qǐng)求的數(shù)據(jù)報(bào)丟失了，故Client端不得不重新發(fā)送一遍；這個(gè)時(shí)候Server端僅收到一個(gè)連接請(qǐng)求，因此可以正常的建立連接。但是，有時(shí)候Client端重新發(fā)送請(qǐng)求不是因?yàn)閿?shù)據(jù)報(bào)丟失了，而是有可能數(shù)據(jù)傳輸過程因?yàn)榫W(wǎng)絡(luò)并發(fā)量很大在某結(jié)點(diǎn)被阻塞了，這種情形下Server端將先后收到2次請(qǐng)求，并持續(xù)等待兩個(gè)Client請(qǐng)求向他發(fā)送數(shù)據(jù)...問題就在這里，Cient端實(shí)際上只有一次請(qǐng)求，而Server端卻有2個(gè)響應(yīng)，極端的情況可能由于Client端多次重新發(fā)送請(qǐng)求數(shù)據(jù)而導(dǎo)致Server端最后建立了N多個(gè)響應(yīng)在等待，因而造成極大的資源浪費(fèi)！所以，“三次握手”很有必要！

為什么要四次握手？
試想一下，假如現(xiàn)在你是客戶端你想斷開跟Server的所有連接該怎么做？第一步，你自己先停止向Server端發(fā)送數(shù)據(jù)，并等待Server的回復(fù)。但事情還沒有完，雖然你自身不往Server發(fā)送數(shù)據(jù)了，但是因?yàn)槟銈冎耙呀?jīng)建立好平等的連接了，所以此時(shí)他也有主動(dòng)權(quán)向你發(fā)送數(shù)據(jù)；故Server端還得終止主動(dòng)向你發(fā)送數(shù)據(jù)，并等待你的確認(rèn)。其實(shí)，說白了就是保證雙方的一個(gè)合約的完整執(zhí)行！

3、進(jìn)程與線程

定義

進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng),進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位.

線程：當(dāng)一個(gè)進(jìn)程內(nèi)有多個(gè)線程時(shí)，線程的程序是其所屬進(jìn)程的一部分，表示進(jìn)程中的一個(gè)控制點(diǎn)，執(zhí)行一系列的指令。同屬一個(gè)進(jìn)程的其他的線程共享進(jìn)程所擁有的全部資源（包括地址空間）。它是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位.線程自己基本上不擁有系統(tǒng)資源,只擁有一點(diǎn)在運(yùn)行中必不可少的資源(如程序計(jì)數(shù)器,一組寄存器和棧)，因此，它的創(chuàng)建、撤銷、切換所需要的時(shí)空開銷比進(jìn)程要小。線程的引入可進(jìn)一步提高系統(tǒng)的并發(fā)性。

區(qū)別

進(jìn)程和線程的主要差別在于它們是不同的操作系統(tǒng)資源管理方式。進(jìn)程有獨(dú)立的地址空間，一個(gè)進(jìn)程崩潰后，在保護(hù)模式下不會(huì)對(duì)其它進(jìn)程產(chǎn)生影響，而線程只是一個(gè)進(jìn)程中的不同執(zhí)行路徑。線程有自己的堆棧和局部變量，但線程之間沒有單獨(dú)的地址空間，一個(gè)線程死掉就等于整個(gè)進(jìn)程死掉，所以多進(jìn)程的程序要比多線程的程序健壯，但在進(jìn)程切換時(shí)，耗費(fèi)資源較大，效率要差一些。但對(duì)于一些要求同時(shí)進(jìn)行并且又要共享某些變量的并發(fā)操作，只能用線程，不能用進(jìn)程。

調(diào)度分派：線程是可調(diào)度分派的工作單元，它包括處理器上下文環(huán)境和棧中自己的數(shù)據(jù)區(qū)域。線程順序執(zhí)行，并且可以中斷，這樣處理器可以轉(zhuǎn)到另一個(gè)線程。在有線程的系統(tǒng)中，進(jìn)程不再是可調(diào)度分派的工作單元。
資源擁有：進(jìn)程是一個(gè)或多個(gè)線程和相關(guān)資源的集合。線程基本不擁有資源，它的運(yùn)行資源取決于其所屬的進(jìn)程。
地址空間：不同進(jìn)程的地址空間是相互獨(dú)立的，而同一個(gè)進(jìn)程的各線程共享同一地址空間。
一個(gè)進(jìn)程可包含一個(gè)或多個(gè)線程，反過來則不然。一個(gè)進(jìn)程中的線程在另一個(gè)進(jìn)程中時(shí)不可見的。
通信關(guān)系：進(jìn)程間的通信必須使用操作系統(tǒng)提供的進(jìn)程間通信機(jī)制，而同一個(gè)進(jìn)程中的各線程間可以通過直接讀寫數(shù)據(jù)段來進(jìn)行通信。當(dāng)然，同一個(gè)進(jìn)程中的各線程間的通信也需要同步和互斥手段的輔助，以確保數(shù)據(jù)一致性。

4、進(jìn)程調(diào)度算法

（1）先來先服務(wù)（FCFS，F(xiàn)irst-Come-First-Served）: 此算法的原則是按照作業(yè)到達(dá)后備作業(yè)隊(duì)列（或進(jìn)程進(jìn)入就緒隊(duì)列）的先后次序來選擇作業(yè)（或進(jìn)程）。
（2）短作業(yè)優(yōu)先（SJF,Shortest Process Next）：這種調(diào)度算法主要用于作業(yè)調(diào)度，它從作業(yè)后備隊(duì)列中挑選所需運(yùn)行時(shí)間（估計(jì)值）最短的作業(yè)進(jìn)入主存運(yùn)行。
（3）時(shí)間片輪轉(zhuǎn)調(diào)度算法（RR，Round-Robin）：當(dāng)某個(gè)進(jìn)程執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送就緒隊(duì)列的末尾，等待分配下一時(shí)間片再執(zhí)行。然后把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片處理機(jī)執(zhí)行時(shí)間。
（4）高響應(yīng)比優(yōu)先（HRRN，Highest Response Ratio Next）: 按照高響應(yīng)比（（已等待時(shí)間＋要求運(yùn)行時(shí)間）/ 要求運(yùn)行時(shí)間）優(yōu)先的原則，在每次選擇作業(yè)投入運(yùn)行時(shí)，先計(jì)算此時(shí)后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比RP然后選擇其值最大的作業(yè)投入運(yùn)行。
（5）優(yōu)先權(quán)(Priority)調(diào)度算法: 按照進(jìn)程的優(yōu)先權(quán)大小來調(diào)度，使高優(yōu)先權(quán)進(jìn)程得到優(yōu)先處理的調(diào)度策略稱為優(yōu)先權(quán)調(diào)度算法。
（6） 多級(jí)隊(duì)列調(diào)度算法：多隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同，將就緒隊(duì)列再分為若干個(gè)子隊(duì)列，所有的作業(yè)（或進(jìn)程）按其性質(zhì)排入相應(yīng)的隊(duì)列中，而不同的就緒隊(duì)列采用不同的調(diào)度算法。

5、死鎖

什么是死鎖

在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程持有某種資源而又都等待別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，在未改變這種狀態(tài)之前都不能向前推進(jìn)，稱這一組進(jìn)程產(chǎn)生了死鎖。通俗地講，就是兩個(gè)或多個(gè)進(jìn)程被無限期地阻塞、相互等待的一種狀態(tài)。

產(chǎn)生死鎖的原因

死鎖產(chǎn)生的原因主要是：1、 系統(tǒng)資源不足；2、進(jìn)程推進(jìn)順序非法。
產(chǎn)生死鎖有四個(gè)必要條件：
（1）互斥：一個(gè)資源每次只能被一個(gè)進(jìn)程使用；
（2）不可搶占進(jìn)程已獲得的資源，在未使用完之前，不能強(qiáng)行剝奪；
（3）占有并等待一個(gè)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已獲得的資源保持不放；
（4）環(huán)形等待若干進(jìn)程之間形成一種首尾相接的循環(huán)等待資源關(guān)系。
這四個(gè)條件是死鎖的必要條件，只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會(huì)發(fā)生死鎖。

如何避免死鎖

理解了死鎖的原因，尤其是產(chǎn)生死鎖的四個(gè)必要條件，就可以最大可能地避免、預(yù)防和解除死鎖。所以，在系統(tǒng)設(shè)計(jì)、進(jìn)程調(diào)度等方面注意如何不讓這四個(gè)必要條件成立，如何確定資源的合理分配算法，避免進(jìn)程永久占據(jù)系統(tǒng)資源。此外，也要防止進(jìn)程在處于等待狀態(tài)的情況下占用資源。因此，對(duì)資源的分配要給予合理的規(guī)劃。

下面介紹幾種常見的死鎖解決方法：

設(shè)置加鎖順序
當(dāng)多個(gè)線程需要相同的一些鎖，但是按照不同的順序加鎖，死鎖就很容易發(fā)生。如果能確保所有的線程都是按照相同的順序獲得鎖，那么死鎖就不會(huì)發(fā)生?？聪旅孢@個(gè)例子：

如果一個(gè)線程（比如線程3）需要一些鎖，那么它必須按照確定的順序獲取鎖。它只有獲得了從順序上排在前面的鎖之后，才能獲取后面的鎖。例如，線程2和線程3只有在獲取了鎖A之后才能嘗試獲取鎖C(譯者注：獲取鎖A是獲取鎖C的必要條件)。因?yàn)榫€程1已經(jīng)擁有了鎖A，所以線程2和3需要一直等到鎖A被釋放。然后在它們嘗試對(duì)B或C加鎖之前，必須成功地對(duì)A加了鎖。

按照順序加鎖是一種有效的死鎖預(yù)防機(jī)制。但是，這種方式需要你事先知道所有可能會(huì)用到的鎖，但總有些時(shí)候是無法預(yù)知的。

加鎖時(shí)限
另外一個(gè)可以避免死鎖的方法是在嘗試獲取鎖的時(shí)候加一個(gè)超時(shí)時(shí)間，這也就意味著在嘗試獲取鎖的過程中若超過了這個(gè)時(shí)限該線程則放棄對(duì)該鎖請(qǐng)求。若一個(gè)線程沒有在給定的時(shí)限內(nèi)成功獲得所有需要的鎖，則會(huì)進(jìn)行回退并釋放所有已經(jīng)獲得的鎖，然后等待一段隨機(jī)的時(shí)間再重試。這段隨機(jī)的等待時(shí)間讓其它線程有機(jī)會(huì)嘗試獲取相同的這些鎖，并且讓該應(yīng)用在沒有獲得鎖的時(shí)候可以繼續(xù)運(yùn)行。

死鎖檢測

死鎖檢測是一個(gè)更好的死鎖預(yù)防機(jī)制，它主要是針對(duì)那些不可能實(shí)現(xiàn)按序加鎖并且鎖超時(shí)也不可行的場景。每當(dāng)一個(gè)線程獲得了鎖，會(huì)在線程和鎖相關(guān)的數(shù)據(jù)結(jié)構(gòu)中（map、graph等等）將其記下。除此之外，每當(dāng)有線程請(qǐng)求鎖，也需要記錄在這個(gè)數(shù)據(jù)結(jié)構(gòu)中。

當(dāng)一個(gè)線程請(qǐng)求鎖失敗時(shí)，這個(gè)線程可以遍歷鎖的關(guān)系圖看看是否有死鎖發(fā)生。例如，線程A請(qǐng)求鎖7，但是鎖7這個(gè)時(shí)候被線程B持有，這時(shí)線程A就可以檢查一下線程B是否已經(jīng)請(qǐng)求了線程A當(dāng)前所持有的鎖。如果線程B確實(shí)有這樣的請(qǐng)求，那么就是發(fā)生了死鎖（線程A擁有鎖1，請(qǐng)求鎖7；線程B擁有鎖7，請(qǐng)求鎖1）。

當(dāng)然，死鎖一般要比兩個(gè)線程互相持有對(duì)方的鎖這種情況要復(fù)雜的多。線程A等待線程B，線程B等待線程C，線程C等待線程D，線程D又在等待線程A。線程A為了檢測死鎖，它需要遞進(jìn)地檢測所有被B請(qǐng)求的鎖。從線程B所請(qǐng)求的鎖開始，線程A找到了線程C，然后又找到了線程D，發(fā)現(xiàn)線程D請(qǐng)求的鎖被線程A自己持有著。這是它就知道發(fā)生了死鎖。

下面是一幅關(guān)于四個(gè)線程（A,B,C和D）之間鎖占有和請(qǐng)求的關(guān)系圖。像這樣的數(shù)據(jù)結(jié)構(gòu)就可以被用來檢測死鎖。

那么當(dāng)檢測出死鎖時(shí)，這些線程該做些什么呢？

一個(gè)可行的做法是釋放所有鎖，回退，并且等待一段隨機(jī)的時(shí)間后重試。這個(gè)和簡單的加鎖超時(shí)類似，不一樣的是只有死鎖已經(jīng)發(fā)生了才回退，而不會(huì)是因?yàn)榧渔i的請(qǐng)求超時(shí)了。雖然有回退和等待，但是如果有大量的線程競爭同一批鎖，它們還是會(huì)重復(fù)地死鎖（編者注：原因同超時(shí)類似，不能從根本上減輕競爭）。

一個(gè)更好的方案是給這些線程設(shè)置優(yōu)先級(jí)，讓一個(gè)（或幾個(gè)）線程回退，剩下的線程就像沒發(fā)生死鎖一樣繼續(xù)保持著它們需要的鎖。如果賦予這些線程的優(yōu)先級(jí)是固定不變的，同一批線程總是會(huì)擁有更高的優(yōu)先級(jí)。為避免這個(gè)問題，可以在死鎖發(fā)生的時(shí)候設(shè)置隨機(jī)的優(yōu)先級(jí)。

6、高速緩存Cache

Cache的原理

Cache，即高速緩存，是介于CPU和內(nèi)存之間的高速小容量存儲(chǔ)器。在金字塔式存儲(chǔ)體系中它位于自頂向下的第二層，僅次于CPU寄存器。其容量遠(yuǎn)小于內(nèi)存，但速度卻可以接近CPU的頻率。
當(dāng)CPU發(fā)出內(nèi)存訪問請(qǐng)求時(shí)，會(huì)先查看 Cache 內(nèi)是否有請(qǐng)求數(shù)據(jù)。
如果存在（命中），則直接返回該數(shù)據(jù)；
如果不存在（失效），再去訪問內(nèi)存 —— 先把內(nèi)存中的相應(yīng)數(shù)據(jù)載入緩存，再將其返回處理器。
提供“高速緩存”的目的是讓數(shù)據(jù)訪問的速度適應(yīng)CPU的處理速度，通過減少訪問內(nèi)存的次數(shù)來提高數(shù)據(jù)存取的速度。

Cache 技術(shù)所依賴的原理是”程序執(zhí)行與數(shù)據(jù)訪問的局部性原理“，這種局部性表現(xiàn)在兩個(gè)方面：
時(shí)間局部性：如果程序中的某條指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行，如果某數(shù)據(jù)被訪問過，不久以后該數(shù)據(jù)可能再次被訪問。
空間局部性：一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，這是因?yàn)橹噶罨驍?shù)據(jù)通常是順序存放的。
時(shí)間局部性是通過將近來使用的指令和數(shù)據(jù)保存到Cache中實(shí)現(xiàn)?？臻g局部性通常是使用較大的高速緩存，并將 預(yù)取機(jī)制 集成到高速緩存控制邏輯中來實(shí)現(xiàn)。

Cache替換策略(頁面置換算法)

Cache的容量是有限的，當(dāng)Cache的空間都被占滿后，如果再次發(fā)生緩存失效，就必須選擇一個(gè)緩存塊來替換掉。常用的替換策略有以下幾種：
（1）最佳置換算法（Optimal）：即選擇那些永不使用的，或者是在最長時(shí)間內(nèi)不再被訪問的頁面置換出去。（它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)）。
（2）先進(jìn)先出置換算法FIFO：該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。
（3）最近最久未使用置換算法LRU（Least Recently Used）：該算法是選擇最近最久未使用的頁面予以淘汰，系統(tǒng)在每個(gè)頁面設(shè)置一個(gè)訪問字段，用以記錄這個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間T，當(dāng)要淘汰一個(gè)頁面時(shí)，選擇T最大的頁面。
（4）Clock置換算法：也叫最近未用算法NRU（Not RecentlyUsed）。該算法為每個(gè)頁面設(shè)置一位訪問位，將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁被訪問時(shí)，其訪問位置“1”。在選擇一頁淘汰時(shí)，就檢查其訪問位，如果是“0”，就選擇該頁換出；若為“1”，則重新置為“0”，暫不換出該頁，在循環(huán)隊(duì)列中檢查下一個(gè)頁面，直到訪問位為“0”的頁面為止。由于該算法只有一位訪問位，只能用它表示該頁是否已經(jīng)使用過，而置換時(shí)是將未使用過的頁面換出去，所以把該算法稱為最近未用算法。
（5）最少使用置換算法LFU：該算法選擇最近時(shí)期使用最少的頁面作為淘汰頁。

7、最近最久未使用置換算法LRU的JAVA實(shí)現(xiàn)

之前面頭條的暑期實(shí)習(xí)生時(shí)曾經(jīng)考過這道題，因此這里整理一下。

思路分析

對(duì)一個(gè)Cache的操作無非三種：插入(insert)、替換(replace)、查找（lookup）。
為了能夠快速刪除最久沒有訪問的數(shù)據(jù)項(xiàng)和插入最新的數(shù)據(jù)項(xiàng)，我們使用 雙向鏈表 連接Cache中的數(shù)據(jù)項(xiàng)，并且保證鏈表維持?jǐn)?shù)據(jù)項(xiàng)從最近訪問到最舊訪問的順序。
插入：當(dāng)Cache未滿時(shí)，新的數(shù)據(jù)項(xiàng)只需插到雙鏈表頭部即可。時(shí)間復(fù)雜度為O(1).
替換：當(dāng)Cache已滿時(shí)，將新的數(shù)據(jù)項(xiàng)插到雙鏈表頭部，并刪除雙鏈表的尾結(jié)點(diǎn)即可。時(shí)間復(fù)雜度為O(1).
查找：每次數(shù)據(jù)項(xiàng)被查詢到時(shí)，都將此數(shù)據(jù)項(xiàng)移動(dòng)到鏈表頭部。
經(jīng)過分析，我們知道使用雙向鏈表可以保證插入和替換的時(shí)間復(fù)雜度是O(1)，但查詢的時(shí)間復(fù)雜度是O(n)，因?yàn)樾枰獙?duì)雙鏈表進(jìn)行遍歷。為了讓查找效率也達(dá)到O(1)，很自然的會(huì)想到使用 hash table 。

具體的實(shí)現(xiàn)代碼如下：

對(duì)于上述代碼的解釋如下：

get：通過get方法得到一個(gè)頁面之后，要將這個(gè)頁面先從鏈表中進(jìn)行刪除，然后放入到鏈表的頭部。

remove：執(zhí)行刪除一個(gè)頁面的操作，此時(shí)要判斷刪除的key是頭部節(jié)點(diǎn)和尾部節(jié)點(diǎn)的兩種情況。

setHead：設(shè)置頭節(jié)點(diǎn)。要注意的情況是當(dāng)鏈表為空時(shí)，要同時(shí)設(shè)置head和end的值

set：更新緩存，如果key已經(jīng)存在，則進(jìn)行替換并放到鏈表的頭部，如果key不存在，則插入到鏈表中，此時(shí)又要區(qū)分緩存的容量是否已滿兩種情況。