1臼朗、網(wǎng)絡(luò)層次劃分

為了使不同計算機(jī)廠家生產(chǎn)的計算機(jī)能夠相互通信，以便在更大的范圍內(nèi)建立計算機(jī)網(wǎng)絡(luò)，國際標(biāo)準(zhǔn)化組織（ISO）在1978年提出了“開放系統(tǒng)互聯(lián)參考模型”，即著名的OSI/RM模型（Open System Interconnection/Reference Model）。它將計算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)的通信協(xié)議劃分為七層堕绩，自下而上依次為：物理層（Physics Layer）、數(shù)據(jù)鏈路層（Data Link Layer）、網(wǎng)絡(luò)層（Network Layer）专执、傳輸層（Transport Layer）痊末、會話層（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é)議罗心，它們之間的對應(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ā)出信號狼电，要求重新傳輸，直到所有數(shù)據(jù)安全正確地傳輸?shù)侥康牡叵阴濉６鳬P是給因特網(wǎng)的每一臺聯(lián)網(wǎng)設(shè)備規(guī)定一個地址肩碟。

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

注：seq:"sequance"序列號盈匾；ack:"acknowledge"確認(rèn)號腾务；SYN:"synchronize"請求同步標(biāo)志毕骡；削饵；ACK:"acknowledge"確認(rèn)標(biāo)志"；FIN："Finally"結(jié)束標(biāo)志未巫。

TCP連接建立過程
首先Client端發(fā)送連接請求報文窿撬，Server段接受連接后回復(fù)ACK報文，并為這次連接分配資源叙凡。Client端接收到ACK報文后也向Server段發(fā)生ACK報文劈伴，并分配資源，這樣TCP連接就建立了握爷。

TCP連接斷開過程
假設(shè)Client端發(fā)起中斷連接請求跛璧，也就是發(fā)送FIN報文。Server端接到FIN報文后新啼，意思是說"我Client端沒有數(shù)據(jù)要發(fā)給你了"追城，但是如果你還有數(shù)據(jù)沒有發(fā)送完成，則不必急著關(guān)閉Socket燥撞，可以繼續(xù)發(fā)送數(shù)據(jù)座柱。所以你先發(fā)送ACK迷帜，"告訴Client端，你的請求我收到了色洞，但是我還沒準(zhǔn)備好戏锹，請繼續(xù)你等我的消息"。這個時候Client端就進(jìn)入FIN_WAIT狀態(tài)火诸，繼續(xù)等待Server端的FIN報文锦针。當(dāng)Server端確定數(shù)據(jù)已發(fā)送完成，則向Client端發(fā)送FIN報文置蜀，"告訴Client端伞插，好了，我這邊數(shù)據(jù)發(fā)完了盾碗，準(zhǔn)備好關(guān)閉連接了"媚污。Client端收到FIN報文后，"就知道可以關(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接請求的數(shù)據(jù)報丟失了零院，故Client端不得不重新發(fā)送一遍溉跃；這個時候Server端僅收到一個連接請求，因此可以正常的建立連接告抄。但是撰茎，有時候Client端重新發(fā)送請求不是因?yàn)閿?shù)據(jù)報丟失了，而是有可能數(shù)據(jù)傳輸過程因?yàn)榫W(wǎng)絡(luò)并發(fā)量很大在某結(jié)點(diǎn)被阻塞了玄妈，這種情形下Server端將先后收到2次請求乾吻，并持續(xù)等待兩個Client請求向他發(fā)送數(shù)據(jù)...問題就在這里髓梅，Cient端實(shí)際上只有一次請求，而Server端卻有2個響應(yīng)绎签，極端的情況可能由于Client端多次重新發(fā)送請求數(shù)據(jù)而導(dǎo)致Server端最后建立了N多個響應(yīng)在等待枯饿，因而造成極大的資源浪費(fèi)！所以诡必，“三次握手”很有必要奢方！

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

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

定義

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

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

區(qū)別

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

