LRU cache-高频

LRUcache.png
1. 要求：
i. lookup O(1)时间复杂度
ii. insert O(1)时间复杂度
2. 数据结构选择：
i. hashtable: 以实现O(1) loopup
ii. 循环双向链表: 以实现O(1) insert
3. 实现策略：
用hashtable key-> listNode 快速查询
用listNode 存放{key, value } pair
4. 基本操作
4.1 链表操作
i. 加入链表头：addNode ;
ii. 原地将node 从链表中移除;
iii. 从链表尾巴 将链表尾节点移除;
4.2 hash 操作
i. put 操作

查询节点是否存在
if 存在{
  removeNode(node);
  addNode(node);
  node->value = value;
} else (不存在) {
    node = newNode(key, value);
    addNode;
    hash[key] = node;
    hashSize++;
    if (hashSize > capacity) {
      hashSize--;
      evictNode= head->pre;
      removeNode(evictNode);
      hash[evictNode->key] = NULL;
    } 
}

ii. get 操作

查询节点是否存在
if 存在{
  removeNode(node);
  addNode(node);
  return node->value;
} else (不存在) {
    return -1;
}

struct listNode {
    int key;
    int value;

    struct listNode *pre;
    struct listNode *next;

};

typedef struct {
    struct listNode *head;
    struct listNode **hash;
    int size;
    int capacity;
} LRUCache;

struct listNode *newNode(int key,int value)
{
    struct listNode *node = (struct listNode *)malloc(sizeof(struct listNode));
    node->key = key;
    node->value = value;
    node->pre=NULL;
    node->next=NULL;
    return node;
}

void initList(LRUCache* obj)
{
    struct listNode *node = newNode(0,0);
    node->pre = node;
    node->next = node;
    obj->head = node;
}

void removeNode(struct listNode *node)
{
    struct listNode *pre, *next;
    pre = node->pre;
    next = node->next;
    pre->next = next;
    next->pre = pre;
}

void addNode(struct listNode *node, struct listNode *head)
{
    struct listNode *next=head->next;
    node->next = next;
    node->pre = head;
    next->pre = node;
    head->next = node;
}

#define MAX_HASH_SIZE (10001)
LRUCache* lRUCacheCreate(int capacity) {
    LRUCache *lrucache = (LRUCache *)malloc(sizeof(LRUCache));
    initList(lrucache);

    lrucache->hash = (struct listNode **)malloc(sizeof(struct listNode *) * MAX_HASH_SIZE);
    lrucache->size = 0;
    lrucache->capacity = capacity;
    return lrucache;
}

int lRUCacheGet(LRUCache* obj, int key) {
    struct listNode *node = obj->hash[key];

    if (node == NULL) {
        return -1;
    } else {
        removeNode(node);
        addNode(node, obj->head);
        return node->value;
    }
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    struct listNode *node = obj->hash[key];

    if (node == NULL) {
        node = newNode(key,value);
        obj->hash[key] = node;
        addNode(node, obj->head);
        obj->size++;
        if (obj->size > obj->capacity) {
            struct listNode *evict = obj->head->pre;
            int evictKey = evict->key;
            removeNode(evict);
            free(evict);
            obj->hash[evictKey]=NULL;
            obj->size--;
        }

    } else {
        removeNode(node);
        addNode(node, obj->head);
        node->value = value;

    }
}

void lRUCacheFree(LRUCache* obj) {

    struct listNode *head = obj->head;
    while(head->next!= head) {
        struct listNode *next = head->next;
        removeNode(next);
        free(next);
    }
    free(head);
    free(obj->hash);
    obj->size = 0;
    obj->capacity = 0;
}