面試騰訊遇到的算法題。
眾所周知，LRU本質(zhì)就是一個(gè)哈希表+雙向鏈表的組合數(shù)據(jù)結(jié)構(gòu)，java中l(wèi)inkedHashMap就是一個(gè)實(shí)現(xiàn)好了的LRU，其內(nèi)部實(shí)現(xiàn)就是繼承HashMap的基本能力，繼承HashMap的內(nèi)部類Node增加前后兩個(gè)指針形成一個(gè)雙向鏈表，在hashMap的get，put操作基礎(chǔ)之上維護(hù)這個(gè)雙向鏈表。
現(xiàn)在需要不使用LinkedHashMap，只使用HashMap的基礎(chǔ)上實(shí)現(xiàn)一個(gè)LRU。代碼如下：
public class LRUCache {
private? int capacity;
? ? private int size;
? ?Map<Integer,Node> map;
? ? Node head;
? ? Node tail;
? ? public LRUCache(int capacity) {
????????this.capacity=capacity;
? ? ? ? size=0;
? ? ? ? map=new HashMap<>(capacity);
? ? ? ? head=new Node();
? ? ? ? tail=new Node();
? ? ? ? head.next=tail;
? ? ? ? tail.pre=head;
? ? }
public int get(int key) {
if(map.containsKey(key)) {
Node p=map.get(key);
? ? ? ? ? ? moveNodeToHead(p);
? ? ? ? ? ? return p.value;
? ? ? ? }
return -1;
? ? }
public void put(int key, int value) {
if(map.containsKey(key)) {
Node p=map.get(key);
? ? ? ? ? ? p.value=value;
? ? ? ? ? ? moveNodeToHead(p);
? ? ? ? }else {
Node p=new Node(key,value);
? ? ? ? ? ? map.put(key,p);
? ? ? ? ? ? addToHead(p);
? ? ? ? ? ? if(size==capacity){
map.remove(tail.pre.key);
? ? ? ? ? ? ? ? removeNode(tail.pre);
? ? ? ? ? ? }else {
size++;
? ? ? ? ? ? }
}
}
private void addToHead(Node node) {
head.next.pre=node;
? ? ? ? node.next=head.next;
? ? ? ? node.pre=head;
? ? ? ? head.next=node;
? ? }
private void? removeNode(Node node){
node.pre.next=node.next;
? ? ? ? node.next.pre=node.pre;
? ? }
private void moveNodeToHead(Node node) {
removeNode(node);
? ? ? ? addToHead(node);
? ? }
}
class Node{
int key;
? ? int value;
? ? Nodepre;
? ? Nodenext;
? ? public Node() {}
public Node(int key,int value) {
this.key=key;
? ? ? ? this.value=value;
? ? }
}
總結(jié)：
1、自己實(shí)現(xiàn)哈希表和雙向鏈表的組合數(shù)據(jù)結(jié)構(gòu)，不要像LinkedHashMap那樣去繼承HashMap，直接修改HashMap中Node的結(jié)構(gòu)（如果按照LinkedHashMap源碼的思路自己實(shí)現(xiàn)就踩大坑了），而是應(yīng)該將Node結(jié)構(gòu)中的value從直接存儲值改為存儲鏈表結(jié)點(diǎn)，因此內(nèi)部Map屬性從Map<Integer,Integer> map改為Map?<Integer,Node>。
2、雙向鏈表收尾都指向哨兵結(jié)點(diǎn)，這樣插入刪除鏈表結(jié)點(diǎn)時(shí)就不需要判斷鏈表為空時(shí)首尾結(jié)點(diǎn)的特殊處理情況。
3、對于get，put操作，命中時(shí)都有將結(jié)點(diǎn)移動到表頭這樣的操作，可以將這塊邏輯剝離出來抽象成公共方法。插入新節(jié)點(diǎn)和刪除新節(jié)點(diǎn)時(shí)，注意哈希表中也要進(jìn)行插入刪除操作。
