Detailed explanation of how to use LRU algorithm in Java

This article mainly introduces the java LRU algorithm. It briefly introduces the concept of the LRU algorithm and analyzes the specific usage of the LRU algorithm in the form of examples. Friends in need can refer to it

The examples in this article describe java Introduction and usage of LRU algorithm. Share it with everyone for your reference, the details are as follows:

1. Foreword

When users use Internet-connected software, they will always start from the Internet When the same data needs to be used multiple times within a period of time, it is impossible for the user to go to the Internet to request every time, which is a waste of time and a waste of the network.

At this time, you can The data requested by the user is saved, but not all data is saved, which will cause a waste of memory. The idea of ​​​​the LRU algorithm can be applied.

2. Introduction to LRU

LRU is the Least Recently Used algorithm, which can process data that has not been used for a long time. delete.

LRU is also well reflected in some people's emotions. When you are in contact with a group of friends, the relationship with the people you often communicate with is very good. If you don't contact them for a long time and you will probably never contact them again, you will have lost this friend.

3. The following code shows the LRU algorithm:

The simplest way is to use LinkHashMap, because it has a method itself It is to remove additional old data within the set cache range

public class LRUByHashMap<K, V> {
 /*
 * 通过LinkHashMap简单实现LRU算法
 */
 /**
 * 缓存大小
 */
 private int cacheSize;
 /**
 * 当前缓存数目
 */
 private int currentSize;
 private LinkedHashMap<K, V> maps;
 public LRUByHashMap(int cacheSize1) {
 this.cacheSize = cacheSize1;
 maps = new LinkedHashMap<K, V>() {
  /**
  *
  */
  private static final long serialVersionUID = 1;
  // 这里移除旧的缓存数据
  @Override
  protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
  // 当超过缓存数量的时候就将旧的数据移除
  return getCurrentSize() > LRUByHashMap.this.cacheSize;
  }
 };
 }
 public synchronized int getCurrentSize() {
 return maps.size();
 }
 public synchronized void put(K k, V v) {
 if (k == null) {
  throw new Error("存入的键值不能为空");
 }
 maps.put(k, v);
 }
 public synchronized void remove(K k) {
 if (k == null) {
  throw new Error("移除的键值不能为空");
 }
 maps.remove(k);
 }
 public synchronized void clear() {
 maps = null;
 }
 // 获取集合
 public synchronized Collection<V> getCollection() {
 if (maps != null) {
  return maps.values();
 } else {
  return null;
 }
 }
 public static void main(String[] args) {
 // 测试
 LRUByHashMap<Integer, String> maps = new LRUByHashMap<Integer, String>(
  3);
 maps.put(1, "1");
 maps.put(2, "2");
 maps.put(3, "3");
 maps.put(4, "4");
 maps.put(5, "5");
 maps.put(6, "6");
 Collection<String> col = maps.getCollection();
 System.out.println("存入缓存中的数据是--->>" + col.toString());
 }
}

The effect after running:

The code obviously put 6 Entries but only three were displayed in the end. The three in between were old and were clicked out

The second method is to use a doubly linked list + HashTable

The function of the doubly linked list is to record the location, while the HashTable is used as a container to store data.

Why use HashTable instead of HashMap?

1. Neither the key nor the value of HashTable can be null;
2. The LRU implemented above using LinkHashMap is useful for synchronized, allowing threads to process it synchronously, thus avoiding the need for multi-threads to process unified data. Causing problems

HashTable has its own synchronization mechanism, so multi-threads can correctly process HashTable.

All caches are connected with positional double linked lists. When a position is hit, the position will be adjusted to the position of the head of the linked list by adjusting the pointing of the linked list. The newly added Cache will be added directly. to the head of the linked list. In this way, after multiple cache operations,

the most recently hit ones will be moved toward the head of the linked list, and those without hits will be moved to the back of the linked list. The tail of the linked list represents the least recently used Cache. . When content needs to be replaced, the last position of the linked list is the least hit position. We only need to eliminate the last part of the linked list

public class LRUCache {
 private int cacheSize;
 private Hashtable<Object, Entry> nodes;//缓存容器
 private int currentSize;
 private Entry first;//链表头
 private Entry last;//链表尾
 public LRUCache(int i) {
 currentSize = 0;
 cacheSize = i;
 nodes = new Hashtable<Object, Entry>(i);//缓存容器
 }
 /**
 * 获取缓存中对象,并把它放在最前面
 */
 public Entry get(Object key) {
 Entry node = nodes.get(key);
 if (node != null) {
  moveToHead(node);
  return node;
 } else {
  return null;
 }
 }
 /**
 * 添加 entry到hashtable, 并把entry 
 */
 public void put(Object key, Object value) {
 //先查看hashtable是否存在该entry, 如果存在，则只更新其value
 Entry node = nodes.get(key);
 if (node == null) {
  //缓存容器是否已经超过大小.
  if (currentSize >= cacheSize) {
  nodes.remove(last.key);
  removeLast();
  } else {
  currentSize++;
  }  
  node = new Entry();
 }
 node.value = value;
 //将最新使用的节点放到链表头，表示最新使用的.
 node.key = key
 moveToHead(node);
 nodes.put(key, node);
 }
 /**
 * 将entry删除, 注意：删除操作只有在cache满了才会被执行
 */
 public void remove(Object key) {
 Entry node = nodes.get(key);
 //在链表中删除
 if (node != null) {
  if (node.prev != null) {
  node.prev.next = node.next;
  }
  if (node.next != null) {
  node.next.prev = node.prev;
  }
  if (last == node)
  last = node.prev;
  if (first == node)
  first = node.next;
 }
 //在hashtable中删除
 nodes.remove(key);
 }
 /**
 * 删除链表尾部节点，即使用最后 使用的entry
 */
 private void removeLast() {
 //链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
 if (last != null) {
  if (last.prev != null)
  last.prev.next = null;
  else
  first = null;
  last = last.prev;
 }
 }
 /**
 * 移动到链表头，表示这个节点是最新使用过的
 */
 private void moveToHead(Entry node) {
 if (node == first)
  return;
 if (node.prev != null)
  node.prev.next = node.next;
 if (node.next != null)
  node.next.prev = node.prev;
 if (last == node)
  last = node.prev;
 if (first != null) {
  node.next = first;
  first.prev = node;
 }
 first = node;
 node.prev = null;
 if (last == null)
  last = first;
 }
 /*
 * 清空缓存
 */
 public void clear() {
 first = null;
 last = null;
 currentSize = 0;
 }
}
class Entry {
 Entry prev;//前一节点
 Entry next;//后一节点
 Object value;//值
 Object key;//键
}

The above is the detailed content of Detailed explanation of how to use LRU algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!