1
我們都聽過 cache嚷那，當(dāng)你問他們是什么是緩存的時(shí)候胞枕，他們會(huì)給你一個(gè)完美的答案，可是他們不知道緩存是怎么構(gòu)建的魏宽，或者沒有告訴你應(yīng)該采用什么標(biāo)準(zhǔn)去選擇緩存框架腐泻。在這篇文章，我們會(huì)去討論緩存队询，緩存算法贫悄，緩存框架以及哪個(gè)緩存框架會(huì)更好。

2

面試

“緩存就是存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時(shí)地方娘摔，因?yàn)槿≡紨?shù)據(jù)的代價(jià)太大了窄坦，所以我可以取得快一些〉仕拢”

這就是 programmer one （programmer one 是一個(gè)面試者）在面試中的回答（一個(gè)月前鸭津，他向公司提交了簡(jiǎn)歷，想要應(yīng)聘要求在緩存肠缨，緩存框架逆趋，大規(guī)模數(shù)據(jù)操作有著豐富經(jīng)驗(yàn)的 java 開發(fā)職位）。

programmer one 通過 hash table 實(shí)現(xiàn)了他自己的緩存晒奕，但是他知道的只是他的緩存和他那存儲(chǔ)著150條記錄的 hash table闻书，這就是他認(rèn)為的大規(guī)模數(shù)據(jù)（緩存 = hashtable，只需要在 hash table 查找就好了）脑慧，所以魄眉，讓我們來看看面試的過程吧。

面試官：你選擇的緩存方案闷袒，是基于什么標(biāo)準(zhǔn)的坑律？
programmer one：呃，（想了5分鐘）嗯囊骤，基于晃择，基于，基于數(shù)據(jù)（咳嗽……）
面試官：excese me ! 能不能重復(fù)一下也物？
programmer one：數(shù)據(jù)宫屠？！
面試官：好的滑蚯。說說幾種緩存算法以及它們的作用
programmer one：（凝視著面試官浪蹂，臉上露出了很奇怪的表情，沒有人知道原來人類可以做出這種表情 ）
面試官：好吧，那我換個(gè)說法乌逐，當(dāng)緩存達(dá)到容量時(shí)，會(huì)怎么做创葡？
programmer one：容量浙踢？嗯（思考……h(huán)ash table 的容量時(shí)沒有限制的，我能任意增加條目灿渴，它會(huì)自動(dòng)擴(kuò)充容量的）（這是 programmer one 的想法洛波，但是他沒有說出來）

面試官對(duì) programmer one 表示感謝（面試過程持續(xù)了10分鐘），之后一個(gè)女士走過來說：謝謝你的時(shí)間骚露，我們會(huì)給你打電話的蹬挤，祝你好心情。這是 programmer one 最糟糕的面試（他沒有看到招聘對(duì)求職者有豐富的緩存經(jīng)驗(yàn)背景要求棘幸，實(shí)際上焰扳，他只看到了豐厚的報(bào)酬 ）。

3

說到做到

programmer one 離開之后误续，他想要知道這個(gè)面試者說的問題和答案吨悍，所以他上網(wǎng)去查，programmer one 對(duì)緩存一無所知蹋嵌，除了：當(dāng)我需要緩存的時(shí)候育瓜，我就會(huì)用 hash table。

在他使用了他最愛的搜索引擎搜索之后栽烂，他找到了一篇很不錯(cuò)的關(guān)于緩存文章躏仇，并且開始去閱讀……

4

為什么我們需要緩存？

很久很久以前腺办，在還沒有緩存的時(shí)候……用戶經(jīng)常是去請(qǐng)求一個(gè)對(duì)象焰手，而這個(gè)對(duì)象是從數(shù)據(jù)庫去取，然后怀喉，這個(gè)對(duì)象變得越來越大册倒，這個(gè)用戶每次的請(qǐng)求時(shí)間也越來越長(zhǎng)了，這也把數(shù)據(jù)庫弄得很痛苦磺送，他無時(shí)不刻不在工作驻子。所以，這個(gè)事情就把用戶和數(shù)據(jù)庫弄得很生氣估灿，接著就有可能發(fā)生下面兩件事情：

