LRU算法实现，HashMap与LinkedHashMap源码的部分总结
- 2019 年 10 月 20 日
- 笔记
关于HashMap与LinkedHashMap源码的一些总结
- JDK1.8之后的HashMap底层结构中，在数组(Node<K,V> table)长度大于64的时候且链表(依然是Node)长度大于8的时候，链表在转换为红黑树时，链表长度小于等于6时将不会进行转化为红黑树。目的是为了保证效率。其中链表的结点只有next，LinkedHashMap实在Entry<K,V>中添加before, after（双向链表的定义）;，保证可迭代，遍历时为存入顺序。
LinkedHashMap中的双向链表定义
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; } //------------------------------------------------- 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
