Take off, masturbate a LRU cache, the source code turns out to be so simple!

LRU is the abbreviation of Least Recently Used, which is a common page replacement algorithm that selects the most recently unused pages to be eliminated. Simply put, for a set of data, for example: int[] a = {1,2,3,4,5,6}, if the numbers 1 and 2 are frequently used, they will be ranked after 3,4,5,6, and the set becomes as follows: int[] a = {3,4,5,6,1,2}, if a number is not frequently used, it will be ranked at the top! LRU algorithm, generally used in the query of hot data, such as news information, the more users can see more news, the more likely to be seen by other users, for the kind of news that basically no one access, basically similar to the deposit of the sea! In Java, there is such a collection class to achieve this function, it is LinkedHashMap! LinkedHashMap Introduction We all know that in the java collection, LinkedHashMap inherited from HashMap, the underlying is a two-way link table data structure, and HashMap different is that LinkedHashMap initialization stage has a parameter accessOrder, the default is false. replication public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{ /** head node of a two-way link*/ Entry<K,V> head; /* The tail node of the two-way link */ transient LinkedHashMap. If accessOrder is true, the accessed elements will be placed behind the chain, and the order of placement is the order of access * 2. If accessOrder is false, the elements will be traversed in the order of insertion */ final boolean accessOrder; } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. If accessOrder is true, the most recently accessed elements will be placed behind the The order of placement is the order of access, the test is as follows: replication public static void main(String[] args) { //accessOrder default to false Map<String, String> accessOrderFalse = new LinkedHashMap <>(); accessOrderFalse.put("1", "1"); accessOrderFalse.put("2", "2"); accessOrderFalse.put("3", "3"); accessOrderFalse.put("4", "4"); System.out.println("accessOrderFalse: "+accessOrderFalse.toString()); //accessOrder sets to true Map<String, String> accessOrderTrue = new LinkedHashMap<>(16, 0.75f, true); accessOrderTrue.put("1", "1"); accessOrderTrue.put("2", "2"); accessOrderTrue.put("3", "3"); accessOrderTrue.put("4", "4"); accessOrderTrue.get("2");//get key 2 accessOrderTrue.get("3");//get key 3 System.out.println("accessOrderTrue: "+ accessOrderTrue.toString()); } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. The output is as follows: Copy acessOrderFalse: {1=1, 2=2, 3=3, 4=4} accessOrderTrue: {1=1, 4=4, 2=2, 3=3} 1. 2. As we can see, when we set accessOrder to true, the frequently accessed elements are put in front! We use this feature to implement a LRU cache using LinkedHashMap, the operation is as follows: create a LinkedHashMap object, set accessOrder to true; set the capacity of the LinkedHashMap to n, more than this value to delete the excess elements; rewrite the LinkedHashMap method; where removeEldestEntry() means that if it returns true, it will remove the recently unused elements, if it returns false, it will not do any operation, this method will be called every time when add(). Create a LRU cache class with the following contents: copy public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { // Create a LinkedHashMap with a capacity of 3 private static final int MAX_SIZE = 3; /** * Override the removeEldestEntry method in LinkedHashMap * @param eldest * @return */ protected boolean removeEldestEntry(Map.Entry eldest) { //If the number of elements in the container is greater than MAX_SIZE, each time an element is added, remove the most recently unused element in the container return size() > MAX_SIZE; } public LRULinkedHashMap() { // Set the initialized capacity of the LinkedHashMap with a load factor of 0.75f and accessOrder set to true super(MAX_SIZE, 0.75f, true); } } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. test use: replication public static void main(String[] args) { LRULinkedHashMap<String,String> cache = new LRULinkedHashMap<String,String>(); cache.put("1", "a"); cache.put("2", "b"); cache.put("3", "c") System.out.println("Initial cache content: " + cache.toString()); cache.get("2"); System.out.println("After querying the element with key 2, cache content: " + cache.toString()); cache.put("4", "d"); System.out.println("After adding new elements, cache content: " + cache.toString()); } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. The output is as follows: Copy Initial cache content: {1=a, 2=b, 3 =After querying the element with key 2, the cache content: {1=a, 3=c, 2=b} After adding new elements, the cache content: {3=c, 2=b, 4=d} 1. 2. 3. Initial cache content: {1=a, 2=b, 3=c} After querying the element with key 2, the cache content: {1=a, 3=c, 2=b} After adding new elements, the cache content: {3=c, 2=b, 4=d}