iOS-OC实现LRU算法NSDictionary容器（非线程安全）

1 LRU算法

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

这篇文章对LRU缓存算法做了非常详细的介绍：缓存淘汰算法之LRU-OYK

可惜Foundation框架中并未提供一个比较简洁的LRU算法，NSCache没怎么看懂，java中有LruCache。

2 使用NSDictionary实现

2.1 实现代码

为了便于查找，缓存通常都是Dictionary的形式，这里也是通过继承NSMutableDictionary来实现一个包含LRU算法的容器。

头文件如下，支持泛型：

#import <Foundation/Foundation.h>

@interface LRUMutableDictionary<__covariant KeyType, __covariant ObjectType> : NSObject

// maxCountLRU: 执行LRU算法时的最大存储的元素数量
- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU;

//*****NSDictionary
@property (readonly) NSUInteger count;

- (NSEnumerator<KeyType> *)keyEnumerator;

- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(KeyType key, ObjectType obj, BOOL *stop))block;

//*****NSMutableDictionary
- (void)removeObjectForKey:(KeyType)aKey;
- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;

- (void)removeAllObjects;
- (void)removeObjectsForKeys:(NSArray<KeyType> *)keyArray;

//*****LRUMutableDictionary
// 执行LRU算法，当访问的元素可能是被淘汰的时候，可以通过在block中返回需要访问的对象，会根据LRU机制自动添加到dictionary中
- (ObjectType)objectForKey:(KeyType)aKey returnEliminateObjectUsingBlock:(ObjectType (^)(BOOL maybeEliminate))block;

@end

实现文件如下：

#import "LRUMutableDictionary.h"

@interface LRUMutableDictionary ()

@property (nonatomic, strong) NSMutableDictionary *dict;
@property (nonatomic, strong) NSMutableArray *arrayForLRU;
@property (nonatomic, assign) NSUInteger maxCountLRU;

@end

@implementation LRUMutableDictionary

- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU
{
    self = [super init];
    if (self) {
        _dict = [[NSMutableDictionary alloc] initWithCapacity:maxCountLRU];
        _arrayForLRU = [[NSMutableArray alloc] initWithCapacity:maxCountLRU];
        _maxCountLRU = maxCountLRU;
    }
    return self;
}
#pragma mark - NSDictionary

- (NSUInteger)count
{
    return [_dict count];
}

- (NSEnumerator *)keyEnumerator
{
    return [_dict keyEnumerator];
}

- (id)objectForKey:(id)aKey
{
    return [self objectForKey:aKey returnEliminateObjectUsingBlock:^id(BOOL maybeEliminate) {
        return nil;
    }];
}

- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block
{
    [_dict enumerateKeysAndObjectsUsingBlock:block];
}

#pragma mark - NSMutableDictionary

- (void)removeObjectForKey:(id)aKey
{
    [_dict removeObjectForKey:aKey];
    [self _removeObjectLRU:aKey];
}

- (void)setObject:(id)anObject forKey:(id<NSCopying>)aKey
{
    BOOL isExist = ([_dict objectForKey:aKey] != nil);
    [_dict setObject:anObject forKey:aKey];
    
    if (isExist) {
        [self _adjustPositionLRU:aKey];
    } else {
        [self _addObjectLRU:aKey];
    }
}

- (void)removeAllObjects
{
    [_dict removeAllObjects];
    [_arrayForLRU removeAllObjects];
}

- (void)removeObjectsForKeys:(NSArray *)keyArray
{
    [_dict removeObjectsForKeys:keyArray];
    [_arrayForLRU removeObjectsInArray:keyArray];
}

#pragma mark - LRUMutableDictionary

- (id)objectForKey:(id)aKey returnEliminateObjectUsingBlock:(id (^)(BOOL))block
{
    id object = [_dict objectForKey:aKey];
    if (object) {
        [self _adjustPositionLRU:aKey];
    }
    if (block) {
        BOOL maybeEliminate = object ? NO : YES;
        id newObject = block(maybeEliminate);
        if (newObject) {
            [self setObject:newObject forKey:aKey];
            return [_dict objectForKey:aKey];
        }
    }
    return object;
}

#pragma mark - LRU

- (void)_adjustPositionLRU:(id)anObject
{
    NSUInteger idx = [_arrayForLRU indexOfObject:anObject];
    if (idx != NSNotFound) {
        [_arrayForLRU removeObjectAtIndex:idx];
        [_arrayForLRU insertObject:anObject atIndex:0];
    }
}

