Shulou(Shulou.com)06/02 Report--

This article mainly explains "java LRU algorithm and Apache LRUMap source code example analysis", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Now let the editor to take you to learn "java LRU algorithm and Apache LRUMap source code example analysis" it!

1. What is LRU?

LRU (least recently used): least recently used

LRU is a classic algorithm that defines a last use time for an element in a container. When a new element is written, if the container is full, the least recently used element is eliminated and the new element is written.

1.1 Custom requirements for implementing LRU

For example, redis, how to implement a simple version of redis cache by yourself.

Then we need a data structure that supports set and get operations.

1) get operation time complexity O (1)

2) RLU algorithm needs to be supported. When there is insufficient space, the least used elements need to be removed to make room for new elements.

3) time lapse remove (this aside, it's troublesome).

1.2 Apache LRUMap example 1.2.1 pom depends on org.apache.commons commons-collections4 4.2 1.2.2 demoLRUMap map = new LRUMap (3); map.put ("1", "1"); map.put ("2", "2"); map.put ("3", "3"); map.get ("2") System.out.println ("- -"); map.forEach ((KMagnev)-> System.out.println (k + "\ t" + v)); map.put ("4", "4"); map.put ("5", "5") System.out.println ("- -"); map.forEach ((KMagnev)-> System.out.println (k + "\ t" + v)); map.put ("6", "6") System.out.println ("- -"); map.forEach ((KBEN v)-> System.out.println (k + "\ t" + v))

The results are as follows:

-

eleven

thirty-three

twenty-two

-

twenty-two

forty-four

fifty-five

-

forty-four

fifty-five

sixty-six

You can see that after the position of get ("2"), 2 is moved, then the order of removal is delayed.

When the capacity is insufficient, it is always removed, the one with the least use and the one with the longest time.

two。 Source code parsing 2.1.Designs public class LRUMap extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {

Check out AbstractLinkedMap,AbstractHashedMap further

Public abstract class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap {public class AbstractHashedMap extends AbstractMap implements IterableMap {

The essence is custom AbstractMap.

Let's take a look at HashMap LinkedHashMap

Public class LinkedHashMap extends HashMap implements Mappublic class HashMap extends AbstractMap implements Map, Cloneable, Serializable {

You can see that the essence of AbstractMap,AbstractHashedMap,LRUMap is also HashMap.

2.2 data structure protected static final int DEFAULT_MAX_SIZE = 100; public LRUMap () {this (DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);}

You can see that the default initialization capacity is 100, and the maximum capacity is 100.

Further tracking

Public LRUMap (final int maxSize, final float loadFactor, final boolean scanUntilRemovable) {this (maxSize, maxSize, loadFactor, scanUntilRemovable);} / * Constructs a new, empty map with the specified max / initial capacity and load factor. * * @ param maxSize the maximum size of the map * @ param initialSize the initial size of the map * @ param loadFactor the load factor * @ param scanUntilRemovable scan until a removeable entry is found, default false * @ throws IllegalArgumentException if the maximum size is less than one * @ throws IllegalArgumentException if the initial size is negative or larger than the maximum size * @ throws IllegalArgumentException if the load factor is less than zero * @ since 4.1 * / public LRUMap (final int maxSize Final int initialSize, final float loadFactor, final boolean scanUntilRemovable) {super (initialSize, loadFactor) If (maxSize

MaxSize) {throw new IllegalArgumentException ("LRUMap initial size must not be greather than max size");} this.maxSize = maxSize; this.scanUntilRemovable = scanUntilRemovable;}

Tracking super (initialSize, loadFactor)

Public abstract class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap {protected AbstractLinkedMap (final int initialCapacity, final float loadFactor) {super (initialCapacity, loadFactor);} / super, trace public class AbstractHashedMap extends AbstractMap implements IterableMap {/ / define some basic initialization data / * * The default capacity to use * / protected static final int DEFAULT_CAPACITY = 16; / * The default threshold to use * / protected static final int DEFAULT_THRESHOLD = 12 / * * The default load factor to use * / protected static final float DEFAULT_LOAD_FACTOR = 0.75f; / * * The maximum capacity allowed * / protected static final int MAXIMUM_CAPACITY = 1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.