LRU算法实现，HashMap与LinkedHashMap源码的部分总结
2024-09-01 08:54:51
关于HashMap与LinkedHashMap源码的一些总结
JDK1.8之后的HashMap底层结构中，在数组(Node<K,V> table)长度大于64的时候且链表(依然是Node)长度大于8的时候，链表在转换为红黑树时，链表长度小于等于6时将不会进行转化为红黑树。目的是为了保证效率。其中链表的结点只有next，LinkedHashMap是在Entry<K,V>中添加before, after（双向链表的定义），保证可迭代，遍历时为存入顺序。
下面是LinkedHashMap中的双向链表定义
//HashMap方法
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//LinkedHashMap----------------------------------------
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//添加结点，添加次序为从右到左，移动last指针
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
LinkedHashMap中有个布尔值accessOrder可以改变访问顺序（get），默认是false，不改变，true则把访问的键值对放到尾部，是实现LRU的关键，且这个值在构造方法中可以获得。
0.75f为默认加载因子，若用户自定义size容量大于capacity*0.75（积为threshold）时，数组就会进行扩容，加载不宜太大太小，太大容易哈希冲突，太小浪费空间
关于removeEldestEntry方法：默认返回false，若为true则会执行以下源码摘除头结点
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
//拿到最右边key - 最早添加的数据key
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
- 但是两者的线程均不安全没有加同步锁（synchronized），而HashTable是安全的
HashMap实现LRU
- 主要思路是：常命中、使用多、和刚添加的移至头部，缓存满了先淘汰尾部
- 最近最久未使用 - 这里指的是Node，需要变换的也是Node，key只作为索引不考虑交换
- tail和head结点用于摘除结点，其中并不包含任何数据
初始化结点
//定义双列集合的结点结构(双向链表的结点)
private class Node {
//key的作用是cache满的时候，hashmap便于淘汰尾部和移除操作,还有遍历
int key;
int value;
Node pre;
Node post;
//构造方法初始化Node数据
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public Node() {
}
}
定义缓存中的成员变量
//定义头尾结点
private Node head;
private Node tail;
//定义当前缓存大小
private int count;
//定义总缓存大小
private int size;
//定义双列集合存储数据
private HashMap<Integer, Node> cache;
//构造方法初始化数据
public LRUCache(int size) {
//双向链表初始化
head = new Node();
tail = new Node();
//结点外的指针置空
head.pre = null;
tail.post = null;
//头尾结点的互连
head.post = tail;
tail.pre = head;
//容量初始化
this.count = 0;
this.size = size;
cache = new HashMap<>(size);
}
访问缓存内容方法
//get方法得到key中缓存的数据
public int get(int key) {
//取得hashmap中的结点数据
Node node = cache.get(key);
//如果没有返回-1
if (node == null)
return -1;
//有，访问后将结点移动到开头，成为最近使用结点
moveToHead(node);
//并返回查询的值
return node.value;
}
当前结点前移至头结点之后
//摘除双链表结点
private void removeNode(Node node) {
node.pre.post = node.post;
node.post.pre = node.pre;
}
//结点插入头部之后
private void insertNode(Node node) {
//前连插入结点
node.pre = head;
node.post = head.post;
//后连插入结点
head.post.pre = node;
head.post = node;
}
private void moveToHead(Node node) {
//摘除结点
removeNode(node);
//插入头结点之后
insertNode(node);
}
调进方法
//put方法存入数据，同时将值放入hashmap的node
public void put(int key, int value) {
//获取Node仓库
Node node = cache.get(key);
//如果没有命中就调进
if (node == null) {
//如果cache满了淘汰尾部
if (count >= size) {
cache.remove(tail.pre.key);
//摘除tail尾部前一个结点
removeNode(tail.pre);
//数量--
count--;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
//由于刚添加，把新数据结点移动到头部
insertNode(newNode);
count++;
}
//如果命中更新该key索引的node值,并移至开头
else {
node.value = value;
//如果目前只有一个节点不用摘
if(count == 1) {
return;
}
moveToHead(node);
}
}
移除其中一个元素方法
//移除缓存中的一个数据
public void remove(int key) {
Node node = cache.get(key);
//没有就什么也不干，有就删除
if (node == null)
return;
cache.remove(key);
removeNode(node);
}
LinkedHashMap实现LRU
package cn.work.demo.demo02;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
public class LRULinkedHashMapCache<K,V> extends LinkedHashMap<K,V> {
//Cache容量
private int size;
//定义一个锁保证线程安全
private final ReentrantLock lock = new ReentrantLock();
//初始化，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在尾部，最早访问的放在头部（数据由last添加至尾部）
public LRULinkedHashMapCache(int size) {
super(size,0.75f,true);
this.size = size;
}
//重写removeEldestEntry方法，若当前容量>size,弹出尾部
@Override
public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
//size()方法，每当LinkedHashMap添加元素时就会++
return size() > size;
}
//重写LinkedHashMap的方法，加锁保证线程安全
@Override
public V put(K key, V value) {
try {
lock.lock();
return super.put(key, value);
} finally {
lock.unlock();
}
}
@Override
public V get(Object key) {
try {
lock.lock();
return super.get(key);
} finally {
lock.unlock();
}
}
@Override
public V remove(Object key) {
try {
lock.lock();
return super.remove(key);
} finally {
lock.unlock();
}
}
}
完整代码
HashMap
package cn.work.demo.demo02;
import java.util.*;
//主要思路是：常命中（使用多）和刚添加的移至头部，缓存满了先淘汰尾部
//最近最久未使用 - 指的是Node里的数据，需要变换的也是Node，key只作为索引不考虑交换
//tail和head结点用于摘除结点，其中并不包含任何数据
public class LRUCache {
//定义双列集合的结点结构(双向链表的结点)
private class Node {
//key的作用是cache满的时候，hashmap便于淘汰尾部和移除操作,还有遍历
int key;
int value;
Node pre;
Node post;
//构造方法初始化Node数据
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public Node() {
}
}
//定义头尾结点
private Node head;
private Node tail;
//定义当前缓存大小
private int count;
//定义总缓存大小
private int size;
//定义双列集合存储数据
private HashMap<Integer, Node> cache;
//构造方法初始化数据
public LRUCache(int size) {
//双向链表初始化
head = new Node();
tail = new Node();
//结点外的指针置空
head.pre = null;
tail.post = null;
//头尾结点的互连
head.post = tail;
tail.pre = head;
//容量初始化
this.count = 0;
this.size = size;
cache = new HashMap<>(size);
}
//get方法得到key中缓存的数据
public int get(int key) {
//取得hashmap中的结点数据
Node node = cache.get(key);
//如果没有返回-1
if (node == null)
return -1;
//有，访问后将结点移动到开头，成为最近使用结点
moveToHead(node);
//并返回查询的值
return node.value;
}
//摘除双链表结点
private void removeNode(Node node) {
node.pre.post = node.post;
node.post.pre = node.pre;
}
//结点插入头部之后
private void insertNode(Node node) {
//前连插入结点
node.pre = head;
node.post = head.post;
//后连插入结点
head.post.pre = node;
head.post = node;
}
private void moveToHead(Node node) {
//摘除结点
removeNode(node);
//插入头结点之后
insertNode(node);
}
//put方法存入数据，同时将值放入hashmap的node
public void put(int key, int value) {
//获取Node仓库
Node node = cache.get(key);
//如果没有命中就调进
if (node == null) {
//如果cache满了淘汰尾部
if (count >= size) {
cache.remove(tail.pre.key);
//摘除tail尾部前一个结点
removeNode(tail.pre);
//数量--
count--;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
//由于刚添加，把新数据结点移动到头部
insertNode(newNode);
count++;
}
//如果命中更新该key索引的node值,并移至开头
else {
node.value = value;
//如果目前只有一个节点不用摘
if (count == 1) {
return;
}
moveToHead(node);
}
}
//移除缓存中的一个数据
public void remove(int key) {
Node node = cache.get(key);
//没有就什么也不干，有就删除
if (node == null)
return;
cache.remove(key);
removeNode(node);
}
//用于遍历cache
public void print() {
Set<Integer> keyset = cache.keySet();
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
int key = (int) iterator.next();
System.out.println(cache.get(key).key + "-->" + cache.get(key).value);
}
}
}
LinkedHashMap
package cn.work.demo.demo02;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
public class LRULinkedHashMapCache<K,V> extends LinkedHashMap<K,V> {
//Cache容量
private int size;
//定义一个锁保证线程安全
private final ReentrantLock lock = new ReentrantLock();
public LRULinkedHashMapCache(int size) {
super(size,0.75f,true);
this.size = size;
}
//初始化，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
//重写removeEldestEntry方法，若当前容量>size,弹出尾部
@Override
public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
//size()方法，每当LinkedHashMap添加元素时就会++
return size() > size;
}
//重写LinkedHashMap的方法，加锁保证线程安全
@Override
public V put(K key, V value) {
try {
lock.lock();
return super.put(key, value);
} finally {
lock.unlock();
}
}
@Override
public V get(Object key) {
try {
lock.lock();
return super.get(key);
} finally {
lock.unlock();
}
}
@Override
public V remove(Object key) {
try {
lock.lock();
return super.remove(key);
} finally {
lock.unlock();
}
}
}
主方法
package cn.work.demo.demo02;
import java.util.Map;
public class LRU {
public static void main(String[] args) {
LRUCache lru = new LRUCache(4);
lru.put(1,2);
lru.put(2,5);
lru.put(8,10);
lru.put(6,5);
lru.get(1);
lru.put(3,8);
lru.get(8);
lru.put(5,2);
lru.put(6,2);
lru.put(7,2);
lru.print();
System.out.println("//-------------------------------");
LRULinkedHashMap<Integer,Integer> linkedHashMap= new LRULinkedHashMap<>(4);
linkedHashMap.put(1,2);
linkedHashMap.put(2,5);
linkedHashMap.put(8,10);
linkedHashMap.put(6,5);
linkedHashMap.get(1);
linkedHashMap.put(3,8);
linkedHashMap.get(8);
linkedHashMap.put(5,2);
linkedHashMap.put(6,2);
linkedHashMap.put(7,2);
for (Map.Entry<Integer,Integer> entry:linkedHashMap.entrySet()){
System.out.println(entry.getKey()+"-->"+entry.getValue());
}
}
}
结果
8-->10
5-->2
6-->2
7-->2
//-------------------------------
8-->10
5-->2
6-->2
7-->2
最新文章
- jsonp使用，spring4.x对jsonp的支持
- 实用redis前需了解的5大事项
- c# 连接Mysql数据库
- .NET 多个程序配置文件合并到主app.config
- guava学习--SettableFuture
- Quality Trimming Via Trimmomatic
- Java数据结构和算法之数组与简单排序
- 闭包在python中的应用，translate和maketrans方法详解
- 11g RAC R2 日常巡检--Grid
- USACO5.4-TeleCowmunication
- Fatal error: Allowed memory size of 8388608 bytes exhausted
- STORM在线业务实践-集群空闲CPU飙高问题排查
- input元素之间的融合
- iOS根据域名获取ip地址
- IFrame父页面和子页面的交互
- 小白的Python之路 day4 生成器
- 数据结构与算法 —— 链表linked list(02)
- Tomcat相关面试题，看这篇就够了！保证能让面试官颤抖！
- 目录命令(tree)
- python使用MySQLdb模块连接MySQL