１崇呵、用戶很煩，在抱怨馅袁，甚至不去用這個(gè)應(yīng)用了（這是大多數(shù)情況下都會(huì)發(fā)生的）

２域慷、數(shù)據(jù)庫為打包回家，離開這個(gè)應(yīng)用，然后犹褒，就出現(xiàn)了大麻煩（沒地方去存儲(chǔ)數(shù)據(jù)了）（發(fā)生在極少數(shù)情況下）

5

上帝派來了緩存

在幾年之后抵窒，IBM（60年代）的研究人員引進(jìn)了一個(gè)新概念，它叫“緩存”叠骑。

6

什么是緩存李皇？

正如開篇所講，緩存是“存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時(shí)地方宙枷，因?yàn)槿≡紨?shù)據(jù)的代價(jià)太大了掉房，所以我可以取得快一些∥看裕”

緩存可以認(rèn)為是數(shù)據(jù)的池卓囚，這些數(shù)據(jù)是從數(shù)據(jù)庫里的真實(shí)數(shù)據(jù)復(fù)制出來的，并且為了能別取回诅病，被標(biāo)上了標(biāo)簽（鍵 ID）哪亿。太棒了

programmer one 已經(jīng)知道這點(diǎn)了，但是他還不知道下面的緩存術(shù)語贤笆。

命中：

當(dāng)客戶發(fā)起一個(gè)請(qǐng)求（我們說他想要查看一個(gè)產(chǎn)品信息）锣夹，我們的應(yīng)用接受這個(gè)請(qǐng)求，并且如果是在第一次檢查緩存的時(shí)候苏潜，需要去數(shù)據(jù)庫讀取產(chǎn)品信息银萍。

如果在緩存中，一個(gè)條目通過一個(gè)標(biāo)記被找到了恤左，這個(gè)條目就會(huì)被使用贴唇、我們就叫它緩存命中。所以飞袋，命中率也就不難理解了戳气。

Cache Miss：

但是這里需要注意兩點(diǎn)：

１、如果還有緩存的空間巧鸭，那么瓶您，沒有命中的對(duì)象會(huì)被存儲(chǔ)到緩存中來。

２纲仍、如果緩存慢了呀袱，而又沒有命中緩存，那么就會(huì)按照某一種策略郑叠，把緩存中的舊對(duì)象踢出夜赵，而把新的對(duì)象加入緩存池。而這些策略統(tǒng)稱為替代策略（緩存算法）乡革，這些策略會(huì)決定到底應(yīng)該提出哪些對(duì)象寇僧。

存儲(chǔ)成本：

當(dāng)沒有命中時(shí)摊腋，我們會(huì)從數(shù)據(jù)庫取出數(shù)據(jù)，然后放入緩存嘁傀。而把這個(gè)數(shù)據(jù)放入緩存所需要的時(shí)間和空間兴蒸，就是存儲(chǔ)成本。

索引成本：

和存儲(chǔ)成本相仿细办。

失效：

當(dāng)存在緩存中的數(shù)據(jù)需要更新時(shí)橙凳，就意味著緩存中的這個(gè)數(shù)據(jù)失效了。

替代策略：

當(dāng)緩存沒有命中時(shí)蟹腾，并且緩存容量已經(jīng)滿了痕惋，就需要在緩存中踢出一個(gè)老的條目区宇，加入一條新的條目蘸泻，而到底應(yīng)該踢出什么條目苛茂，就由替代策略決定。

最優(yōu)替代策略：

最優(yōu)的替代策略就是想把緩存中最沒用的條目給踢出去，但是未來是不能夠被預(yù)知的含滴，所以這種策略是不可能實(shí)現(xiàn)的。但是有很多策略贞远，都是朝著這個(gè)目前去努力悦即。

