LRU算法设计

名词定义

用来实现Lru的结构称之为时间包容器

时间包容器

时间包容器下面有几个时间包（以下以AgeBag代称），这些时间包内部主要是一个并发双向队列用来存储节点。每一个时间包允许插入的节点数量相同。而所有的时间包以单向循环队列方式连接。

当前时间包指针

容器之中有一个指针（以下以CurAgeIndex代称）用来表示当前使用的时间包。当有节点需要插入的时候就会尝试在当前时间包进行插入

节点

AgeBag中存储的内容，节点中包含一个ageindex指针。默认为插入时的AgeBag。如果节点被读取了，则设置ageindex为CurAgeIndex的值。

算法思想

在有节点进行插入的时候，选择将节点插入到当前的时间包中。如果当前时间包满就移动当前时间包指针到下一个时间包并且进行插入。每一个节点内都有一个时间包指针，默认值是当前插入的时间包。
每当有节点被读取的时候就将节点内部的时间包指针指向当前的时间包。
当需要执行清理的时候，将一个时间包内节点的时间包指针不指向当前时间包的节点全部删除
由于当前时间包指针是单向移动，所以指针的下一个时间包是距离当前使用最远的一个时间包。清理这个时间包就完成了清理最不常使用的节点的目的，也就完成了lru算法。

初始化工作

确定时间包个数

时间包的个数不能太多，否则每一个时间包中可以容纳的节点很少，在插入的时候更容易发生时间包满导致当前时间包指针移动。但也不能太少，特别是不能少于2，否则就失去作用。

连接时间包

将所有的时间包以单向链表的形式连接起来。并且设置当前时间包指针的值

执行操作

节点插入

当有节点需要执行插入的时候，从当前时间包中插入。如果当前时间包满，则查询下一个时间包是否满，如果满则首先将下一个时间包中节点的时间包指针不为当前时间包的节点全部删除。然后设置当前时间包指针为下一个时间包。执行插入并且返回。在有节点需要插入的时