准备
LRU缓存机制是什么？
一般的数据在存储时都会考虑采用栈(先进后出) 还是 队列(先进先出)的模式，举例以队列（先进先出）的模式管理缓存中的数据,那么如下图:
先进先出模式
设置缓存空间只能存储数量为2时，当A\B存储后再需要空间存储C时，那么就只能先移除A数据。换句话说，每次删除的都是优先级低的数据，而现在队列的处理方式相当于 (缓存加入的时间) == (优先级)，越先加入的数据优先级会越低，也就会越先被删除。
那么如果 A 在插入 C数据时，被访问了多次，而且在插入C数据之后也访问了多次，按照队列（先进先出）的模式会不会导致 A 不断的移除又不断的加入呢？
确实会这样，那么 删除的优先级 就不单单等同于缓存第一次加入的时间，而是等同于每次刷新的时间，每次调用Get时都不断的刷新缓存数据的时间，也就是LRU（least-recently-used）缓存机制。
LRU缓存机制
基于以上的几个问题就能LRU缓存机制的实现原理:
① A虽然是最先缓存的数据，优先级最低，但是每次访问都能必须将A放置到最高优先级的位置.
② 涉及到数据的多次位置变更，所以链式存储优于线性存储。但是链表在搜索操作时的时间复杂度为0(n)，所以必须有辅助工具: hash表 + 双向链表。
用图就能很简单的描述出整体的思路:
LRU缓存机制实现思路
以LeetCode上的N.146 LRU缓存机制来验证以上的思路(Python版):
① 结点 Node
class Node: # 构建结点
def __init__(self):
self.key = 0
self.val = 0
self.prev = None # 前面结点
self.next = None # 后面结点
② 链表管理
class LRUCache:
def __add(self, node): #添加node
node.next = self.__header.next
node.prev = self.__header
self.__header.next.prev = node
self.__header.next = node
def __remove(self, node): # 移除node
node.prev.next = node.next
node.next.prev = node.prev
def __move_to_end(self, node): #移动到前面，也就是将优先级设置最高
self.__remove(node)
self.__add(node)
def __remove_tail(self):
res = self.__tail.prev
self.__remove(res)
return res
def __init__(self,capacity):
self.capacity = capacity #缓存容量
self.dic = {} # hash
self.size = 0
self.__header, self.__tail = Node(), Node()
self.__header.next = self.__tail
self.__tail.prev = self.__header
def get(self, key): # get Node
node = self.dic.get(key, None)
if node is not None:
self.__move_to_end(node)
return node.val
return -1
def put(self,key, val): # push new Node
node = self.dic.get(key, None)
if node is None:
node = Node()
node.key = key
node.val = val
self.__add(node)
self.dic[key] = node
self.size += 1
else:
node.val = val
self.__move_to_end(node)
if self.size > self.capacity:
tail = self.__remove_tail()
self.dic.pop(tail.key)
查找、插入、删除的时间复杂度都为O(1).
Memory Cache和On-disk Cache有什么差别？
Memory Cache就是RAM（运行内存），CPU能直接访问，但是不能掉电存储。
on-Disk Cache 是ROM,不能被CPU直接访问，能掉电存储，以文件File 或 数据库SQlite等形式进行存储。
YYCache
架构
Memory Cache
是一种快速存储键值对的内存缓存。相对于NSDictionary，键会被retained而不会capied。API的性能和NSCache类似，所有的方法都是线程安全
与NSCache不同的地方:
① 使用了LRU缓存机制移除对象
② 能被cost花销、count数量和age缓存时间控制
③ 能配置当接收到内存警告或App进入后台时自动释放对象
从以上对LRU缓存机制的讲解入手:
① 结点 _YYLinkedMapNode
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
__unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
id _key;
id _value;
NSUInteger _cost;
NSTimeInterval _time;
}
@end
② 链表管理 _YYLinkedMap
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; // 哈希表直接在map的内部，并没有并行放在外部
NSUInteger _totalCost;
NSUInteger _totalCount;
_YYLinkedMapNode *_head; // 头部指针
_YYLinkedMapNode *_tail; // 尾部指针
BOOL _releaseOnMainThread;
BOOL _releaseAsynchronously;
}
通过CoreFoundation 提高了_dic中的操作性能，在该链表类中也同样包括对插入、删除结点相关的方法：
③ 实际操作 YYMemoryCache
- 通知的处理
shouldRemoveAllObjectsOnMemoryWarning // 默认为YES，在接收到内存警告时移除所有的对象
shouldRemoveAllObjectsWhenEnteringBackground // 默认为YES，在App进入后台时移除所有的对象
- 线程的处理
releaseOnMainThread //默认为NO， 如果为YES就会在主线程中释放，只有当包含了如UIView/CALayer只能在主线程中操作的对象才设置YES
releaseAsynchronously //默认为YES，会异步的释放键值对避免阻塞当前方法
在release释放某个node时，会进入其他线程中让block持有holder，然后由该queue异步释放该holder中的node
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
网友评论