什么是LRU?
借用百度百科 : LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最少使用的页面予以淘汰。
发挥下头脑风暴,如果要设计一个iOS内存缓存,我们大致应该从几个方面思考呢?我觉得是:
- 能够稳定存储
- 读写操作
- 参考NSCache,文件大小限制,文件数量限制
- 参考NSCache,需要在复杂的多线程环境下保证线程安全
- 提供自动清除策略
- 提供手动清除策略
当然,以上可能是我凭借阅读资料和个人经验得出的推算.我们还是通过YYMemoryCache来研究一下LRU先.
LRU理解
LRU本身的实现目标应该是能够存储数据,存储数据的方式有很多,我们基本上所有的数据结构都能够做到,但是对于快速查找到数据的方式应该是HashMap和数组,考虑到我们存储的数据可能需要定向查找,即通过key进行查找~所以选择HashMap这个数据结构是更优解.而且LRU本身的说法我们拆解一下:
- 如果一条数据刚刚被访问,在需要释放内存的情况下,它不应该被清除
- 如果我们的数据不存在被重复访问,在需要释放内存的情况下,最先插入的第一条应该被清除
- 我们需要快速增删数据
那么什么样的数据结构应该满足我们上边的基本条件呢?最合理的数据结构应该是HashMap + 双向链表,HashMap提供了时间复杂度为O(1)的增删改查,而双向链表可以保证我们能够操作数据顺序的安全性和稳定性.为什么不使用单链表呢?是因为单链表自身无法随意更新节点位置信息.用一副图来解释一下:
LRU.png
PS:画的不好看,用PPT和keynote画了半个小时,后来找的EDarwMax画的~
YYMemoryCache是如何实现的?
上链接YYCache
首先作者定义了LRU的数据结构
@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
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; // do not set object directly
NSUInteger _totalCost;
NSUInteger _totalCount;
_YYLinkedMapNode *_head; // MRU, do not change it directly
_YYLinkedMapNode *_tail; // LRU, do not change it directly
BOOL _releaseOnMainThread;
BOOL _releaseAsynchronously;
}
我们可以看到,确实是以HashMap为主体,双向链表连接的数据结构结构
我们看一下具体实现
//初始化
- (instancetype)init {
self = [super init];
_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
//是否可以再主线程释放内存
_releaseOnMainThread = NO;
//异步子线程释放内存
_releaseAsynchronously = YES;
return self;
}
//CFDic 需要我们手动去管理内存
- (void)dealloc {
CFRelease(_dic);
}
//把新的节点插入链表头
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));
_totalCost += node->_cost;
_totalCount++;
if (_head) {
node->_next = _head;
_head->_prev = node;
_head = node;
} else {
_head = _tail = node;
}
}
//把旧的节点插入链表头
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
if (_head == node) return;
if (_tail == node) {
_tail = node->_prev;
_tail->_next = nil;
} else {
node->_next->_prev = node->_prev;
node->_prev->_next = node->_next;
}
node->_next = _head;
node->_prev = nil;
_head->_prev = node;
_head = node;
}
//删除某个指定的节点
- (void)removeNode:(_YYLinkedMapNode *)node {
CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
_totalCost -= node->_cost;
_totalCount--;
if (node->_next) node->_next->_prev = node->_prev;
if (node->_prev) node->_prev->_next = node->_next;
if (_head == node) _head = node->_next;
if (_tail == node) _tail = node->_prev;
}
//移除尾部节点
- (_YYLinkedMapNode *)removeTailNode {
if (!_tail) return nil;
_YYLinkedMapNode *tail = _tail;
CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
_totalCost -= _tail->_cost;
_totalCount--;
if (_head == _tail) {
_head = _tail = nil;
} else {
_tail = _tail->_prev;
_tail->_next = nil;
}
return tail;
}
//清空链表
- (void)removeAll {
_totalCost = 0;
_totalCount = 0;
_head = nil;
_tail = nil;
if (CFDictionaryGetCount(_dic) > 0) {
CFMutableDictionaryRef holder = _dic;
_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
if (_releaseAsynchronously) {
dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
CFRelease(holder); // hold and release in specified queue
});
} else if (_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
CFRelease(holder); // hold and release in specified queue
});
} else {
CFRelease(holder);
}
}
}
以上就是LRU在YYMemoryCache中的实现,我只是做了简单的搬运工作,然后图是我自己画的,可以帮助不太熟悉的小伙伴理解一下,如果有出入的地方,请尽管指出~
如果对缓存的具体操作感兴趣,可以去github上查看实现的源码,插一句,NSCache自身就很强大,我只是看到YYMemoryCache是自己实现的LRU就总结了一下,方便以后自己去实现一些功能~
网友评论