Java 街惡夢(mèng)：

當(dāng) programmer one 在讀這篇文章的時(shí)候，他睡著了逼裆，并且做了個(gè)惡夢(mèng)（每個(gè)人都有做惡夢(mèng)的時(shí)候）郁稍。

programmer one：nihahha，我要把你弄失效Ｊび睢（瘋狂的狀態(tài)）
緩存對(duì)象：別別耀怜，讓我活著，他們還需要我桐愉，我還有孩子财破。

programmer one：每個(gè)緩存對(duì)象在失效之前都會(huì)那樣說。你從什么時(shí)候開始有孩子的从诲？不用擔(dān)心左痢，現(xiàn)在就永遠(yuǎn)消失吧！

哈哈哈哈哈……programmer one 恐怖的笑著系洛，但是警笛打破了沉靜俊性，警察把 programmer one 抓了起來，并且控告他殺死了（失效）一個(gè)仍需被使用的緩存對(duì)象描扯，他被押到了監(jiān)獄磅废。

programmer one 突然醒了，他被嚇到了荆烈，渾身是汗拯勉，他開始環(huán)顧四周竟趾，發(fā)現(xiàn)這確實(shí)是個(gè)夢(mèng)，然后趕緊繼續(xù)閱讀這篇文章宫峦，努力的消除自己的恐慌岔帽。

在programmer one 醒來之后，他又開始閱讀文章了导绷。

7

緩存算法

沒有人能說清哪種緩存算法優(yōu)于其他的緩存算法

Least Frequently Used（LFU）：

大家好犀勒，我是 LFU，我會(huì)計(jì)算為每個(gè)緩存對(duì)象計(jì)算他們被使用的頻率妥曲。我會(huì)把最不常用的緩存對(duì)象踢走贾费。

Least Recently User（LRU）：

我是 LRU 緩存算法，我把最近最少使用的緩存對(duì)象給踢走檐盟。

我總是需要去了解在什么時(shí)候褂萧，用了哪個(gè)緩存對(duì)象。如果有人想要了解我為什么總能把最近最少使用的對(duì)象踢掉葵萎，是非常困難的导犹。

瀏覽器就是使用了我（LRU）作為緩存算法。新的對(duì)象會(huì)被放在緩存的頂部羡忘，當(dāng)緩存達(dá)到了容量極限谎痢，我會(huì)把底部的對(duì)象踢走，而技巧就是：我會(huì)把最新被訪問的緩存對(duì)象卷雕，放到緩存池的頂部节猿。

所以，經(jīng)常被讀取的緩存對(duì)象就會(huì)一直呆在緩存池中漫雕。有兩種方法可以實(shí)現(xiàn)我滨嘱，array 或者是 linked list。

我的速度很快蝎亚，我也可以被數(shù)據(jù)訪問模式適配九孩。我有一個(gè)大家庭，他們都可以完善我发框，甚至做的比我更好（我確實(shí)有時(shí)會(huì)嫉妒躺彬，但是沒關(guān)系）。我家庭的一些成員包括 LRU2 和 2Q梅惯，他們就是為了完善 LRU 而存在的宪拥。

Least Recently Used 2（LRU2）：

我是 Least Recently Used 2，有人叫我最近最少使用 twice铣减，我更喜歡這個(gè)叫法她君。我會(huì)把被兩次訪問過的對(duì)象放入緩存池，當(dāng)緩存池滿了之后葫哗，我會(huì)把有兩次最少使用的緩存對(duì)象踢走缔刹。因?yàn)樾枰檶?duì)象2次球涛，訪問負(fù)載就會(huì)隨著緩存池的增加而增加。如果把我用在大容量的緩存池中校镐，就會(huì)有問題亿扁。另外，我還需要跟蹤那么不在緩存的對(duì)象鸟廓，因?yàn)樗麄冞€沒有被第二次讀取从祝。我比LRU好，而且是 adoptive to access 模式 引谜。

