|
| 1 | +packagepackage1; |
| 2 | + |
| 3 | +importjava.util.Comparator; |
| 4 | +importjava.util.HashMap; |
| 5 | +importjava.util.List; |
| 6 | +importjava.util.Map; |
| 7 | +importjava.util.Map.Entry; |
| 8 | +importjava.util.PriorityQueue; |
| 9 | +importjava.util.Queue; |
| 10 | +importjava.util.TreeMap; |
| 11 | +importjava.util.TreeSet; |
| 12 | + |
| 13 | +publicclassLFUCache { |
| 14 | +/** |
| 15 | + * Wikipedia: The simplest method to employ an LFU algorithm is to assign a counter to every |
| 16 | + * block that is loaded into the cache. Each time a reference is made to that block the counter |
| 17 | + * is increased by one. When the cache reaches capacity and has a new block waiting to be |
| 18 | + * inserted the system will search for the block with the lowest counter and remove it from the |
| 19 | + * cache. |
| 20 | + * |
| 21 | + * Policy to handle frequency ties: based on timestamp, the entries that get set into cache earlier will be evicted first. |
| 22 | + */ |
| 23 | + |
| 24 | +classFreqKeyValueTimestamp { |
| 25 | +intfreq; |
| 26 | +intkey; |
| 27 | +intvalue; |
| 28 | +longtimestamp; |
| 29 | + } |
| 30 | + |
| 31 | +Map<Integer,FreqKeyValueTimestamp>map; |
| 32 | +TreeSet<FreqKeyValueTimestamp>set; |
| 33 | +intmax; |
| 34 | + |
| 35 | +publicLFUCache(intcapacity) { |
| 36 | +max =capacity; |
| 37 | +map =newHashMap<Integer,FreqKeyValueTimestamp>(); |
| 38 | +set =newTreeSet<FreqKeyValueTimestamp>(newComparator<FreqKeyValueTimestamp>(){ |
| 39 | + |
| 40 | +@Override |
| 41 | +publicintcompare(FreqKeyValueTimestampo1,FreqKeyValueTimestampo2) { |
| 42 | +if(o1.freq !=o2.freq)returno1.freq -o2.freq; |
| 43 | +elsereturn (int) (o1.timestamp -o2.timestamp);//it's guaranteed that timestamp will never have two to be the same |
| 44 | + } |
| 45 | + |
| 46 | + }); |
| 47 | + } |
| 48 | + |
| 49 | +publicintget(intkey) { |
| 50 | +if(!map.containsKey(key))return -1; |
| 51 | +else { |
| 52 | +FreqKeyValueTimestampvalueObj =map.get(key); |
| 53 | +set.remove(valueObj); |
| 54 | +valueObj.freq +=1; |
| 55 | +valueObj.timestamp =System.currentTimeMillis(); |
| 56 | +map.put(key,valueObj); |
| 57 | +returnmap.get(key).value; |
| 58 | + } |
| 59 | + } |
| 60 | + |
| 61 | +publicvoidset(intkey,intvalue) { |
| 62 | +if(!map.containsKey(key)){ |
| 63 | +while(set.size() >=max){ |
| 64 | +FreqKeyValueTimestampvalueObj =set.pollFirst(); |
| 65 | +map.remove(valueObj.key); |
| 66 | + } |
| 67 | +FreqKeyValueTimestampvalueObj =newFreqKeyValueTimestamp(); |
| 68 | +valueObj.key =key; |
| 69 | +valueObj.timestamp =System.currentTimeMillis(); |
| 70 | +valueObj.value =value; |
| 71 | +valueObj.freq =1; |
| 72 | +map.put(key,valueObj); |
| 73 | +set.add(valueObj); |
| 74 | + } |
| 75 | + } |
| 76 | + |
| 77 | + |
| 78 | +publicstaticvoidmain(String...args){ |
| 79 | +intcapacity =2; |
| 80 | +LFUCachetest =newLFUCache(capacity); |
| 81 | +test.set(1,11); |
| 82 | +test.set(2,22); |
| 83 | +System.out.println(test.get(1)); |
| 84 | +test.set(3,33); |
| 85 | +System.out.println(test.get(2)); |
| 86 | +System.out.println(test.get(3)); |
| 87 | + } |
| 88 | + |
| 89 | +} |