What is the elimination strategy?
In the case of a certain container capacity, with the gradual increase of elements, the capacity will eventually be full. The elimination strategy is used to eliminate some elements to free up container space when the capacity is about to be full. Common elimination strategies include FIFO, LRU (The Least Recently Used algorithm) and LFU (The Least Frequently Used algorithm).
FIFO
The idea of FIFO(first in, first out) is based on queues. If a piece of data is entered first, it can be assumed that it is less likely to be accessed in the future. When the space is full, the data that comes in first is replaced by the data that comes in first.
implementation
Using a bidirectional list, place the new element at the end of the list, and when the list is full, remove the element at the head of the queue. In Java, LinkedHashMap inherited hashMap and overwrote newNode, visting emoval, afterNodeInsertion, and afterNodeAccess. We can rewrite the afterNodeInsertion method in LinkedHashMap to implement FIFO algorithm. After adding an element to the queue, the element will be inserted at the end of the queue.
LRU
The idea of LRU (The Least Recently Used algorithm) is based on time. If an element has not been Used for The longest time, it has The Least chance of being Used in The future, and The element that has not been Used for The longest time can be removed from The container.
implementation
The LRU can also use a two-way queue. Each time an element is accessed, it moves the element to the end of the list. At this point, the element at the head of the list is the one that has not been accessed for the longest. When accessOrder=true in the LinkedHashMap, each access to the map puts the element at the end of the internally maintained list, making the element at the head the oldest unused element.
LFU
LFU (Least Frequently Used algorithm) is based on frequency. If an element is Used the Least Frequently, it will be Used the Least Frequently in the future. If the element is Used the same frequency, then the access time of the element is compared.
implementation
The LFU determines substitution elements based on times and access times, so we can use: HashMap
: to store key values. HashMap
: Use another Map to store the number of accesses per key. HashMap
>: store K if two elements are accessed the same number of times. In the whole process, we need to record the number of visits to maintain a minimum min, when elements capacity more than expected, and need replacement elements can be from the same number of times the Map inside in min, for all the K K value, to determine whether these elements are eliminated, or based on other factors (access timestamp), to filter out the need to eliminate elements.