LRU算法

LRU即最近最少使用算法Least Recently Used：最近最少使用缓存；核心思想是“数据最近被访问过，那么将来被访问的几率会更高”；
这样能够保证：利用最少的空间实现最高效的缓存；
实现方式是：
1.利用map实现迅速读取；时间复杂度为1;
2.利用双向链表头节点的操作保证数据按照数据按照访问顺序排列；
3.容量通过每次set时，检查缓存数量来保证。
4.双向链表可以让我们顺利的删除一个节点。

Node实现

@interface Node : NSObject

- (instancetype)initWithKey:(NSString*)key value:(id)value;
//上一个结点
@property (nonatomic,strong) Node *pre;
//下一个结点
@property (nonatomic,strong) Node *next;
//键
@property (nonatomic,copy) NSString *key;
//值
@property (nonatomic,copy) id value;

@end

#import "Node.h"

@interface Node ()

@end

@implementation Node

- (instancetype)initWithKey:(NSString *)key value:(id)value {
    if (self = [super init]) {
        self.key = key;
        self.value = value;
    }
    return self;
}
@end

cache实现

@interface Cache : NSObject

- (instancetype)initWithCapacity:(NSInteger)capacity;

- (id)getItemForKey:(NSString*)key;

- (void)setItem:(id)item forKey:(NSString*)key;

@end

#import "Cache.h"
#import "Node.h"

@interface Cache ()

@property (nonatomic,assign) NSInteger capacity;
@property (nonatomic,strong) Node *head;
@property (nonatomic,strong) Node *trail;
@property (nonatomic,strong) NSMutableDictionary *nodeMap;

@end

@implementation Cache

- (instancetype)initWithCapacity:(NSInteger)capacity {
    if (self = [super init]) {
        self.capacity = capacity;
    }
    return self;
}


/*
 1.将元素删除；
 2.元素放到链表头部
 */
- (id)getItemForKey:(NSString *)key {
    //存在
    if ([self.nodeMap.allKeys containsObject:key]) {
        //找到结点
        Node *node = [self.nodeMap objectForKey:key];
        //移除结点
        [self removeNode:node];
        //设为头结点
        [self setHeadNode:node];
        return node.value;
    } else {//不存在
        return nil;
    }
}

- (void)setItem:(id)item forKey:(NSString *)key {
    //存在，直接操作旧值
    if ([self.nodeMap.allKeys containsObject:key]) {
        Node *oldNode = [self.nodeMap objectForKey:key];
        [self removeNode:oldNode];
        [self setHeadNode:oldNode];
    } else {//不存在，操作新值
        Node *newHeadNode = [[Node alloc] initWithKey:key value:item];
        if (self.nodeMap.allKeys.count >= self.capacity) {
            [self.nodeMap removeObjectForKey:self.trail.key];
            [self removeNode:self.trail];
            [self setHeadNode:newHeadNode];
        } else {
         [self setHeadNode:newHeadNode];
        }
        [self.nodeMap setObject:newHeadNode forKey:key];
    }
}

/*
移除结点，操作前后结点；
 */
- (void)removeNode:(Node*)node {
    Node *currentPreNode = node.pre;
    Node *currentNextNode = node.next;
    //操作此节点的上一个结点
    if(currentPreNode == nil) {
        self.head = currentNextNode;
    } else {
        currentPreNode.next = node.next;
    }
    //操作此节点的下一个结点
    if(currentNextNode == nil) {
        self.trail = currentPreNode;
    } else {
        currentNextNode.pre = currentPreNode;
    }
}

/*
 设置头结点
 */
- (void)setHeadNode:(Node *)node {
    Node *oldHeadNode = self.head;
    //完成头结点赋值
    Node *newHeadNode = node;
    
    //更新新结点
    newHeadNode.pre = nil;
    newHeadNode.next = oldHeadNode;
    
    //更新旧头结点
    oldHeadNode.pre = newHeadNode;
    
    self.head = newHeadNode;
    if (self.head.next == nil) {
        self.trail = newHeadNode;
    }
}

- (NSMutableDictionary *)nodeMap {
    if (_nodeMap == nil) {
        _nodeMap = [NSMutableDictionary dictionary];
    }
    return _nodeMap;
}
@end