使用LRU算法实现页面置换算法。LRU算法基于一种假设,长期不使用的数据,在未来的使用性也不大。因此,当数据占用内存达到一定的阙值时,我们要移除最近最少使用的数据。LRU算法中,使用了一种有趣的数据结构,叫做哈希链表。
我们都知道,哈希表是由若干个Key-Value所组成,在逻辑上,这些Key-Value是无所谓排列顺序的。
在哈希链表中,这些Key-Value不再是彼此无关的存在,而是被一个链条串联起来,每一个key-Value都有它的前驱和后继Key-value,就像双向链表中的节点一样。这样一来,无序的哈希表拥有了固定的排列顺序。
1