设计题——LPU缓存机制

关键点：怎么确认最近最少使用。

关键词：hash

关键思路：访问之前先删除再添加，保证hash表元素是按照访问时间从旧到新的，这样在删除“最久未使用”元素时，只需要迭代hash表，然后删除第一个元素即可。

代码：

typedef struct {     int key;     int val;     UT_hash_handle hh; } LRUCache;
int g_Size; LRUCache *hashtable  = NULL;
LRUCache* lRUCacheCreate(int capacity) {     g_Size = capacity;     return hashtable ; }
int lRUCacheGet(LRUCache* obj, int key) {     LRUCache *cur_usr = NULL;     HASH_FIND_INT(hashtable, &key, cur_usr);     if (cur_usr != NULL) { // 找到了，get存在的key，则该key被使用了一次，因此需要先删后入，满足LRU         HASH_DEL(hashtable, cur_usr);         HASH_ADD_INT(hashtable, key, cur_usr);         return cur_usr->val;     } else { // 没有找到         return -1;     } }
void lRUCachePut(LRUCache* obj, int key, int value) {     LRUCache *cur_usr = NULL, *next_usr = NULL;     HASH_FIND_INT(hashtable, &key, cur_usr);     if (cur_usr != NULL) { // 找到了，get存在的key，则该key被使用了一次，因此需要先删后入，满足LRU         HASH_DEL(hashtable, cur_usr);         cur_usr->key = key;         cur_usr->val = value;         HASH_ADD_INT(hashtable, key, cur_usr);     } else { // 没有找到，新插入         int cnt = HASH_COUNT(hashtable);         if (cnt == g_Size) { // 达到容量上限，删除最久未使用的数据             // HASH_ITER是一个宏定义，程序执行时被替换为一个循环             HASH_ITER(hh, hashtable, cur_usr, next_usr) {                 HASH_DEL(hashtable, cur_usr);                 free(cur_usr);                 break;             }         }         LRUCache *new_usr = (LRUCache *)malloc(sizeof(LRUCache));         new_usr->key = key;         new_usr->val = value;         HASH_ADD_INT(hashtable, key, new_usr);     }     return; }
void lRUCacheFree(LRUCache* obj) {     LRUCache *cur_usr = NULL, *next_usr = NULL;     HASH_ITER(hh, hashtable, cur_usr, next_usr) {         HASH_DEL(hashtable, cur_usr);         free(cur_usr);     } }