- (void)_addObjectLRU:(id)anObject
{
    [_arrayForLRU insertObject:anObject atIndex:0];
    // 当超出LRU算法限制之后，将最不常使用的元素淘汰
    if ((_maxCountLRU > 0) && (_arrayForLRU.count > _maxCountLRU)) {
        [_dict removeObjectForKey:[_arrayForLRU lastObject]];
        [_arrayForLRU removeLastObject];
        
        // 【注意】这里不要直接调用下面这个方法，因为内部调用[_arrayForLRU removeObject:anObject];的时候，
        // 每次都将Array从头开始遍历到最后一个，这里既然已经知道是删除最后一个了，直接删除即可。
        // 使用下面这种方法会增加上百倍的耗时。
        // [self removeObjectForKey:[_arrayForLRU lastObject]];
    }
}

- (void)_removeObjectLRU:(id)anObject
{
    [_arrayForLRU removeObject:anObject];
}

@end

2.2 实现原理概述

实现原理其实很简单，重写NSMutableDictionary的几个重要方法，内部持有NSMutableDictionary用于存储缓存数据。持有NSMutableArray用于存储Key值，Key的顺序为LRU算法中的优先级，最前面的元素表示最近使用，最后面的元素表示最近最少使用。
每次对NSMutableDictionary中的元素做数据操作，都认为这个元素是最近使用的元素，然后调整该元素的Key在NSMutableArray中的顺序为第一位。
设定一个容器可存储的数量最大值，当插入元素到超出这个最大值之后，在NSMutableArray中找到最后一个元素Key删除，并在NSMutableDictionary中找到对应的元素删除。

2.3 弊端

以上的实现在对性能要求不是特别高的时候，已经可以满足需求了。
我们知道，NSMutableArray的内部是使用动态数组实现的，动态数组的缺点在这里被完全暴露出来，我们的实现里面基本上都在用到“插入”和“删除”的操作，这两个操作对动态数组的性能消耗是比较大的，比较好的实现方式应该是使用“双向链表”，奈何Foundation框架中没有我们想要的“双向链表”容器。当然我们可以使用C++的STL库中的list来实现，有兴趣的读者可以尝试。
容器中有设定一个容器的最大存储容量值，我相信，在使用这个LRU容器时，绝大部分的情况下都是达不到这个最大容量的，淘汰算法应该是属于一种保护措施不是吗？那么问题来了，如果大部分情况下都达不到最大容量，或者可能永远都达不到最大容量，那我们每次对元素操作时做了LRU算法调整，不是白费功夫吗（这个调整还是要消耗一些性能的），毕竟这个调整最终是为了当超出容量时用来将最后面的元素淘汰而做的准备，想想是不是可以以此做一些优化？

3 性能优化

针对第三点弊端做一些优化，当容量达不到最大容量值得时候，可以完全停止掉LRU算法，这时候这个LRU容器就跟普通的NSMutableDictionary容器没什么两样了，当容量接近最大容量值得时候，开始启动LRU算法。

头文件不变，来看实现文件：

#import "LRUMutableDictionary.h"

// 定义一个开始准备启动LRU的值，当 (MaxCount - CurCount < LRU_RISK_COUNT) 时才启动 LRU
#define LRU_RISK_COUNT 100

@interface LRUMutableDictionary ()

@property (nonatomic, strong) NSMutableDictionary *dict;    // 存储数据的字典
@property (nonatomic, strong) NSMutableArray *arrayForLRU;  // 存放LRU的数组

@property (nonatomic, assign) NSUInteger maxCountLRU;       // 最大存储值，存储量超出这个值，启动LRU淘汰算法
@property (nonatomic, assign) BOOL isOpenLRU;               // 是否开启LRU算法，如果存储量远低于最大存储值时，其实没有必要开启LRU算法

@end

@implementation LRUMutableDictionary

- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU
{
    self = [super init];
    if (self) {
        _dict = [[NSMutableDictionary alloc] initWithCapacity:maxCountLRU];
        _arrayForLRU = [[NSMutableArray alloc] initWithCapacity:maxCountLRU];
        _maxCountLRU = maxCountLRU;
    }
    return self;
}
#pragma mark - NSDictionary

- (NSUInteger)count
{
    return [_dict count];
}

- (NSEnumerator *)keyEnumerator
{
    return [_dict keyEnumerator];
}

- (id)objectForKey:(id)aKey
{
    return [self objectForKey:aKey returnEliminateObjectUsingBlock:^id(BOOL maybeEliminate) {
        return nil;
    }];
}

- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block
{
    [_dict enumerateKeysAndObjectsUsingBlock:block];
}

