97AV电影,美女抽插网站,91丨国产丨白丝,激情婷婷五月天,竹菊影视一区二区三区,西西特级444www高清视频,777国产视频,北条麻妃影音先锋

本文公眾號來源：程序員小灰作者：小灰本文已收錄至我的GitHub

—————? 兩個月前? —————

用戶信息當然是存在數(shù)據(jù)庫里。但是由于我們對用戶系統(tǒng)的性能要求比較高，顯然不能每一次請求都去查詢數(shù)據(jù)庫。

所以，小灰在內(nèi)存中創(chuàng)建了一個哈希表作為緩存，每次查找一個用戶的時候先在哈希表中查詢，以此提高訪問性能。

很快，用戶系統(tǒng)上線了，小灰美美地休息了幾天。

一個多月之后......

———————————————

什么是哈希鏈表呢？

我們都知道，哈希表是由若干個Key-Value所組成。在“邏輯”上，這些Key-Value是無所謂排列順序的，誰先誰后都一樣。

在哈希鏈表當中，這些Key-Value不再是彼此無關(guān)的存在，而是被一個鏈條串了起來。每一個Key-Value都具有它的前驅(qū)Key-Value、后繼Key-Value，就像雙向鏈表中的節(jié)點一樣。

這樣一來，原本無序的哈希表擁有了固定的排列順序。

讓我們以用戶信息的需求為例，來演示一下LRU算法的基本思路：

1.假設(shè)我們使用哈希鏈表來緩存用戶信息，目前緩存了4個用戶，這4個用戶是按照時間順序依次從鏈表右端插入的。

2.此時，業(yè)務(wù)方訪問用戶5，由于哈希鏈表中沒有用戶5的數(shù)據(jù)，我們從數(shù)據(jù)庫中讀取出來，插入到緩存當中。這時候，鏈表中最右端是最新訪問到的用戶5，最左端是最近最少訪問的用戶1。

3.接下來，業(yè)務(wù)方訪問用戶2，哈希鏈表中存在用戶2的數(shù)據(jù)，我們怎么做呢？我們把用戶2從它的前驅(qū)節(jié)點和后繼節(jié)點之間移除，重新插入到鏈表最右端。這時候，鏈表中最右端變成了最新訪問到的用戶2，最左端仍然是最近最少訪問的用戶1。

4.接下來，業(yè)務(wù)方請求修改用戶4的信息。同樣道理，我們把用戶4從原來的位置移動到鏈表最右側(cè)，并把用戶信息的值更新。這時候，鏈表中最右端是最新訪問到的用戶4，最左端仍然是最近最少訪問的用戶1。

5.后來業(yè)務(wù)方換口味了，訪問用戶6，用戶6在緩存里沒有，需要插入到哈希鏈表。假設(shè)這時候緩存容量已經(jīng)達到上限，必須先刪除最近最少訪問的數(shù)據(jù)，那么位于哈希鏈表最左端的用戶1就會被刪除掉，然后再把用戶6插入到最右端。

以上，就是LRU算法的基本思路。

privateNode head;
privateNodeend;
//緩存存儲上限
privateint limit;
privateHashMap<String,Node> hashMap;
publicLRUCache(int limit){
? ?this.limit = limit;
? ?hashMap =newHashMap<String,Node>();
}
publicStringget(String key){
? ?Node node = hashMap.get(key);
? ?if(node ==null){
? ? ? ?returnnull;
? ?}
? ?refreshNode(node);
? ?return node.value;
}
publicvoid put(String key,String value){
? ?Node node = hashMap.get(key);
? ?if(node ==null){
? ? ? ?//如果key不存在，插入key-value
? ? ? ?if(hashMap.size()>= limit){
? ? ? ? ? ?String oldKey = removeNode(head);
? ? ? ? ? ?hashMap.remove(oldKey);
? ? ? ?}
? ? ? ?node =newNode(key, value);
? ? ? ?addNode(node);
? ? ? ?hashMap.put(key, node);
? ?}else{
? ? ? ?//如果key存在，刷新key-value
? ? ? ?node.value = value;
? ? ? ?refreshNode(node);
? ?}
}
publicvoid remove(String key){
? ?Node node = hashMap.get(key);
? ?removeNode(node);
? ?hashMap.remove(key);
}
/**
* 刷新被訪問的節(jié)點位置
* @param ?node 被訪問的節(jié)點
*/
privatevoid refreshNode(Node node){
? ?//如果訪問的是尾節(jié)點，無需移動節(jié)點
? ?if(node ==end){
? ? ? ?return;
? ?}
? ?//移除節(jié)點
? ?removeNode(node);
? ?//重新插入節(jié)點
? ?addNode(node);
}
/**
* 刪除節(jié)點
* @param ?node 要刪除的節(jié)點
*/
privateString removeNode(Node node){
? ?if(node ==end){
? ? ? ?//移除尾節(jié)點
? ? ? ?end=end.pre;
? ?}elseif(node == head){
? ? ? ?//移除頭節(jié)點
? ? ? ?head = head.next;
? ?}else{
? ? ? ?//移除中間節(jié)點
? ? ? ?node.pre.next= node.next;
? ? ? ?node.next.pre = node.pre;
? ?}
? ?return node.key;
}
/**
* 尾部插入節(jié)點
* @param ?node 要插入的節(jié)點
*/
privatevoid addNode(Node node){
? ?if(end!=null){
? ? ? ?end.next= node;
? ? ? ?node.pre =end;
? ? ? ?node.next=null;
? ?}
? ?end= node;
? ?if(head ==null){
? ? ? ?head = node;
? ?}
}
classNode{
? ?Node(String key,String value){
? ? ? ?this.key = key;
? ? ? ?this.value = value;
? ?}
? ?publicNode pre;
? ?publicNodenext;
? ?publicString key;
? ?publicString value;
}
publicstaticvoid main(String[] args){
? ?LRUCache lruCache =newLRUCache(5);
? ?lruCache.put("001","用戶1信息");
? ?lruCache.put("002","用戶1信息");
? ?lruCache.put("003","用戶1信息");
? ?lruCache.put("004","用戶1信息");
? ?lruCache.put("005","用戶1信息");
? ?lruCache.get("002");
? ?lruCache.put("004","用戶2信息更新");
? ?lruCache.put("006","用戶6信息");
? ?System.out.println(lruCache.get("001"));
? ?System.out.println(lruCache.get("006"));
}

需要注意的是，這段不是線程安全的，要想做到線程安全，需要加上synchronized修飾符。

—————END—————

歡迎加入交流群學(xué)習，備注加群說實話在這個群，哪怕您不說話，光看聊天記錄，都能學(xué)到東西

推薦阿里云推廣服務(wù)器89/年，229/3年，買來送自己，送女朋友馬上過年再合適不過了，買了搭建個項目給面試官看也香，還可以熟悉技術(shù)棧，(老用戶用家人賬號買就好了，我用我女朋友的?）。掃碼購買

我這里還有購買后的教程：搭建教程，從0開始一步一步帶你搭建?

兩年嘔心瀝血的文章：「面試題」「基礎(chǔ)」「進階」這里全都有！

面試經(jīng)常問你的LRU算法