調(diào)度分派：線程是可調(diào)度分派的工作單元圆雁，它包括處理器上下文環(huán)境和棧中自己的數(shù)據(jù)區(qū)域。線程順序執(zhí)行帆谍，并且可以中斷伪朽，這樣處理器可以轉(zhuǎn)到另一個線程。在有線程的系統(tǒng)中汛蝙，進(jìn)程不再是可調(diào)度分派的工作單元驱负。
資源擁有：進(jìn)程是一個或多個線程和相關(guān)資源的集合。線程基本不擁有資源患雇，它的運(yùn)行資源取決于其所屬的進(jìn)程跃脊。
地址空間：不同進(jìn)程的地址空間是相互獨(dú)立的，而同一個進(jìn)程的各線程共享同一地址空間苛吱。
一個進(jìn)程可包含一個或多個線程酪术，反過來則不然。一個進(jìn)程中的線程在另一個進(jìn)程中時不可見的翠储。
通信關(guān)系：進(jìn)程間的通信必須使用操作系統(tǒng)提供的進(jìn)程間通信機(jī)制绘雁，而同一個進(jìn)程中的各線程間可以通過直接讀寫數(shù)據(jù)段來進(jìn)行通信。當(dāng)然援所，同一個進(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)行時間（估計值）最短的作業(yè)進(jìn)入主存運(yùn)行杠娱。
（3）時間片輪轉(zhuǎn)調(diào)度算法（RR，Round-Robin）：當(dāng)某個進(jìn)程執(zhí)行的時間片用完時谱煤，調(diào)度程序便停止該進(jìn)程的執(zhí)行摊求，并將它送就緒隊(duì)列的末尾，等待分配下一時間片再執(zhí)行刘离。然后把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程室叉，同時也讓它執(zhí)行一個時間片睹栖。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時間內(nèi)茧痕，均能獲得一時間片處理機(jī)執(zhí)行時間野来。
（4）高響應(yīng)比優(yōu)先（HRRN，Highest Response Ratio Next）: 按照高響應(yīng)比（（已等待時間＋要求運(yùn)行時間）/ 要求運(yùn)行時間）優(yōu)先的原則凿渊，在每次選擇作業(yè)投入運(yùn)行時梁只，先計算此時后備作業(yè)隊(duì)列中每個作業(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） 多級隊(duì)列調(diào)度算法：多隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同，將就緒隊(duì)列再分為若干個子隊(duì)列彩掐，所有的作業(yè)（或進(jìn)程）按其性質(zhì)排入相應(yīng)的隊(duì)列中构舟，而不同的就緒隊(duì)列采用不同的調(diào)度算法。

5堵幽、死鎖

什么是死鎖

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

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

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

如何避免死鎖

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

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

設(shè)置加鎖順序
當(dāng)多個線程需要相同的一些鎖铁蹈，但是按照不同的順序加鎖，死鎖就很容易發(fā)生众眨。如果能確保所有的線程都是按照相同的順序獲得鎖握牧，那么死鎖就不會發(fā)生∶淅妫看下面這個例子：

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

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

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

死鎖檢測

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

當(dāng)一個線程請求鎖失敗時，這個線程可以遍歷鎖的關(guān)系圖看看是否有死鎖發(fā)生锻霎。例如著角，線程A請求鎖7，但是鎖7這個時候被線程B持有量窘，這時線程A就可以檢查一下線程B是否已經(jīng)請求了線程A當(dāng)前所持有的鎖雇寇。如果線程B確實(shí)有這樣的請求，那么就是發(fā)生了死鎖（線程A擁有鎖1蚌铜，請求鎖7锨侯；線程B擁有鎖7，請求鎖1）冬殃。

當(dāng)然囚痴，死鎖一般要比兩個線程互相持有對方的鎖這種情況要復(fù)雜的多。線程A等待線程B审葬，線程B等待線程C深滚，線程C等待線程D，線程D又在等待線程A涣觉。線程A為了檢測死鎖痴荐，它需要遞進(jìn)地檢測所有被B請求的鎖。從線程B所請求的鎖開始官册，線程A找到了線程C生兆，然后又找到了線程D，發(fā)現(xiàn)線程D請求的鎖被線程A自己持有著膝宁。這是它就知道發(fā)生了死鎖匙瘪。

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

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

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

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

6辛燥、高速緩存Cache

Cache的原理

Cache，即高速緩存缝其，是介于CPU和內(nèi)存之間的高速小容量存儲器挎塌。在金字塔式存儲體系中它位于自頂向下的第二層，僅次于CPU寄存器内边。其容量遠(yuǎn)小于內(nèi)存榴都，但速度卻可以接近CPU的頻率。
當(dāng)CPU發(fā)出內(nèi)存訪問請求時漠其，會先查看 Cache 內(nèi)是否有請求數(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)在兩個方面：
時間局部性：如果程序中的某條指令一旦執(zhí)行纲岭，不久以后該指令可能再次執(zhí)行，如果某數(shù)據(jù)被訪問過线罕，不久以后該數(shù)據(jù)可能再次被訪問止潮。
空間局部性：一旦程序訪問了某個存儲單元，在不久之后钞楼，其附近的存儲單元也將被訪問喇闸，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，這是因?yàn)橹噶罨驍?shù)據(jù)通常是順序存放的燃乍。
時間局部性是通過將近來使用的指令和數(shù)據(jù)保存到Cache中實(shí)現(xiàn)唆樊。空間局部性通常是使用較大的高速緩存刻蟹，并將 預(yù)取機(jī)制 集成到高速緩存控制邏輯中來實(shí)現(xiàn)逗旁。

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

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

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

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

