YYMemoryCache 源码分析

提示

YYMemoryCache 是内存缓存，所以存取速度非常快，主要用到两种数据结构的 LRU 淘汰算法

LRU 淘汰算法

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

最常见的实现是使用一个链表保存缓存数据

【命中率】

当存在热点数据时，LRU 的效率很好，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。

Cache 的容量是有限的，当 Cache 的空间都被占满后，如果再次发生缓存失效，就必须选择一个缓存块来替换掉。LRU 法是依据各块使用的情况， 总是选择那个最长时间未被使用的块替换。这种方法比较好地反映了程序局部性规律

数据结构

双向链表 (Doubly Linked List) 哈希表 (Dictionary)

缓存操作

新数据插入到链表头部； 每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 当链表满的时候，将链表尾部的数据丢弃。

分析图

bpM38.png

YYMemoryCache.m 里的两个分类

链表节点 _YYLinkedMapNode

链表 _YYLinkedMap

链表插入、查找、替换操作实现

添加节点到链表头节点

移动当前节点到链表头节点

移除节点

移除指定节点

移除尾节点

移除所有缓存

图片引用自YYCache 源码分析(二) 感谢作者

ps 未完待续……