YYMemoryCache是YYCache组件中负责内存缓存的。

涉及知识点：

• 双向链表
• 哈希表
• LRU（算法实现是使用上面两种数据结构）
• 线程同步锁

LRU

LRU（Least recently used，最近最少使用）

核心思想：如果数据最近被访问过，那么将来被访问的几率也更高”。

通过上面的思想，整理思路如下

1. 需要一个有序集合作为队列进行优先级(访问概率)控制；集合使用双向链表
2. 找到队列中已存在数据，并提高优先级；使用哈希表快速定位

为什么使用链表而不使用顺序表？为什么使用双向链表？

• 链表的增加和删除的操作时间复杂度是O(1)，而顺序表涉及到扩容的问题（开新内存，内存拷贝）

• 如果我们想删除最后一个元素，链表的操作是拿到最后一个元素的前一个元素，并将它的next设置成null，那怎么拿到最后一个元素的上一个元素呢？如果队列中已经有了元素，需要把它提到队头，那怎么拿到该元素的上一个元素呢？

我们可以维护一个链表的头节点和尾节点，但是没办法找到尾节点的上一个节点，所以需要双向链表

YYMemoryCache源码实现

链表节点封装

@interface _YYLinkedMapNode : NSObject {
    // 在当前module中生效
    @package
    // 上一个节点
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    // 下一个节点
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    // 节点key
    id _key;
    // 节点值
    id _value;
    // 花费的内存
    NSUInteger _cost;
    // 缓存的时间
    NSTimeInterval _time;
}
@end
@implementation _YYLinkedMapNode
@end

链表的封装 - 包含增删改查等操作