使用双向链表实现简单的LRU
什么是LRU
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
什么是链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
什么是单向链表
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。
什么是双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
HashMap中单向链表Node对象
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
使用双向链表实现Map
public class MyLruMap<K, V> implements Map<K, V> {
private Node<K, V> head;
private Node<K, V> tail;
private int size = 0;
/**
* 最大存储个数
*/
private int capacity = -1;
public MyLruMap(int capacity) {
this.capacity = capacity;
}
public MyLruMap() {
}
@Override
public String toString() {
if (size == 0) {
return "";
}
StringBuilder stringBuilder = new StringBuilder();
Node n = head;
while (n != null) {
stringBuilder.append(n.key).append("=").append(n.value).append(",");
n = n.next;
}
return stringBuilder.toString().substring(0, stringBuilder.toString().length() - 1);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean containsKey(Object key) {
return getNodeByKey(key) != null;
}
@Override
public boolean containsValue(Object value) {
return getNodeByValue(value) != null;
}
@Override
public V get(Object key) {
Node<K, V> node = getNodeByKey(key);
if (node != null) {
// 访问一次就将该node放置到head
remove(node);
setHead(node);
size++;
}
return node != null ? node.value : null;
}
private void setHead(Node node){
if (head != null) {
node.next = head;
head.prev = node;
}
head = node;
if (tail == null) {
tail = node;
}
}
@Override
public V put(K key, V value) {
Node<K, V> node = getNodeByKey(key);
if (node != null) {
node.value = value;
remove(node);
} else {
node = new Node(key, value);
if (size >= capacity) {
// 删除尾部节点
remove(tail);
}
}
setHead(node);
size++;
return value;
}
@Override
public V remove(Object key) {
Node<K, V> node = getNodeByKey(key);
if (node != null) {
remove(node);
return node.value;
}
return null;
}
private void remove(Node node){
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
size--;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
if (m == null || m.size() == 0) {
return;
}
for (K k:m.keySet()) {
put(k, m.get(k));
}
}
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}
@Override
public Set<K> keySet() {
Node<K, V> p = head;
Set<K> keys = new HashSet<>();
while (p != null) {
keys.add(p.key);
p = p.next;
}
return keys;
}
@Override
public Collection<V> values() {
Node<K, V> p = head;
Collection<V> values = new ArrayList<>();
while (p != null) {
values.add(p.value);
p = p.next;
}
return values;
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> entries = new HashSet<>();
Node<K, V> p = head;
while (p != null) {
entries.add(p);
p = p.next;
}
return entries;
}
private Node<K, V> getNodeByKey(Object key){
if (head == null) {
return null;
}
Node<K, V> n = head;
do {
if (n.key.equals(key)) {
break;
}
n = n.next;
} while (n != null);
return n;
}
private Node<K, V> getNodeByValue(Object value){
if (head == null) {
return null;
}
Node<K, V> n = head;
do {
if (n.value.equals(value)) {
break;
}
n = n.next;
} while (n != null);
return n;
}
private class Node<K, V> implements Entry<K, V> {
private final K key;
private V value;
private Node<K, V> prev;
private Node<K, V> next;
Node(K key, V value){
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
this.value = value;
return value;
}
}
正文到此结束