Two Queues（2Q）：

我是 Two Queues牍陌；我把被訪問的數(shù)據(jù)放到 LRU 的緩存中，如果這個(gè)對(duì)象再一次被訪問员咽，我就把他轉(zhuǎn)移到第二個(gè)毒涧、更大的 LRU 緩存。

我踢走緩存對(duì)象是為了保持第一個(gè)緩存池是第二個(gè)緩存池的1/3骏融。當(dāng)緩存的訪問負(fù)載是固定的時(shí)候链嘀，把 LRU 換成 LRU2萌狂，就比增加緩存的容量更好档玻。這種機(jī)制使得我比 LRU2 更好，我也是 LRU 家族中的一員茫藏，而且是 adoptive to access 模式 误趴。

Adaptive Replacement Cache（ARC）：

我是 ARC，有人說我是介于 LRU 和 LFU 之間务傲，為了提高效果凉当，我是由2個(gè) LRU 組成，第一個(gè)售葡，也就是 L1看杭，包含的條目是最近只被使用過一次的，而第二個(gè) LRU挟伙，也就是 L2楼雹，包含的是最近被使用過兩次的條目。因此尖阔， L1 放的是新的對(duì)象贮缅，而 L2 放的是常用的對(duì)象。所以介却，別人才會(huì)認(rèn)為我是介于 LRU 和 LFU 之間的谴供，不過沒關(guān)系，我不介意齿坷。

我被認(rèn)為是性能最好的緩存算法之一桂肌，能夠自調(diào)数焊，并且是低負(fù)載的。我也保存著歷史對(duì)象崎场，這樣昌跌，我就可以記住那些被移除的對(duì)象，同時(shí)照雁，也讓我可以看到被移除的對(duì)象是否可以留下蚕愤，取而代之的是踢走別的對(duì)象。我的記憶力很差饺蚊，但是我很快萍诱，適用性也強(qiáng)。

Most Recently Used（MRU）：

我是 MRU污呼，和 LRU 是對(duì)應(yīng)的裕坊。我會(huì)移除最近最多被使用的對(duì)象，你一定會(huì)問我為什么燕酷。好吧籍凝，讓我告訴你，當(dāng)一次訪問過來的時(shí)候苗缩，有些事情是無法預(yù)測(cè)的饵蒂，并且在緩存系統(tǒng)中找出最少最近使用的對(duì)象是一項(xiàng)時(shí)間復(fù)雜度非常高的運(yùn)算，這就是為什么我是最好的選擇酱讶。

我是數(shù)據(jù)庫內(nèi)存緩存中是多么的常見退盯！每當(dāng)一次緩存記錄的使用，我會(huì)把它放到棧的頂端泻肯。當(dāng)棧滿了的時(shí)候渊迁，你猜怎么著？我會(huì)把棧頂?shù)膶?duì)象給換成新進(jìn)來的對(duì)象灶挟！

First in First out（FIFO）：

我是先進(jìn)先出琉朽，我是一個(gè)低負(fù)載的算法，并且對(duì)緩存對(duì)象的管理要求不高稚铣。我通過一個(gè)隊(duì)列去跟蹤所有的緩存對(duì)象箱叁，最近最常用的緩存對(duì)象放在后面，而更早的緩存對(duì)象放在前面榛泛，當(dāng)緩存容量滿時(shí)蝌蹂，排在前面的緩存對(duì)象會(huì)被踢走，然后把新的緩存對(duì)象加進(jìn)去曹锨。我很快孤个，但是我并不適用。

Second Chance：