思路分析

對一個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ù)據(jù)項(xiàng)只需插到雙鏈表頭部即可。時間復(fù)雜度為O(1).
替換：當(dāng)Cache已滿時盈蛮，將新的數(shù)據(jù)項(xiàng)插到雙鏈表頭部废菱，并刪除雙鏈表的尾結(jié)點(diǎn)即可。時間復(fù)雜度為O(1).
查找：每次數(shù)據(jù)項(xiàng)被查詢到時抖誉，都將此數(shù)據(jù)項(xiàng)移動到鏈表頭部殊轴。
經(jīng)過分析，我們知道使用雙向鏈表可以保證插入和替換的時間復(fù)雜度是O(1)袒炉，但查詢的時間復(fù)雜度是O(n)旁理，因?yàn)樾枰獙﹄p鏈表進(jìn)行遍歷。為了讓查找效率也達(dá)到O(1)我磁，很自然的會想到使用 hash table 孽文。

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

import java.util.*

class Node{
    int key;
    int value;
    Node pre;
    Node next;

    public Node(int kye,int value){
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    int capacity;
    Map<Integer,Node> map = new HashMap<Integer,Node>();
    Node head = null;
    Node end = null;

    public LRUCache(int capacity){
        this.capacity = capacity;
    }

    public int get(int key){
        if(map.containsKey(key)){
            Node n = map.get(key);
            remove(n);
            setHead(n);
            return n.value;
        }
        return -1;
    }

    public void remove(Node n){
        if(n.pre != null){
            n.pre.next = n.next;
        }
        else{
            head = n.next;
        }

        if(n.next != null){
            n.next.pre = n.pre;
        }
        else{
            end = n.pre;
        }
    }

    public void setHead(Node n){
        n.next = head;
        n.pre = null;
        if(head!=null)
            head.pre = n;
        head = n;
        if(end == null){
            end = head;
        }
    }

    public void set(int key,int value){
        if(map.containsKey(key)){
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        }
        else{
            Node created = new Node(key,value);
            if(map.size() >= capacity){
                map.remove(end.key);
                remove(end);
                setHead(created);
            }
            else{
                setHead(created);
            }
            map.put(key,created);
        }
    }

}

對于上述代碼的解釋如下：
get：通過get方法得到一個頁面之后，要將這個頁面先從鏈表中進(jìn)行刪除夺艰，然后放入到鏈表的頭部芋哭。

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

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

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

參考文獻(xiàn)

1固以、計算機(jī)網(wǎng)絡(luò)基礎(chǔ)知識總結(jié)：https://www.cnblogs.com/maybe2030/p/4781555.html
2墩虹、多線程死鎖的產(chǎn)生以及如何避免死鎖：https://blog.csdn.net/ls5718/article/details/51896159
3嘱巾、操作系統(tǒng)面試知識點(diǎn)總結(jié)：https://blog.csdn.net/sunxianghuang/article/details/51883496
4、設(shè)計并實(shí)現(xiàn)一個LRU Cache (java)：https://blog.csdn.net/maoyeqiu/article/details/50452870