#pragma mark - NSMutableDictionary

- (void)removeObjectForKey:(id)aKey
{
    [_dict removeObjectForKey:aKey];
    [self _removeObjectLRU:aKey];
}

- (void)setObject:(id)anObject forKey:(id<NSCopying>)aKey
{
    BOOL isExist = ([_dict objectForKey:aKey] != nil);
    [_dict setObject:anObject forKey:aKey];
    
    if (isExist) {
        [self _adjustPositionLRU:aKey];
    } else {
        [self _addObjectLRU:aKey];
    }
}

- (void)removeAllObjects
{
    [_dict removeAllObjects];
    [self _removeAllObjectsLRU];
}

- (void)removeObjectsForKeys:(NSArray *)keyArray
{
    if (keyArray.count > 0) {
        [_dict removeObjectsForKeys:keyArray];
        [self _removeObjectsLRU:keyArray];
    }
}

#pragma mark - LRUMutableDictionary

- (id)objectForKey:(id)aKey returnEliminateObjectUsingBlock:(id (^)(BOOL))block
{
    id object = [_dict objectForKey:aKey];
    if (object) {
        [self _adjustPositionLRU:aKey];
    }
    if (block) {
        BOOL maybeEliminate = object ? NO : YES;
        id newObject = block(maybeEliminate);
        if (newObject) {
            [self setObject:newObject forKey:aKey];
            return [_dict objectForKey:aKey];
        }
    }
    return object;
}

#pragma mark - LRU

- (void)_adjustPositionLRU:(id)anObject
{
    if (_isOpenLRU) {
        NSUInteger idx = [_arrayForLRU indexOfObject:anObject];
        if (idx != NSNotFound) {
            [_arrayForLRU removeObjectAtIndex:idx];
            [_arrayForLRU insertObject:anObject atIndex:0];
        }
    }
}

- (void)_addObjectLRU:(id)anObject
{
    if (!_isOpenLRU && [self isNeedOpenLRU:_dict.count]) {
        // 如果原来没有开启 LRU，现在增加一个元素之后达到了存储量临界条件，则开启，一次性将所有的Key导入
        [_arrayForLRU removeAllObjects];
        [_arrayForLRU addObjectsFromArray:_dict.allKeys];
        [_arrayForLRU removeObject:anObject];
        _isOpenLRU = YES;
    }
    
    if (_isOpenLRU) {
        [_arrayForLRU insertObject:anObject atIndex:0];
        // 当超出LRU算法限制之后，将最不常使用的元素淘汰
        if ((_maxCountLRU > 0) && (_arrayForLRU.count > _maxCountLRU)) {
            [_dict removeObjectForKey:[_arrayForLRU lastObject]];
            [_arrayForLRU removeLastObject];
            
            // 【注意】这里不要直接调用下面这个方法，因为内部调用[_arrayForLRU removeObject:anObject];的时候，
            // 每次都将Array从头开始遍历到最后一个，这里既然已经知道是删除最后一个了，直接删除即可。
            // 使用下面这种方法会增加上百倍的耗时。
            // [self removeObjectForKey:[_arrayForLRU lastObject]];
        }
    }
}

- (void)_removeObjectLRU:(id)anObject
{
    if (_isOpenLRU) {
        [_arrayForLRU removeObject:anObject];
        
        if (![self isNeedOpenLRU:_arrayForLRU.count]) {
            [_arrayForLRU removeAllObjects];
            _isOpenLRU = NO;
        }
    }
}

- (void)_removeObjectsLRU:(NSArray *)otherArray
{
    if (_isOpenLRU) {
        [_arrayForLRU removeObjectsInArray:otherArray];
        
        if (![self isNeedOpenLRU:_arrayForLRU.count]) {
            [_arrayForLRU removeAllObjects];
            _isOpenLRU = NO;
        }
    }
}

- (void)_removeAllObjectsLRU
{
    if (_isOpenLRU) {
        [_arrayForLRU removeAllObjects];
        _isOpenLRU = NO;    // 清空全部元素了，一定可以关闭LRU
    }
}

- (BOOL)isNeedOpenLRU:(NSUInteger)count
{
    return (_maxCountLRU - count) < LRU_RISK_COUNT;
}

@end

上面定义 100 接近值可以根据实际情况做一些修改，以上实现方法已经在项目中实际使用，可以很好的满足需求。

读者如果对于实现LRU算法有更好的方法，欢迎讨论。

本文首发于我的博客vinnyxiong.cn，欢迎访问。

最后编辑于：2017.12.04 03:13:31

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342