大家好沛简，我是 second chance齐鲤，我是通過 FIFO 修改而來的斥废，被大家叫做 second chance 緩存算法，我比 FIFO 好的地方是我改善了 FIFO 的成本给郊。我是 FIFO 一樣也是在觀察隊(duì)列的前端牡肉，但是很FIFO的立刻踢出不同，我會(huì)檢查即將要被踢出的對(duì)象有沒有之前被使用過的標(biāo)志（1一個(gè) bit 表示）淆九，沒有沒有被使用過统锤，我就把他踢出；否則炭庙，我會(huì)把這個(gè)標(biāo)志位清除饲窿，然后把這個(gè)緩存對(duì)象當(dāng)做新增緩存對(duì)象加入隊(duì)列。你可以想象就這就像一個(gè)環(huán)隊(duì)列焕蹄。當(dāng)我再一次在隊(duì)頭碰到這個(gè)對(duì)象時(shí)逾雄，由于他已經(jīng)沒有這個(gè)標(biāo)志位了，所以我立刻就把他踢開了腻脏。我在速度上比 FIFO 快鸦泳。

CLock：

我是 Clock，一個(gè)更好的 FIFO永品，也比 second chance 更好做鹰。因?yàn)槲也粫?huì)像 second chance 那樣把有標(biāo)志的緩存對(duì)象放到隊(duì)列的尾部，但是也可以達(dá)到 second chance 的效果腐碱。

我持有一個(gè)裝有緩存對(duì)象的環(huán)形列表誊垢，頭指針指向列表中最老的緩存對(duì)象掉弛。當(dāng)緩存 miss 發(fā)生并且沒有新的緩存空間時(shí)症见，我會(huì)問問指針指向的緩存對(duì)象的標(biāo)志位去決定我應(yīng)該怎么做。如果標(biāo)志是0殃饿，我會(huì)直接用新的緩存對(duì)象替代這個(gè)緩存對(duì)象谋作；如果標(biāo)志位是1，我會(huì)把頭指針遞增乎芳，然后重復(fù)這個(gè)過程遵蚜，知道新的緩存對(duì)象能夠被放入。我比 second chance 更快奈惑。

Simple time-based：

我是 simple time-based 緩存算法吭净，我通過絕對(duì)的時(shí)間周期去失效那些緩存對(duì)象。對(duì)于新增的對(duì)象肴甸，我會(huì)保存特定的時(shí)間寂殉。我很快，但是我并不適用原在。

Extended time-based expiration：

我是 extended time-based expiration 緩存算法友扰，我是通過相對(duì)時(shí)間去失效緩存對(duì)象的彤叉；對(duì)于新增的緩存對(duì)象，我會(huì)保存特定的時(shí)間村怪，比如是每5分鐘秽浇，每天的12點(diǎn)。

Sliding time-based expiration：

我是 sliding time-based expiration甚负，與前面不同的是柬焕，被我管理的緩存對(duì)象的生命起點(diǎn)是在這個(gè)緩存的最后被訪問時(shí)間算起的。我很快梭域，但是我也不太適用击喂。

其他的緩存算法還考慮到了下面幾點(diǎn)：

成本：如果緩存對(duì)象有不同的成本，應(yīng)該把那些難以獲得的對(duì)象保存下來碰辅。

容量：如果緩存對(duì)象有不同的大小懂昂，應(yīng)該把那些大的緩存對(duì)象清除，這樣就可以讓更多的小緩存對(duì)象進(jìn)來了没宾。

時(shí)間：一些緩存還保存著緩存的過期時(shí)間凌彬。電腦會(huì)失效他們，因?yàn)樗麄円呀?jīng)過期了循衰。

根據(jù)緩存對(duì)象的大小而不管其他的緩存算法可能是有必要的铲敛。

8

電子郵件！

在讀完這篇文章之后会钝，programmer one 想了一會(huì)兒伐蒋，然后決定給作者發(fā)封郵件，他感覺作者的名字在哪聽過迁酸，但是已經(jīng)想不起來了先鱼。不管怎樣，他還是把郵件發(fā)送出來了奸鬓，他詢問了作者在分布式環(huán)境中焙畔，緩存是怎么樣工作的。

