通过YYMemoryCache简单分析LRU实现内存缓存

什么是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就总结了一下,方便以后自己去实现一些功能~