Recently Alibaba telephone interview was asked how to use fixed capacity HashMap, realization LRU algorithm . At that time, he was confused , Usually used HashMap It's just for quick access to data , The capacity is unlimited .
I thought about it for a long time , Think about it node Node expansion , Add reference count , After reaching the specified capacity , Delete the with the least reference count .
The interviewer questioned how inefficient it was , Can we optimize it .
When you think about deleting , All elements need to be traversed , At the cost of O(n), It's too big . It's possible to use the smallest heap to filter . What are the node values for heap building , I didn't think about this one , It's stuck .
After the interview , I searched the Internet , Just found out Java The official has reserved it for us LRU Framework of algorithm , stay LinkedHashMap in . We just need to expand , The code example is as follows ：
/** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified
initial capacity, load factor and ordering mode. * * @param initialCapacity the
initial capacity * @param loadFactor the load factor * @param accessOrder the
ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for
insertion-order * @throws IllegalArgumentException if the initial capacity is
negative * or the load factor is nonpositive */ public LinkedHashMap(int
initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity,
loadFactor); this.accessOrder = accessOrder; } // The method is as follows protected , To be clear is to be inherited , rewrite
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
use accessOrder To identify is to use the access order , Or insert order . The default is the insertion order . When accessOrder For access order , When the capacity is fixed , mean LRU
Examples are as follows ：
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> { /** * */ private
static final long serialVersionUID = 1882839504956564761L; private int capacity;
public LRULinkedHashMap(int capacity) { super(capacity,0.75f,true); this.
capacity= capacity; } @Override public boolean removeEldestEntry(Map.Entry<K,V>
eldest) { System.out.println(" Will be based on LRU algorithm , Delete least recently used elements ：key= "+eldest.getKey()+"
value= "+eldest.getValue()+" ."); // This line of code is the key , Once the capacity exceeds the limit , In accordance with LRU Delete return size()>
capacity; } } public class Test { public static void main(String[] args) {
testLinkedHashMap(); testLRULinkedHashMap(); } public static void
testLinkedHashMap() { // Fixed capacity ,accessOrder=true Map<Integer, Integer> map = new
LinkedHashMap<Integer, Integer>(5, 0.75f, true); map.put(1, 1); map.put(2, 2);
map.put(3, 3); map.put(4, 4); map.put(5, 5); // At this time, the output 1,2,3,4,5 for(Iterator<Map.
Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) { System
.out.println(it.next().getValue()); } map.put(4, 4); map.put(6, 6);
// At this time, the output 1,2,3,5,4,6（ Automatic expansion ） for(Iterator<Map.Entry<Integer, Integer>> it = map.
entrySet().iterator(); it.hasNext();) { System.out.println(it.next().getValue())
; } } public static void testLRULinkedHashMap() { // Fixed capacity ,accessOrder=true Map<
Integer, Integer> map = new LRULinkedHashMap<Integer, Integer>(5); map.put(1, 1)
; map.put(2, 2); map.put(3, 3); map.put(4, 4); map.put(5, 5); // At this time, the output 1,2,3,4,5
for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.
hasNext();) { System.out.println(it.next().getValue()); } map.put(4, 4); map.put
(6, 6); // At this time, the output 2,3,5,4,6（ Capacity locking , Delete ） for(Iterator<Map.Entry<Integer, Integer>> it
= map.entrySet().iterator(); it.hasNext();) { System.out.println(it.next().
getValue()); } } }
Technology