[源码阅读] YYCache

YYCache 源码地址

内存淘汰机制 LRU

LRU 最近最少使用 淘汰算法

• YYCache 使用 双向链表实现, 使用某个缓存时, 将缓存移到链表的头部,被移除的部分,前后两端再连接上. 再触发内存淘汰的维度限制时, 从双向链表的尾部开始移除节点, 知道满足条件.
• HashMap 是来配合双向链表，用于减少时间复杂度的。它是可以快速的（O(1)的时间）定位，链表中某个值是否存在.
• YYCache 中使用了 CFMutableDictionary 而不是 NSDictionary 来存储节点, 主要是为了存储 key value时的高效
• 之所以选择 双向链表而不是单向链表是为了 删除节点的时候更高效, 删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，
  • 第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。
  • 第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。
  • 尽管通常会采用方法一。但其实这两种方法的效率是一样的，指针的总的移动操作都会有2*i次. 而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为i次。

线程安全

YYCache 中的 内存缓存和磁盘缓存都是内存安全的
YYMemoryCache 使用了 pthread_mutex_t 互斥锁 来读取和设置节点.
移除节点的时候使用了串行队列,保证线程安全

 _queue = dispatch_queue_create("com.ibireme.cache.memory", DISPATCH_QUEUE_SERIAL);

YYDiskCache 使用了 dispatch_semaphore_t 全局信号量
之所以使用的原因是

dispatch_semaphore 是信号量，但当信号总量设为 1 时也可以当作锁来。在没有等待情况出现时，它的性能比 pthread_mutex 还要高，但一旦有等待情况出现时，性能就会下降许多。相对于 OSSpinLock 来说，它的优势在于等待时不会消耗 CPU 资源。对磁盘缓存来说，它比较合适。

IO 操作的特点

• 如果没有等待, 其性能要高很多
• 等待时, 性能会下降许多, 但是 其等待 不会消耗 CPU 资源. 对于磁盘缓存来说, 它比较合适

锁

从上面可以看出对于锁的使用,要考虑其使用场景来确定.
如果一个操作的任务耗时特别低, 一般使用 pthread_mutex_t ,反之则建议使用 dispatch_semaphore . 当然简单使用的会, 例如属性访问这种, 可以直接使用 @synchronized (内部使用递归mutex来做同步), 不过要注意使用时最好用内部的对象来保证锁的安全性,且内部对象最好不要改变(即变更地址).

参考

yycache源码阅读-lision

LRU(Least Recent Used) java 实现为这么采用HashMap+双向链表