0x01：FIFO算法
FIFO（First in First out），先進(jìn)先出。其實(shí)在操作系統(tǒng)的設(shè)計(jì)理念中很多地方都利用到了先進(jìn)先出的思想，比如作業(yè)調(diào)度（先來先服務(wù)），為什么這個(gè)原則在很多地方都會用到呢？因?yàn)檫@個(gè)原則簡單、且符合人們的慣性思維，具備公平性，并且實(shí)現(xiàn)起來簡單，直接使用數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列即可實(shí)現(xiàn)。
在FIFO Cache設(shè)計(jì)中，核心原則就是：如果一個(gè)數(shù)據(jù)最先進(jìn)入緩存中，則應(yīng)該最早淘汰掉。也就是說，當(dāng)緩存滿的時(shí)候，應(yīng)當(dāng)把最先進(jìn)入緩存的數(shù)據(jù)給淘汰掉。在FIFO Cache中應(yīng)該支持以下操作;
get(key)：如果Cache中存在該key，則返回對應(yīng)的value值，否則，返回-1；
set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則將該key插入到到Cache中，若Cache已滿，則淘汰最早進(jìn)入Cache的數(shù)據(jù)。
舉個(gè)例子：假如Cache大小為3，訪問數(shù)據(jù)序列為set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)
則Cache中的數(shù)據(jù)變化為：
(1,1) set(1,1)
(1,1) (2,2) set(2,2)
(1,1) (2,2) (3,3) set(3,3)
(2,2) (3,3) (4,4) set(4,4)
(2,2) (3,3) (4,4) get(2)
(3,3) (4,4) (5,5) set(5,5)
那么利用什么數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)呢？
下面提供一種實(shí)現(xiàn)思路：
利用一個(gè)雙向鏈表保存數(shù)據(jù)，當(dāng)來了新的數(shù)據(jù)之后便添加到鏈表末尾，如果Cache存滿數(shù)據(jù)，則把鏈表頭部數(shù)據(jù)刪除，然后把新的數(shù)據(jù)添加到鏈表末尾。在訪問數(shù)據(jù)的時(shí)候，如果在Cache中存在該數(shù)據(jù)的話，則返回對應(yīng)的value值；否則返回-1。如果想提高訪問效率，可以利用hashmap來保存每個(gè)key在鏈表中對應(yīng)的位置。
0x02：LFU算法
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)使用次數(shù)很少，那么在將來一段時(shí)間內(nèi)被使用的可能性也很小”的思路。
注意LFU和LRU算法的不同之處，LRU的淘汰規(guī)則是基于訪問時(shí)間，而LFU是基于訪問次數(shù)的。舉個(gè)簡單的例子：
假設(shè)緩存大小為3，數(shù)據(jù)訪問序列為set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，
則在set(4,4)時(shí)對于LFU算法應(yīng)該淘汰(3,3)，而LRU應(yīng)該淘汰(1,1)。
那么LFU Cache應(yīng)該支持的操作為：
get(key)：如果Cache中存在該key，則返回對應(yīng)的value值，否則，返回-1；
set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則將該key插入到到Cache中，若Cache已滿，則淘汰最少訪問的數(shù)據(jù)。
為了能夠淘汰最少使用的數(shù)據(jù)，因此LFU算法最簡單的一種設(shè)計(jì)思路就是 利用一個(gè)數(shù)組存儲 數(shù)據(jù)項(xiàng)，用hashmap存儲每個(gè)數(shù)據(jù)項(xiàng)在數(shù)組中對應(yīng)的位置，然后為每個(gè)數(shù)據(jù)項(xiàng)設(shè)計(jì)一個(gè)訪問頻次，當(dāng)數(shù)據(jù)項(xiàng)被命中時(shí)，訪問頻次自增，在淘汰的時(shí)候淘汰訪問頻次最少的數(shù)據(jù)。這樣一來的話，在插入數(shù)據(jù)和訪問數(shù)據(jù)的時(shí)候都能達(dá)到O(1)的時(shí)間復(fù)雜度，在淘汰數(shù)據(jù)的時(shí)候，通過選擇算法得到應(yīng)該淘汰的數(shù)據(jù)項(xiàng)在數(shù)組中的索引，并將該索引位置的內(nèi)容替換為新來的數(shù)據(jù)內(nèi)容即可，這樣的話，淘汰數(shù)據(jù)的操作時(shí)間復(fù)雜度為O(n)。
另外還有一種實(shí)現(xiàn)思路就是利用 小頂堆+hashmap，小頂堆插入、刪除操作都能達(dá)到O(logn)時(shí)間復(fù)雜度，因此效率相比第一種實(shí)現(xiàn)方法更加高效。
如果哪位朋友有更高效的實(shí)現(xiàn)方式（比如O(1)時(shí)間復(fù)雜度），不妨探討一下，不勝感激。
0x03：LRU算法
LRU算法的設(shè)計(jì)原則是：如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒有被訪問到，那么在將來它被訪問的可能性也很小。也就是說，當(dāng)限定的空間已存滿數(shù)據(jù)時(shí)，應(yīng)當(dāng)把最久沒有被訪問到的數(shù)據(jù)淘汰。
而用什么數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)LRU算法呢？可能大多數(shù)人都會想到：用一個(gè)數(shù)組來存儲數(shù)據(jù)，給每一個(gè)數(shù)據(jù)項(xiàng)標(biāo)記一個(gè)訪問時(shí)間戳，每次插入新數(shù)據(jù)項(xiàng)的時(shí)候，先把數(shù)組中存在的數(shù)據(jù)項(xiàng)的時(shí)間戳自增，并將新數(shù)據(jù)項(xiàng)的時(shí)間戳置為0并插入到數(shù)組中。每次訪問數(shù)組中的數(shù)據(jù)項(xiàng)的時(shí)候，將被訪問的數(shù)據(jù)項(xiàng)的時(shí)間戳置為0。當(dāng)數(shù)組空間已滿時(shí)，將時(shí)間戳最大的數(shù)據(jù)項(xiàng)淘汰。
這種實(shí)現(xiàn)思路很簡單，但是有什么缺陷呢？需要不停地維護(hù)數(shù)據(jù)項(xiàng)的訪問時(shí)間戳，另外，在插入數(shù)據(jù)、刪除數(shù)據(jù)以及訪問數(shù)據(jù)時(shí)，時(shí)間復(fù)雜度都是O(n)。
那么有沒有更好的實(shí)現(xiàn)辦法呢？
那就是利用鏈表和hashmap。當(dāng)需要插入新的數(shù)據(jù)項(xiàng)的時(shí)候，如果新數(shù)據(jù)項(xiàng)在鏈表中存在（一般稱為命中），則把該節(jié)點(diǎn)移到鏈表頭部，如果不存在，則新建一個(gè)節(jié)點(diǎn)，放到鏈表頭部，若緩存滿了，則把鏈表最后一個(gè)節(jié)點(diǎn)刪除即可。在訪問數(shù)據(jù)的時(shí)候，如果數(shù)據(jù)項(xiàng)在鏈表中存在，則把該節(jié)點(diǎn)移到鏈表頭部，否則返回-1。這樣一來在鏈表尾部的節(jié)點(diǎn)就是最近最久未訪問的數(shù)據(jù)項(xiàng)。
總結(jié)一下：根據(jù)題目的要求，LRU Cache具備的操作：
1）set(key,value)：如果key在hashmap中存在，則先重置對應(yīng)的value值，然后獲取對應(yīng)的節(jié)點(diǎn)cur，將cur節(jié)點(diǎn)從鏈表刪除，并移動到鏈表的頭部；若果key在hashmap不存在，則新建一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)放到鏈表的頭部。當(dāng)Cache存滿的時(shí)候，將鏈表最后一個(gè)節(jié)點(diǎn)刪除即可。
2）get(key)：如果key在hashmap中存在，則把對應(yīng)的節(jié)點(diǎn)放到鏈表頭部，并返回對應(yīng)的value值；如果不存在，則返回-1。
