图解LinkedHashMap的LRU-白红宇

图解LinkedHashMap的LRU

阅读量：4213 次

发布时间：2019-05-26

本文共 770 字，大约阅读时间需要 2 分钟。

数据结构支持：双向循环链表

改造过程：

1，在LinkedHashMap的初始化过程添加一个dumy的header双向链表头

2，在Entry添加before和after

过程演示：

1. dumy的header

before(header)<----header --->after(header)

2. 插入第一个entry

entry1

/ \

before(header)<----header --->after(header)

3. 插入第二个entry

header<----entry1---->entry2---->header--->entry1

新插入的元素总是放在header之前，而header的after总是总早放入链表中的那个元素entry1

4. 当其中一个entry3被访问时，将entry3从原位置删除并移动到header之前

访问之前

header<----entry1---->entry2---->entry3----->entry4---->header--->entry1

访问之后

从当前位置删除：

header<----entry1---->entry2----->entry4---->header--->entry1

插入到header之前

header<----entry1---->entry2---->entry4----->entry3---->header--->entry1

5. 执行LRU清除操作

删除header.after即entry1并重新指向entry1的after。

header<-----entry2---->entry4----->entry3---->header--->entry2

code：

请参照addToHead以及recordAccess

转载地址：http://wqdmi.baihongyu.com/

你可能感兴趣的文章

linux performance tool

查看>>

test-definitions/blob/master/auto-test/bazel/bazel.sh

查看>>

test-definitions/blob/master/auto-test/bigdata/bigdata.sh

查看>>

/test-definitions/blob/master/auto-test/blktrace/blktrace.sh

查看>>

test-definitions/blob/master/auto-test/blogbench/blogbench.sh

查看>>

test-definitions/blob/master/auto-test/boost/boost.sh

查看>>

Java多态性理解

查看>>

Intellij Idea 工具在java文件中怎么避免 import .＊包，以及import包顺序的问题

查看>>

IDEA Properties中文unicode转码问题

查看>>

Oracle中Blob转换成Clob

查看>>

明明开发时间很赶，我为什么还要重构整个项目

查看>>

邻接表有向图是否有环 C实现（dfs - 反向边）

查看>>

有向图是否有环（邻接表）拓扑排序法

查看>>

已知中序和前序后序任一求另外一种 C实现~

Dijkstra算法求单源含权最短路径（邻接表有向图）C实现

查看>>

Dijkstra（邻接矩阵有向图）C 实现~

查看>>