文章的作者收到了郵件串远，具有諷刺意味的是宏多，這個(gè)作者就是面試 programmer one 的人 ，作者回復(fù)了……

在這一部分中澡罚，我們來看看如何實(shí)現(xiàn)這些著名的緩存算法伸但。以下的代碼只是示例用的，如果你想自己實(shí)現(xiàn)緩存算法留搔，可能自己還得加上一些額外的工作更胖。

9

LeftOver機(jī)制

在 programmer one 閱讀了文章之后，他接著看了文章的評(píng)論，其中有一篇評(píng)論提到了 leftover 機(jī)制——random cache函喉。

10

Random Cache

我是隨機(jī)緩存避归，我隨意的替換緩存實(shí)體，沒人敢抱怨管呵。你可以說那個(gè)被替換的實(shí)體很倒霉梳毙。通過這些行為，我隨意的去處緩存實(shí)體捐下。我比 FIFO 機(jī)制好账锹，在某些情況下，我甚至比 LRU 好坷襟，但是奸柬，通常LRU都會(huì)比我好。

11

現(xiàn)在是評(píng)論時(shí)間

當(dāng) programmer one 繼續(xù)閱讀評(píng)論的時(shí)候婴程，他發(fā)現(xiàn)有個(gè)評(píng)論非常有趣廓奕，這個(gè)評(píng)論實(shí)現(xiàn)了一些緩存算法，應(yīng)該說這個(gè)評(píng)論做了一個(gè)鏈向評(píng)論者網(wǎng)站的鏈接档叔，programmer one順著鏈接到了那個(gè)網(wǎng)站桌粉，接著閱讀。

看看緩存元素（緩存實(shí)體）

public class CacheElement
{
private Object objectValue;
private Object objectKey;
private int index;
private int hitCount;　// getters and setters
}

這個(gè)緩存實(shí)體擁有緩存的key和value衙四，這個(gè)實(shí)體的數(shù)據(jù)結(jié)構(gòu)會(huì)被以下所有緩存算法用到铃肯。

12

緩存算法的公用代碼

public final synchronized void addElement(Object key, Object value)
{
int index;
Object obj;
// get the entry from the table
obj = table.get(key);
// If we have the entry already in our table
// then get it and replace only its value.
obj = table.get(key);

if (obj != null)
{
CacheElement element;
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}
｝

上面的代碼會(huì)被所有的緩存算法實(shí)現(xiàn)用到。這段代碼是用來檢查緩存元素是否在緩存中了传蹈，如果是押逼，我們就替換它，但是如果我們找不到這個(gè) key 對(duì)應(yīng)的緩存惦界，我們會(huì)怎么做呢挑格？那我們就來深入的看看會(huì)發(fā)生什么吧！

13

現(xiàn)場(chǎng)訪問

今天的專題很特殊表锻，因?yàn)槲覀冇刑厥獾目腿怂∑耄聦?shí)上他們是我們想要聽的與會(huì)者，但是首先瞬逊，先介紹一下我們的客人：Random Cache，F(xiàn)IFO Cache仪或。讓我們從 Random Cache開始确镊。

看看隨機(jī)緩存的實(shí)現(xiàn)

public final synchronized void addElement(Object key, Object value)
{
int index;
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element;// Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}// If we haven't filled the cache yet, put it at the end.
if (!isFull())
{
index = numEntries;
++numEntries;
}
else { // Otherwise, replace a random entry.
index = (int) (cache.length * random.nextFloat());
table.remove(cache[index].getObjectKey());
}
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
table.put(key, cache[index]);
}

看看FIFO緩算法的實(shí)現(xiàn)

public final synchronized void addElement(Objectkey, Object value)
{
int index;
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element; // Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}
// If we haven't filled the cache yet, put it at the end.
if (!isFull())
{
index = numEntries;
++numEntries;
}
else { // Otherwise, replace the current pointer,
// entry with the new one.
index = current;
// in order to make Circular FIFO
if (++current >= cache.length)
current = 0;
table.remove(cache[index].getObjectKey());
}
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
table.put(key, cache[index]);
}

