Preliminary understanding of cache elimination algorithm (LRU and LFU)

API： namely Application Programming Interface （ Application programming interface ）. The operating system will encapsulate some complex underlying operations into simple functions , The programmer only needs to call the corresponding function to realize the low-level detailed operation .（c There is printf、scanf、fopen, stay c++ in API Including functions and classes ）
Cache elimination algorithm ： Memory capacity is limited , When the data you want to cache exceeds the capacity , You have to delete some data , What data is deleted at this time , What data is retained , Namely LRU Algorithm and LFU Algorithm ,FU What is emphasized is that Number of visits , and LRU What is emphasized is that Access time .
LRU： namely Least Recently Used （ Least recently used algorithm ）. Data that has not been used for a long time is regarded as useless data , When the cache is full , Priority will be given to deleting these identified data .
LRU In order to achieve the minimum time complexity of storing and obtaining key value pairs , Use Hash list To realize the core of the algorithm , Hash table storage key, Every key Mapping key value pairs in a two-way linked list , In order to achieve the purpose of fast searching the linked list key（ Hash table search time complexity O（1））.

LFU： namely Least Frequently Used （ The least frequently used algorithm ）. It is also the least likely that the data accessed the least times in a certain period will be accessed in the future . When the cache is full , Priority will be given to deleting these identified data .
LFU In order to select and eliminate according to frequency , So... Is adopted Double hash table As the core algorithm , First hash table fre_table, Its key Is the frequency of visits , Its value It's a two-way list , Each node of the bidirectional linked list contains three elements ：key,value, as well as count. The second hash table key_table, Its key That is, the of the two-way linked list key,value Is a pointer to the corresponding position in the linked list .

（ The following supplementary code part ）
author ： Easy to wind and dust

Game programming ️, A game development favorite ~

If the picture is not displayed for a long time , Please use Chrome Kernel browser .