structNode{intkey;intvalue;intfreq;list<int>::const_iteratorit;};classLFUCache{public:LFUCache(intcapacity):capacity(capacity),minFreq(0){}intget(intkey){if(!keyToNode.count(key))return-1;Node&node=keyToNode[key];touch(node);returnnode.value;}voidput(intkey,intvalue){if(capacity==0)return;if(keyToNode.count(key)){Node&node=keyToNode[key];node.value=value;touch(node);return;}if(keyToNode.size()==capacity){// evict LRU key from the minFreq listconstintkeyToEvict=freqToList[minFreq].back();freqToList[minFreq].pop_back();keyToNode.erase(keyToEvict);}minFreq=1;freqToList[1].push_front(key);keyToNode[key]={key,value,1,cbegin(freqToList[1])};}private:intcapacity;intminFreq;unordered_map<int,Node>keyToNode;unordered_map<int,list<int>>freqToList;voidtouch(Node&node){// update the node's frequencyconstintprevFreq=node.freq;constintnewFreq=++node.freq;// remove the iterator from prevFreq's listfreqToList[prevFreq].erase(node.it);if(freqToList[prevFreq].empty()){freqToList.erase(prevFreq);// update minFreq if neededif(prevFreq==minFreq)++minFreq;}// insert the key to the front of newFreq's listfreqToList[newFreq].push_front(node.key);node.it=cbegin(freqToList[newFreq]);}};
JAVA
classLFUCache{publicLFUCache(intcapacity){this.capacity=capacity;}publicintget(intkey){if(!keyToVal.containsKey(key))return-1;finalintfreq=keyToFreq.get(key);freqToLRUKeys.get(freq).remove(key);if(freq==minFreq&&freqToLRUKeys.get(freq).isEmpty()){freqToLRUKeys.remove(freq);++minFreq;}// increase key's freq by 1// add this key to next freq's listputFreq(key,freq+1);returnkeyToVal.get(key);}publicvoidput(intkey,intvalue){if(capacity==0)return;if(keyToVal.containsKey(key)){keyToVal.put(key,value);get(key);// update key's countreturn;}if(keyToVal.size()==capacity){// evict LRU key from the minFreq listfinalintkeyToEvict=freqToLRUKeys.get(minFreq).iterator().next();freqToLRUKeys.get(minFreq).remove(keyToEvict);keyToVal.remove(keyToEvict);}minFreq=1;putFreq(key,minFreq);// add new key and freqkeyToVal.put(key,value);// add new key and value}privateintcapacity;privateintminFreq=0;privateMap<Integer,Integer>keyToVal=newHashMap<>();privateMap<Integer,Integer>keyToFreq=newHashMap<>();privateMap<Integer,LinkedHashSet<Integer>>freqToLRUKeys=newHashMap<>();privatevoidputFreq(intkey,intfreq){keyToFreq.put(key,freq);freqToLRUKeys.putIfAbsent(freq,newLinkedHashSet<>());freqToLRUKeys.get(freq).add(key);}}
Login to Codeflu
Log in to stay update and get notify on new arrivals.