看看LFU緩存算法的實(shí)現(xiàn)

public synchronized Object getElement(Object key)
{
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element = (CacheElement) obj;
element.setHitCount(element.getHitCount() + 1);
return element.getObjectValue();
}
return null;
}
public final synchronized void addElement(Object key, Object value)
{
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element; // Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}
if (!isFull())
{
index = numEntries;
++numEntries;
}
else
{
CacheElement element = removeLfuElement();
index = element.getIndex();
table.remove(element.getObjectKey());
}
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
cache[index].setIndex(index);
table.put(key, cache[index]);
}
public CacheElement removeLfuElement()
{
CacheElement[] elements = getElementsFromTable();
CacheElement leastElement = leastHit(elements);
return leastElement;
}
public static CacheElement leastHit(CacheElement[] elements)
{
CacheElement lowestElement = null;
for (int i = 0; i < elements.length; i++)
{
CacheElement element = elements[i];
if (lowestElement == null)
{
lowestElement = element;
}
else {
if (element.getHitCount() < lowestElement.getHitCount())
{
lowestElement = element;
}
}
}
return lowestElement;
}

今天的專題很特殊，因?yàn)槲覀冇刑厥獾目腿朔渡荆聦?shí)上他們是我們想要聽的與會(huì)者蕾域，但是首先，先介紹一下我們的客人：Random Cache, FIFO Cache。讓我們從 Random Cache開始旨巷。

最重點(diǎn)的代碼巨缘，就應(yīng)該是 leastHit 這個(gè)方法，這段代碼就是把
hitCount 最低的元素找出來采呐，然后刪除若锁，給新進(jìn)的緩存元素留位置。

看看LRU緩存算法實(shí)現(xiàn)

private void moveToFront(int index)
{
int nextIndex, prevIndex;
if(head != index)
{
nextIndex = next[index];
prevIndex = prev[index];
// Only the head has a prev entry that is an invalid index
// so we don't check.
next[prevIndex] = nextIndex;
// Make sure index is valid. If it isn't, we're at the tail
// and don't set prev[next].
if(nextIndex >= 0)
prev[nextIndex] = prevIndex;
else
tail = prevIndex;
prev[index] = -1;
next[index] = head;
prev[head] = index;
head = index;
}
}
public final synchronized void addElement(Object key, Object value)
{
int index;Object obj;
obj = table.get(key);
if(obj != null)
{
CacheElement entry;
// Just replace the value, but move it to the front.
entry = (CacheElement)obj;
entry.setObjectValue(value);
entry.setObjectKey(key);
moveToFront(entry.getIndex());
return;
}
// If we haven't filled the cache yet, place in next available
// spot and move to front.
if(!isFull())
{
if(_numEntries > 0)
{
prev[_numEntries] = tail;
next[_numEntries] = -1;
moveToFront(numEntries);
}
++numEntries;
}
else { // We replace the tail of the list.
table.remove(cache[tail].getObjectKey());
moveToFront(tail);
}
cache[head].setObjectValue(value);
cache[head].setObjectKey(key);
table.put(key, cache[head]);
}

這段代碼的邏輯如 LRU算法 的描述一樣斧吐，把再次用到的緩存提取到最前面又固，而每次刪除的都是最后面的元素。

14

結(jié)論

我們已經(jīng)看到 LFU緩存算法 和 LRU緩存算法的實(shí)現(xiàn)方式煤率，至于如何實(shí)現(xiàn)仰冠，采用數(shù)組還是 LinkedHashMap，都由你決定蝶糯，不夠我一般是小的緩存容量用數(shù)組洋只，大的用 LinkedHashMap。
來自：lixiang（http://www.leexiang.com/cache-algorithm）
譯文：http://www.zavakid.com/25
原文：http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html