LRU is the abbreviation of Least Recently Used, which translates as "least recently used". LRU cache is implemented using this principle. Simply put, it caches a certain amount of data. When it exceeds When the threshold is set, some expired data will be deleted.
For example, we cache 10,000 pieces of data. When the data is less than 10,000, we can add it at will. When it exceeds 10,000, we need to add new data and delete the expired data to ensure that we cache a maximum of 10,000 pieces. So how to determine which expired data to delete? If implemented using the LRU algorithm, the oldest data will be deleted.
Let’s talk about the Java version of LRU cache implementation: (Recommended: java video tutorial)
There are usually two options for implementing LRU cache in Java, one is Using LinkedHashMap, one is to design the data structure yourself, using linked list HashMap
LRU Cache's LinkedHashMap implementation
LinkedHashMap itself has implemented sequential storage By default, the elements are stored in the order in which they are added. You can also enable storage in the order of access, that is, the most recently read data is placed at the front, and the earliest read data is placed at the end. Then it also has a judgment whether to delete the most recent data. The method for old data returns false by default, that is, the data is not deleted.
The way we use LinkedHashMap to implement LRU caching is to implement a simple extension of LinkedHashMap. There are two extension methods, one is inheritance and the other is delegation.
//LinkedHashMap的一个构造函数,当参数accessOrder为true时,即会按照访问顺序排序,最近访问的放在最前,最早访问的放在后面 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } //LinkedHashMap自带的判断是否删除最老的元素方法,默认返回false,即不删除老数据 //我们要做的就是重写这个方法,当满足一定条件时删除老数据 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
LRU cache LinkedHashMap (inheritance) implementation
It is relatively simple to implement using the inheritance method, and implements the Map interface, which can be used in a multi-threaded environment You can use the Collections.synchronizedMap() method to implement thread-safe operations
package cn.lzrabbit.structure.lru; import java.util.LinkedHashMap; import java.util.Map; /** * Created by liuzhao on 14-5-15. */ public class LRUCache2<K, V> extends LinkedHashMap<K, V> { private final int MAX_CACHE_SIZE; public LRUCache2(int cacheSize) { super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true); MAX_CACHE_SIZE = cacheSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_CACHE_SIZE; } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (Map.Entry<K, V> entry : entrySet()) { sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue())); } return sb.toString(); } }
This is a relatively standard implementation. In actual use, writing like this is still a bit cumbersome. A more practical method is to write like the following, omitting The trouble of seeing a class alone
final int cacheSize = 100; Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { return size() > cacheSize; } };
LRU cache LinkedHashMap (delegation) implementation
The delegation method is more elegant, but because Map is not implemented interface, so thread synchronization needs to be done by yourself
package cn.lzrabbit.structure.lru; import java.util.LinkedHashMap; import java.util.Map; import java.util.Set; /** * Created by liuzhao on 14-5-13. */ public class LRUCache3<K, V> { private final int MAX_CACHE_SIZE; private final float DEFAULT_LOAD_FACTOR = 0.75f; LinkedHashMap<K, V> map; public LRUCache3(int cacheSize) { MAX_CACHE_SIZE = cacheSize; //根据cacheSize和加载因子计算hashmap的capactiy,+1确保当达到cacheSize上限时不会触发hashmap的扩容, int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1; map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_CACHE_SIZE; } }; } public synchronized void put(K key, V value) { map.put(key, value); } public synchronized V get(K key) { return map.get(key); } public synchronized void remove(K key) { map.remove(key); } public synchronized Set<Map.Entry<K, V>> getAll() { return map.entrySet(); } public synchronized int size() { return map.size(); } public synchronized void clear() { map.clear(); } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (Map.Entry entry : map.entrySet()) { sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue())); } return sb.toString(); } }
LRU Cache's linked list HashMap implementation
Note: This implementation is not thread-safe. If used in a multi-threaded environment, synchronized needs to be added to the relevant methods to achieve thread-safe operations
package cn.lzrabbit.structure.lru; import java.util.HashMap; /** * Created by liuzhao on 14-5-12. */ public class LRUCache1<K, V> { private final int MAX_CACHE_SIZE; private Entry first; private Entry last; private HashMap<K, Entry<K, V>> hashMap; public LRUCache1(int cacheSize) { MAX_CACHE_SIZE = cacheSize; hashMap = new HashMap<K, Entry<K, V>>(); } public void put(K key, V value) { Entry entry = getEntry(key); if (entry == null) { if (hashMap.size() >= MAX_CACHE_SIZE) { hashMap.remove(last.key); removeLast(); } entry = new Entry(); entry.key = key; } entry.value = value; moveToFirst(entry); hashMap.put(key, entry); } public V get(K key) { Entry<K, V> entry = getEntry(key); if (entry == null) return null; moveToFirst(entry); return entry.value; } public void remove(K key) { Entry entry = getEntry(key); if (entry != null) { if (entry.pre != null) entry.pre.next = entry.next; if (entry.next != null) entry.next.pre = entry.pre; if (entry == first) first = entry.next; if (entry == last) last = entry.pre; } hashMap.remove(key); } private void moveToFirst(Entry entry) { if (entry == first) return; if (entry.pre != null) entry.pre.next = entry.next; if (entry.next != null) entry.next.pre = entry.pre; if (entry == last) last = last.pre; if (first == null || last == null) { first = last = entry; return; } entry.next = first; first.pre = entry; first = entry; entry.pre = null; } private void removeLast() { if (last != null) { last = last.pre; if (last == null) first = null; else last.next = null; } } private Entry<K, V> getEntry(K key) { return hashMap.get(key); } @Override public String toString() { StringBuilder sb = new StringBuilder(); Entry entry = first; while (entry != null) { sb.append(String.format("%s:%s ", entry.key, entry.value)); entry = entry.next; } return sb.toString(); } class Entry<K, V> { public Entry pre; public Entry next; public K key; public V value; } }
FIFO implementation of LinkedHashMap
FIFO is The abbreviation of First Input First Output, which is often referred to as first in, first out. By default, LinkedHashMap is saved in the order of addition. We only need to rewrite the removeEldestEntry method to easily implement a FIFO cache. The simplified version of the implementation code is as follows
final int cacheSize = 5; LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() { @Override protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) { return size() > cacheSize; } };
Calling example
Test code
package cn.lzrabbit.structure.lru; import cn.lzrabbit.ITest; import java.util.LinkedHashMap; import java.util.Map; /** * Created by liuzhao on 14-5-15. */ public class LRUCacheTest { public static void main(String[] args) throws Exception { System.out.println("start..."); lruCache1(); lruCache2(); lruCache3(); lruCache4(); System.out.println("over..."); } static void lruCache1() { System.out.println(); System.out.println("===========================LRU 链表实现==========================="); LRUCache1<Integer, String> lru = new LRUCache1(5); lru.put(1, "11"); lru.put(2, "11"); lru.put(3, "11"); lru.put(4, "11"); lru.put(5, "11"); System.out.println(lru.toString()); lru.put(6, "66"); lru.get(2); lru.put(7, "77"); lru.get(4); System.out.println(lru.toString()); System.out.println(); } static <T> void lruCache2() { System.out.println(); System.out.println("===========================LRU LinkedHashMap(inheritance)实现==========================="); LRUCache2<Integer, String> lru = new LRUCache2(5); lru.put(1, "11"); lru.put(2, "11"); lru.put(3, "11"); lru.put(4, "11"); lru.put(5, "11"); System.out.println(lru.toString()); lru.put(6, "66"); lru.get(2); lru.put(7, "77"); lru.get(4); System.out.println(lru.toString()); System.out.println(); } static void lruCache3() { System.out.println(); System.out.println("===========================LRU LinkedHashMap(delegation)实现==========================="); LRUCache3<Integer, String> lru = new LRUCache3(5); lru.put(1, "11"); lru.put(2, "11"); lru.put(3, "11"); lru.put(4, "11"); lru.put(5, "11"); System.out.println(lru.toString()); lru.put(6, "66"); lru.get(2); lru.put(7, "77"); lru.get(4); System.out.println(lru.toString()); System.out.println(); } static void lruCache4() { System.out.println(); System.out.println("===========================FIFO LinkedHashMap默认实现==========================="); final int cacheSize = 5; LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() { @Override protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) { return size() > cacheSize; } }; lru.put(1, "11"); lru.put(2, "11"); lru.put(3, "11"); lru.put(4, "11"); lru.put(5, "11"); System.out.println(lru.toString()); lru.put(6, "66"); lru.get(2); lru.put(7, "77"); lru.get(4); System.out.println(lru.toString()); System.out.println(); } }
Running results
"C:\Program Files (x86)\Java\jdk1.6.0_10\bin\java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\charsets.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\deploy.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\javaws.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jce.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jsse.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\management-agent.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\plugin.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\resources.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\rt.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\localedata.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;D:\SVN\projects\Java\Java.Algorithm\target\test-classes;D:\SVN\projects\Java\Java.Algorithm\target\classes;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain Main start... ===========================LRU 链表实现=========================== 5:11 4:11 3:11 2:11 1:11 4:11 7:77 2:11 6:66 5:11 ===========================LRU LinkedHashMap(inheritance)实现=========================== 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ===========================LRU LinkedHashMap(delegation)实现=========================== 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ===========================FIFO LinkedHashMap默认实现=========================== {1=11, 2=11, 3=11, 4=11, 5=11} {3=11, 4=11, 5=11, 6=66, 7=77} over... Process finished with exit code 0
For more java knowledge, please pay attentionjava Basic Tutorial column.
The above is the detailed content of LRU cache implementation in java. For more information, please follow other related articles on the PHP Chinese website!

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

SublimeText3 English version
Recommended: Win version, supports code prompts!

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools
