题目：
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
LRU原理与理解
待更新...
实现
public class LruIntegerCache {
//最大容量
private int mMaxCapacity;
//当前容量
private int mCurCapacity;
//头结点
private Node mHead = new Node("Head");
//尾巴结点
private Node mTail = new Node("Tail");
public LruIntegerCache(int maxCapacity) {
mMaxCapacity = maxCapacity;
init();
}
private void init() {
//构造最初链表head-->tail
mHead.next = mTail;
mTail.pre = mHead;
}
/**
* 获取数据
* 1:遍历链表,查找是否有key只想的数据
* 2:没有数据,返回默认值。因为此类专门存储是的int类型数据所以返回-1
* 2:有数据,把此数据【添加到链表首部】
*
* @param key key
* @return value
*/
public int get(int key) {
boolean hasFlag = false;
Node nextNode = mHead.next;
//遍历链表(优化遍历:为了加快查找速度,可以分别从表头和表尾同时开始遍历此链表)
while (null != nextNode && nextNode != mTail) {
if (nextNode.key == key) {
hasFlag = true;
break;
}
nextNode = nextNode.next;
}
//有数据
//1:先把当前节点从链表中移除
//2:把当前节点添加到'首节点'处
if (hasFlag) {
delete(nextNode);
addToFirst(nextNode);
return nextNode.value;
}
//无数据
return -1;
}
/**
* 存数据
* 1:先判断是否有key所对应的数据
* <p>
* 2:有
* 2.1：更新value
* 2.2：把此节点添加到链表首部
* <p>
* 3:没有，判断如果保存此数据后,是否会达到容量限制
* 3.1：没超过，则把把key，value 构造成一个新节点，添加到链表首部
* 3.2：超过容量限制，从表尾巴开始删除，直到容量可以保存下新数据为止
*
* @param key key
* @param value value
*/
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
update(node, value);
} else {
if (isOverSize(sizeOf(key))) {
//delete
deleteFromTail();
}
addToFirst(key, value);
}
}
/**
* 把待添加节点添加到链表首部
*
* @param newNode 待添加节点
*/
private void addToFirst(Node newNode) {
mCurCapacity += sizeOf(newNode.key);
Node fistNode = mHead.next;
mHead.next = newNode;
newNode.pre = mHead;
fistNode.pre = newNode;
newNode.next = fistNode;
}
/**
* 把 key,value构造成一个节点，添加到链表首部
*
* @param key key
* @param value vaalue
*/
private void addToFirst(int key, int value) {
int sizeOf = sizeOf(key);
mCurCapacity += sizeOf;
Node newNode = new Node(key, value, sizeOf);
Node fistNode = mHead.next;
mHead.next = newNode;
newNode.pre = mHead;
fistNode.pre = newNode;
newNode.next = fistNode;
}
/**
* 更新链表中节点的 value
* <p>
* 1：更新前查看，更新后的内容是否会超过容量限制
* <p>
* 2：没超过
* 2.1：更新 value
* 2.2：把当前节点添加到链表首部
* <p>
* 3:超过
* 3.1：从链表尾部开始删除数据
* 3.2：从链表中删除此接单，并把节点天机到此链表首部
*
* @param node
* @param value
*/
private void update(Node node, int value) {
int sizeOf = sizeOf(node.key);
if (!isOverSize(sizeOf, node.valueSize)) {
//更新value
node.value = value;
node.valueSize = sizeOf;
} else {
//从tail开始删除数据直到能存下更新的数据为止
deleteFromTail();
}
//删除当前node
delete(node);
//移动的链表头部
addToFirst(node);
}
/**
* 从链表中删除给定的节点
*
* @param deleteNode 待删除链表
*/
private void delete(Node deleteNode) {
Node preNode = deleteNode.pre;
Node nextNode = deleteNode.next;
deleteNode.pre = null;
deleteNode.next = null;
preNode.next = nextNode;
nextNode.pre = preNode;
mCurCapacity -= deleteNode.valueSize;
}
/**
* 当当前容量超过最大容量是,从链表尾部删除节点
* 该方法在使用前需要借助 {@link com.sj.android_custom_view.test.LruIntegerCache#isOverSize(int)}判断下当前容量
*/
private void deleteFromTail() {
Node deleteNode = mTail.pre;
while (deleteNode != null && deleteNode != mHead) {
Node preNode = deleteNode.pre;
//删除node
preNode.next = deleteNode.next;
deleteNode.next.pre = preNode;
int deleteSizeOf = deleteNode.valueSize;
mCurCapacity -= deleteSizeOf;
if (mCurCapacity > mMaxCapacity) {
deleteNode = preNode;
continue;
}
return;
}
}
private Node getNode(int key) {
Node lastNode = mHead.next;
while (lastNode != null && lastNode != mTail) {
if (lastNode.key == key) {
return lastNode;
}
lastNode = lastNode.next;
}
return null;
}
/**
* 跟新新添加节点的 value所占的实际大小，判断容量是否超过最大限制
*
* @param sizeOf 待添加数据的大小
* @return
*/
private boolean isOverSize(int sizeOf) {
return mCurCapacity + sizeOf > mMaxCapacity;
}
private boolean isOverSize(int newSizeOf, int oldSizeOf) {
return mCurCapacity - oldSizeOf + newSizeOf > mMaxCapacity;
}
/**
* 当前key所对应value的实际大小
*
* @param key key
* @return value的实际大小
*/
protected int sizeOf(int key) {
return 1;
}
public String raversetFromHead() {
final String splteStr = "-->";
StringBuilder sb = new StringBuilder();
Node lastNode = mHead.next;
while (lastNode != null && lastNode != mTail) {
sb.append(lastNode.key);
sb.append(splteStr);
lastNode = lastNode.next;
}
sb.delete(sb.length() - splteStr.length(), sb.length());
return sb.toString();
}
public String raversetFromTail() {
final String splteStr = "-->";
StringBuilder sb = new StringBuilder("Count:" + mCurCapacity + ":");
Node preNode = mTail.pre;
while (preNode != null && preNode != mHead) {
sb.append(preNode.key);
sb.append(splteStr);
preNode = preNode.pre;
}
sb.delete(sb.length() - splteStr.length(), sb.length());
return sb.toString();
}
private static class Node {
private int key;
private int value;
private Node pre;
private Node next;
private String tag;
private int valueSize;
private Node(String tag) {
this.tag = tag;
}
private Node(int key, int value, int valueSize) {
this.key = key;
this.value = value;
this.valueSize = valueSize;
}
}
}
网友评论