146. LRU 缓存机制

1. 题目

146. LRU 缓存机制

难度中等1377收藏分享切换为英文接收动态反馈

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• 最多调用 3 * 104 次 get 和 put

通过次数168,504

提交次数321,643

2. 分析及设计

1. put操作：
   1）键不存在，则插入。
   2）键存在，则值不同的情况下用新值更新旧值。
   3）插入新结点（键值对）时，若超出LRU的容量，则将最久未使用的结点删除。

2. get操作：
   1）键不存在，返回-1。
   2）键存在，则返回其值。

分析：
题目要求1、2这两种操作的时间复杂度需要尽可能地小（O(1)）。那结点的增删查改就使用双向循环链表来实现,因为删除一个结点，只有在双向循环链表中，才能在0(1)的时间复杂度内完成。
而，要根据一个键值key快速找到一个节点在双向循环链表中的位置，那么就需要做key和节点的某种关系的映射,所以我们这里使用十字链表法表示的哈希表来组织key和节点位置的映射。

1. 图示

2. 代码如下

上图就是我的设计，下面是代码实现，代码都有注释，我也不讲解了，主要是根据操作要求变换指针，我的本地ubuntu环境，运行需要自定义bool类型和对应的true和false宏，力扣平台提交通过。

struct LruNode {
	int key;
	int val;
	struct LruNode *next;
	struct LruNode *pre;
};

typedef struct LruNode node;

struct HashNode
{
	node *pnode;
	struct HashNode *next;
};

typedef struct HashNode hashnode;

typedef struct {
	int capacity;
	int cur_lru_num;
	node *LruList;//双向循环链表
	hashnode **nodetable;//hash表
} LRUCache;

//键值key的hash值计算函数
int hash_func(int capacity,int key)
{
	return key%capacity;
}

//hash表初始化
hashnode **hashtable_init(int capacity)
{
	hashnode **pnodetable = (hashnode **)malloc(sizeof(hashnode *)*capacity);
	memset(pnodetable,0,sizeof(hashnode *)*capacity);
	return pnodetable;
}

//hash桶下的节点hashnode的生成，使用lru双向链表的节点来初始化
hashnode *hash_node_init(node *pnode)
{
	hashnode *phashnode = (hashnode *)malloc(sizeof(hashnode));
	memset(phashnode,0,sizeof(hashnode));	
	phashnode->pnode = pnode;
	return phashnode;
}

//由于可能会修改上层结点，所以使用二级指针
void delete_hash_node_intable(hashnode **pphashhead,const node *plrunode)
{
	if (!pphashhead || !(*pphashhead) || !plrunode)
	{
		return;
	}
	
	hashnode *prenode = NULL;
	hashnode *pcurnode = (*pphashhead);
	hashnode *nextnode = (*pphashhead)->next;
	
    //遍历找到待删除节点
	while (pcurnode && pcurnode->pnode != plrunode)
	{
		prenode = pcurnode;
		pcurnode = pcurnode->next;
	}

	if (prenode == NULL)//待删除节点为第一个结点
	{
		free(pcurnode);
		(*pphashhead) = nextnode;//删除第一个结点后，要将hash表头指针指向下一个结点（其可能为NULL）
	}
	else if (pcurnode == NULL)//待删除节点不存在
	{
		return;
	}
	else
	{
		prenode->next = pcurnode->next;
		pcurnode->next = NULL;
		free(pcurnode);
	}
	
	return;
}

//插入hash桶下的链表中，插入顺序没有要求，所以使用最适宜的头插法
void insert_hash_node_intable(LRUCache *pObj,hashnode *pwaitadd)
{
	if (!pObj || !pwaitadd)
	{
		return;
	}
	
	int index = hash_func(pObj->capacity, pwaitadd->pnode->key);
	pwaitadd->next = pObj->nodetable[index];
	pObj->nodetable[index] = pwaitadd;
}

//删除hash桶下的链表，输入参数为该链表的链表头，删除后要就将其置空，所以使用二级指针
void free_hash_list(hashnode **pphashhead)
{
	if (!pphashhead || !(*pphashhead))
	{
		return;
	}

	hashnode *phead = (*pphashhead);
	
	while (phead)
	{
		hashnode *ptmp = phead->next;
		free(phead);
		phead = ptmp;
	}

	(*pphashhead) = NULL;//置空
}

//由给定的键值对，生成一个lru双向循环链表中的节点
node *lru_node_init(int key,int val)
{
	node *pnode = (node *)malloc(sizeof(node));
	
	memset(pnode,0,sizeof(node));
	
	pnode->key = key;
	pnode->val = val;
	
    //生成链表后，使其前驱后继都指向自己
	pnode->next = pnode;
	pnode->pre = pnode;
	
	return pnode;
}

//头插入双向循环链表
void insert_lru_in_head(node **pplisthead,node *pnode)
{
	assert(pplisthead != NULL);
	assert(pnode != NULL);

	if ((*pplisthead) == NULL)
	{
		(*pplisthead) = pnode;
		return;
	}
	
	(*pplisthead)->pre->next = pnode;
	pnode->pre = (*pplisthead)->pre;
	
	pnode->next = (*pplisthead);
	(*pplisthead)->pre = pnode;

	(*pplisthead) = pnode;
}

//删除双向循环链表中的某个节点，由于有的情况是删除尾巴节点后将其插到头节点，所以这里使用一个参数bool delete来表示是否释放其内存，不释放内存的情况则是为了将该节点再次插入。
void del_lru_node_by_node(node **pplisthead,node *pnode,bool delete)
{
	if (!pnode || !pplisthead || !(*pplisthead))
	{
		return;
	}

	node *pnewhead = pnode->next;//先记录下待删除节点的下一个节点
	
	//pnode脱lru链
	pnode->pre->next = pnode->next;
	pnode->next->pre = pnode->pre;
	
	pnode->next = pnode->pre = pnode;//将pnode的指针初始化避免引起干扰
	
	if ((*pplisthead) == pnode)//要删除的是头节点，则需要更新lrulist的头指针
	{
		if ((*pplisthead) != pnewhead)
		{
			(*pplisthead) = pnewhead;
		}
		else 
		{
			(*pplisthead) = NULL;//待删除的唯一的节点
		}
	}
	
	if (delete == true)
	{
		free(pnode);
	}
	
	#if 0
	由lru中每个结点的初始化值可知，以上指针转向是安全的：
	头结点、尾结点、中间结点、只有一个结点，都是适用的
	#endif
}

//释放双向循环链表
void free_lru_list(node **lruhead)
{
	if (!lruhead)
	{
		return;
	}
	
	node *phead = (*lruhead);
	
	while (phead)
	{
		node *ptmp = phead->next;
		if (ptmp == phead)
		{
			del_lru_node_by_node(lruhead,phead,TRUE);	
			(*lruhead) = NULL;
			return;
		}
		
		del_lru_node_by_node(lruhead,phead,TRUE);
		phead = ptmp;
	}
	
	return;
}

//在hash桶下的链表中查找键值为key的lru双向循环链表的节点
node *find_lru_node_by_key(hashnode *phashnode,int key)
{
	while (phashnode)
	{
		if (phashnode->pnode->key == key)
		{
			return phashnode->pnode;
		}
		
		phashnode = phashnode->next;
	}
	
	return NULL;
}

//打印，调试接口
void lru_list_print(LRUCache* obj)
{
	node *ptmp = obj->LruList;
	node *head = ptmp;
	printf("ndoe num: %d\n",obj->cur_lru_num);
	
	while (ptmp)
	{
		printf("key: %d val: %d ------> ",ptmp->key,ptmp->val);
		node *pnext = ptmp->next;
		if (pnext == head)
		{
			break;
		}
		ptmp = pnext;
	}
	
	printf("\n\n");
}

//get操作
int lRUCacheGet(LRUCache* obj, int key) {
	int index = hash_func(obj->capacity,key);
	hashnode *phead = obj->nodetable[index];
	node *plrunode = find_lru_node_by_key(phead,key);

	if (plrunode == NULL)
	{
		return -1;
	}
	
	//找到此节点后，将其从原位置摘下,再头插入lru链表
	del_lru_node_by_node(&obj->LruList,plrunode,false);	
	insert_lru_in_head(&obj->LruList, plrunode);
	
	return plrunode->val;
}

//put操作
void lRUCachePut(LRUCache* obj, int key, int value) {
	
	int index = hash_func(obj->capacity,key);
	hashnode *phashnode = obj->nodetable[index];
	
	if (phashnode == NULL)//hash表中index处的元素为空,那么lru链表中元素一定不存在
	{
		//由给定键值对,生成lru结点
		node *plrunode = lru_node_init(key,value);

		//生成该hash位置的第一个hash结点
		phashnode = hash_node_init(plrunode);
		
		obj->nodetable[index] = phashnode;
		
		//头插到lru链表中，但是要考虑lru链表的容积是否还够
		if (obj->cur_lru_num < obj->capacity)
		{
			insert_lru_in_head(&obj->LruList,plrunode);//将lru结点插入lru链表中
			++obj->cur_lru_num;
		}
		else 
		{
			//获取尾结点
			node *premove = obj->LruList->pre;

			//由尾结点的key值获取其hash桶位置
			int index = hash_func(obj->capacity,premove->key);

			hashnode *wait_del_hash_pos = obj->nodetable[index];//得到该结点所在的hash桶的头指针
			
			assert(wait_del_hash_pos != NULL);
			
			//从hash桶中清除此结点
			delete_hash_node_intable(&obj->nodetable[index],premove);
			
			//从lru中删除结点premove
			del_lru_node_by_node(&obj->LruList,premove,TRUE);
			
			//将新结点头插入lru链表中
			insert_lru_in_head(&obj->LruList, plrunode);

			//删掉一个结点后增加一个结点，结点数不变
		}
	}
	else 
	{
		node *plrunode = find_lru_node_by_key(phashnode,key);
		if (plrunode)
		{
			//hash桶下的链表中,若节点存在，那么键相同,值覆盖
			plrunode->val = value;
			
			//从lru链表中摘下此节点
			del_lru_node_by_node(&obj->LruList,plrunode,FALSE);

			//将此节点头插入lru链表
			insert_lru_in_head(&obj->LruList, plrunode);
		}
		else
		{
			plrunode = lru_node_init(key,value);//由给定键值对,生成lru结点
			
			hashnode *ptmpnode = hash_node_init(plrunode);
			
			//头插到lru中，但是要考虑lru的容积是否还够
			if (obj->cur_lru_num < obj->capacity)
			{
				insert_lru_in_head(&obj->LruList,plrunode);//将lru结点插入到hash位置处的单向链表			
				++obj->cur_lru_num;
			}
			else 
			{
				//获取尾结点
				node *premove = obj->LruList->pre;

				//由尾结点的key值获取其hash桶位置
				int index = hash_func(obj->capacity,premove->key);
				hashnode *wait_del_hash_pos = obj->nodetable[index];
				
				assert(wait_del_hash_pos != NULL);
				
				//从hash桶中清除此结点
				delete_hash_node_intable(&obj->nodetable[index],premove);
				
				//从lru中删除结点premove
				del_lru_node_by_node(&obj->LruList,premove,TRUE);
				
				//将新结点头插入lru链表中
				insert_lru_in_head(&obj->LruList, plrunode);

				//删掉一个结点后增加一个结点，结点数不变
			}

			//还必须插入hash表中
			insert_hash_node_intable(obj,ptmpnode);
		}
	}
	
	return;
}

//释放lru管理结构
void lRUCacheFree(LRUCache* obj) {
	if (obj)
	{
		//删除lru链表
		if (obj->capacity)
		{
			free_lru_list(&obj->LruList);
		}
		
		if (obj->nodetable)
		{
			//清理hash及其十字链表
			for (int i = 0;i < obj->capacity;++i)
			{
				free_hash_list(&obj->nodetable[i]);
			}
			
			free(obj->nodetable);
		}
		
		free(obj);
	}
}

//创建lru管理结构
LRUCache* lRUCacheCreate(int capacity) {
	if (capacity <= 0)
	{
		return NULL;
	}
	
	LRUCache *plru = (LRUCache *)malloc(sizeof(LRUCache));
	memset(plru,0,sizeof(LRUCache));
	plru->capacity = capacity;
	plru->nodetable = hashtable_init(capacity);
	return plru;
}

3. 本地运行

我本地ubuntu20 环境的下代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define true 1
#define false 0
#define bool int

struct LruNode {
	int key;
	int val;
	struct LruNode *next;
	struct LruNode *pre;
};

typedef struct LruNode node;

struct HashNode
{
	node *pnode;
	struct HashNode *next;
};

typedef struct HashNode hashnode;

typedef struct {
	int capacity;
	int cur_lru_num;
	node *LruList;//双向循环链表
	hashnode **nodetable;//hash表
} LRUCache;

//键值key的hash值计算函数
int hash_func(int capacity,int key)
{
	return key%capacity;
}

//hash表初始化
hashnode **hashtable_init(int capacity)
{
	hashnode **pnodetable = (hashnode **)malloc(sizeof(hashnode *)*capacity);
	memset(pnodetable,0,sizeof(hashnode *)*capacity);
	return pnodetable;
}

//hash桶下的节点hashnode的生成，使用lru双向链表的节点来初始化
hashnode *hash_node_init(node *pnode)
{
	hashnode *phashnode = (hashnode *)malloc(sizeof(hashnode));
	memset(phashnode,0,sizeof(hashnode));	
	phashnode->pnode = pnode;
	return phashnode;
}

//由于可能会修改上层结点，所以使用二级指针
void delete_hash_node_intable(hashnode **pphashhead,const node *plrunode)
{
	if (!pphashhead || !(*pphashhead) || !plrunode)
	{
		return;
	}
	
	hashnode *prenode = NULL;
	hashnode *pcurnode = (*pphashhead);
	hashnode *nextnode = (*pphashhead)->next;
	
    //遍历找到待删除节点
	while (pcurnode && pcurnode->pnode != plrunode)
	{
		prenode = pcurnode;
		pcurnode = pcurnode->next;
	}

	if (prenode == NULL)//待删除节点为第一个结点
	{
		free(pcurnode);
		(*pphashhead) = nextnode;//删除第一个结点后，要将hash表头指针指向下一个结点（其可能为NULL）
	}
	else if (pcurnode == NULL)//待删除节点不存在
	{
		return;
	}
	else
	{
		prenode->next = pcurnode->next;
		pcurnode->next = NULL;
		free(pcurnode);
	}
	
	return;
}

//插入hash桶下的链表中，插入顺序没有要求，所以使用最适宜的头插法
void insert_hash_node_intable(LRUCache *pObj,hashnode *pwaitadd)
{
	if (!pObj || !pwaitadd)
	{
		return;
	}
	
	int index = hash_func(pObj->capacity, pwaitadd->pnode->key);
	pwaitadd->next = pObj->nodetable[index];
	pObj->nodetable[index] = pwaitadd;
}

//删除hash桶下的链表，输入参数为该链表的链表头，删除后要就将其置空，所以使用二级指针
void free_hash_list(hashnode **pphashhead)
{
	if (!pphashhead || !(*pphashhead))
	{
		return;
	}

	hashnode *phead = (*pphashhead);
	
	while (phead)
	{
		hashnode *ptmp = phead->next;
		free(phead);
		phead = ptmp;
	}

	(*pphashhead) = NULL;//置空
}

//由给定的键值对，生成一个lru双向循环链表中的节点
node *lru_node_init(int key,int val)
{
	node *pnode = (node *)malloc(sizeof(node));
	
	memset(pnode,0,sizeof(node));
	
	pnode->key = key;
	pnode->val = val;
	
    //生成链表后，使其前驱后继都指向自己
	pnode->next = pnode;
	pnode->pre = pnode;
	
	return pnode;
}

//头插入双向循环链表
void insert_lru_in_head(node **pplisthead,node *pnode)
{
	assert(pplisthead != NULL);
	assert(pnode != NULL);

	if ((*pplisthead) == NULL)
	{
		(*pplisthead) = pnode;
		return;
	}
	
	(*pplisthead)->pre->next = pnode;
	pnode->pre = (*pplisthead)->pre;
	
	pnode->next = (*pplisthead);
	(*pplisthead)->pre = pnode;

	(*pplisthead) = pnode;
}

//删除双向循环链表中的某个节点，由于有的情况是删除尾巴节点后将其插到头节点，所以这里使用一个参数bool delete来表示是否释放其内存，不释放内存的情况则是为了将该节点再次插入。
void del_lru_node_by_node(node **pplisthead,node *pnode,bool delete)
{
	if (!pnode || !pplisthead || !(*pplisthead))
	{
		return;
	}

	node *pnewhead = pnode->next;//先记录下待删除节点的下一个节点
	
	//pnode脱lru链
	pnode->pre->next = pnode->next;
	pnode->next->pre = pnode->pre;
	
	pnode->next = pnode->pre = pnode;//将pnode的指针初始化避免引起干扰
	
	if ((*pplisthead) == pnode)//要删除的是头节点，则需要更新lrulist的头指针
	{
		if ((*pplisthead) != pnewhead)
		{
			(*pplisthead) = pnewhead;
		}
		else 
		{
			(*pplisthead) = NULL;//待删除的唯一的节点
		}
	}
	
	if (delete == true)
	{
		free(pnode);
	}
	
	#if 0
	由lru中每个结点的初始化值可知，以上指针转向是安全的：
	头结点、尾结点、中间结点、只有一个结点，都是适用的
	#endif
}

//释放双向循环链表
void free_lru_list(node **lruhead)
{
	if (!lruhead)
	{
		return;
	}
	
	node *phead = (*lruhead);
	
	while (phead)
	{
		node *ptmp = phead->next;
		if (ptmp == phead)
		{
			del_lru_node_by_node(lruhead,phead,TRUE);	
			(*lruhead) = NULL;
			return;
		}
		
		del_lru_node_by_node(lruhead,phead,TRUE);
		phead = ptmp;
	}
	
	return;
}

//在hash桶下的链表中查找键值为key的lru双向循环链表的节点
node *find_lru_node_by_key(hashnode *phashnode,int key)
{
	while (phashnode)
	{
		if (phashnode->pnode->key == key)
		{
			return phashnode->pnode;
		}
		
		phashnode = phashnode->next;
	}
	
	return NULL;
}

//打印，调试接口
void lru_list_print(LRUCache* obj)
{
	node *ptmp = obj->LruList;
	node *head = ptmp;
	printf("ndoe num: %d\n",obj->cur_lru_num);
	
	while (ptmp)
	{
		printf("key: %d val: %d ------> ",ptmp->key,ptmp->val);
		node *pnext = ptmp->next;
		if (pnext == head)
		{
			break;
		}
		ptmp = pnext;
	}
	
	printf("\n\n");
}

//get操作
int lRUCacheGet(LRUCache* obj, int key) {
	int index = hash_func(obj->capacity,key);
	hashnode *phead = obj->nodetable[index];
	node *plrunode = find_lru_node_by_key(phead,key);

	if (plrunode == NULL)
	{
		return -1;
	}
	
	//找到此节点后，将其从原位置摘下,再头插入lru链表
	del_lru_node_by_node(&obj->LruList,plrunode,false);	
	insert_lru_in_head(&obj->LruList, plrunode);
	
	return plrunode->val;
}

//put操作
void lRUCachePut(LRUCache* obj, int key, int value) {
	
	int index = hash_func(obj->capacity,key);
	hashnode *phashnode = obj->nodetable[index];
	
	if (phashnode == NULL)//hash表中index处的元素为空,那么lru链表中元素一定不存在
	{
		//由给定键值对,生成lru结点
		node *plrunode = lru_node_init(key,value);

		//生成该hash位置的第一个hash结点
		phashnode = hash_node_init(plrunode);
		
		obj->nodetable[index] = phashnode;
		
		//头插到lru链表中，但是要考虑lru链表的容积是否还够
		if (obj->cur_lru_num < obj->capacity)
		{
			insert_lru_in_head(&obj->LruList,plrunode);//将lru结点插入lru链表中
			++obj->cur_lru_num;
		}
		else 
		{
			//获取尾结点
			node *premove = obj->LruList->pre;

			//由尾结点的key值获取其hash桶位置
			int index = hash_func(obj->capacity,premove->key);

			hashnode *wait_del_hash_pos = obj->nodetable[index];//得到该结点所在的hash桶的头指针
			
			assert(wait_del_hash_pos != NULL);
			
			//从hash桶中清除此结点
			delete_hash_node_intable(&obj->nodetable[index],premove);
			
			//从lru中删除结点premove
			del_lru_node_by_node(&obj->LruList,premove,TRUE);
			
			//将新结点头插入lru链表中
			insert_lru_in_head(&obj->LruList, plrunode);

			//删掉一个结点后增加一个结点，结点数不变
		}
	}
	else 
	{
		node *plrunode = find_lru_node_by_key(phashnode,key);
		if (plrunode)
		{
			//hash桶下的链表中,若节点存在，那么键相同,值覆盖
			plrunode->val = value;
			
			//从lru链表中摘下此节点
			del_lru_node_by_node(&obj->LruList,plrunode,FALSE);

			//将此节点头插入lru链表
			insert_lru_in_head(&obj->LruList, plrunode);
		}
		else
		{
			plrunode = lru_node_init(key,value);//由给定键值对,生成lru结点
			
			hashnode *ptmpnode = hash_node_init(plrunode);
			
			//头插到lru中，但是要考虑lru的容积是否还够
			if (obj->cur_lru_num < obj->capacity)
			{
				insert_lru_in_head(&obj->LruList,plrunode);//将lru结点插入到hash位置处的单向链表			
				++obj->cur_lru_num;
			}
			else 
			{
				//获取尾结点
				node *premove = obj->LruList->pre;

				//由尾结点的key值获取其hash桶位置
				int index = hash_func(obj->capacity,premove->key);
				hashnode *wait_del_hash_pos = obj->nodetable[index];
				
				assert(wait_del_hash_pos != NULL);
				
				//从hash桶中清除此结点
				delete_hash_node_intable(&obj->nodetable[index],premove);
				
				//从lru中删除结点premove
				del_lru_node_by_node(&obj->LruList,premove,TRUE);
				
				//将新结点头插入lru链表中
				insert_lru_in_head(&obj->LruList, plrunode);

				//删掉一个结点后增加一个结点，结点数不变
			}

			//还必须插入hash表中
			insert_hash_node_intable(obj,ptmpnode);
		}
	}
	
	return;
}

//释放lru管理结构
void lRUCacheFree(LRUCache* obj) {
	if (obj)
	{
		//删除lru链表
		if (obj->capacity)
		{
			free_lru_list(&obj->LruList);
		}
		
		if (obj->nodetable)
		{
			//清理hash及其十字链表
			for (int i = 0;i < obj->capacity;++i)
			{
				free_hash_list(&obj->nodetable[i]);
			}
			
			free(obj->nodetable);
		}
		
		free(obj);
	}
}

//创建lru管理结构
LRUCache* lRUCacheCreate(int capacity) {
	if (capacity <= 0)
	{
		return NULL;
	}
	
	LRUCache *plru = (LRUCache *)malloc(sizeof(LRUCache));
	memset(plru,0,sizeof(LRUCache));
	plru->capacity = capacity;
	plru->nodetable = hashtable_init(capacity);
	return plru;
}


LRUCache* g_LruCache = NULL;

int main1()
{
	int capacity = 4;
	g_LruCache = lRUCacheCreate(capacity);

	//1. 先插满4个
	int key = 10;
	int value = 45;
	lRUCachePut(g_LruCache,key,value);
	
	key = 2;
	value = 23;
	lRUCachePut(g_LruCache,key,value);
	
	key = 9;
	value = 1;
	lRUCachePut(g_LruCache,key,value);
	
	key = 8;
	value = 7;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);


	//更新一个中间节点
	key = 9;
	value = 45;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//更新一个尾巴中间节点
	key = 10;
	value = 3;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//更新一个头节点
	key = 10;
	value = 12;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//插入一个新节点
	key = 45;
	value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//插入一个新节点
	key = 13;
	value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	printf("[get]   key: %d val: %d\n",45,lRUCacheGet(g_LruCache, 45));
	lru_list_print(g_LruCache);
	
	printf("[get]   key: %d val: %d\n",9,lRUCacheGet(g_LruCache, 9));
	lru_list_print(g_LruCache);

	printf("[get]   key: %d val: %d\n",10,lRUCacheGet(g_LruCache, 10));
	lru_list_print(g_LruCache);

	//访问一个不存在的节点
	printf("[get]   key: %d val: %d\n",7,lRUCacheGet(g_LruCache, 7));
	lru_list_print(g_LruCache);
	
	printf("[get]   key: %d val: %d\n",2,lRUCacheGet(g_LruCache, 2));
	lru_list_print(g_LruCache);
		
	printf("[get]   key: %d val: %d\n",13,lRUCacheGet(g_LruCache, 13));
	lru_list_print(g_LruCache);

	printf("[get]   key: %d val: %d\n",8,lRUCacheGet(g_LruCache, 7));
	lru_list_print(g_LruCache);
	
	lRUCacheFree(g_LruCache);
	return 0;
}

int main2()
{
	int capacity = 2;
	g_LruCache = lRUCacheCreate(capacity);
	lru_list_print(g_LruCache);
	
	int key = 1;
	int value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	key = 2;
	value = 2;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);
	
	printf("[get]   key: %d val: %d\n",1,lRUCacheGet(g_LruCache, 1));
	lru_list_print(g_LruCache);
		
	key = 3;
	value = 3;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);
	
	printf("[get]   key: %d val: %d\n",2,lRUCacheGet(g_LruCache, 2));
	lru_list_print(g_LruCache);
	
	key = 4;
	value = 4;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);
	
	printf("[get]   key: %d val: %d\n",1,lRUCacheGet(g_LruCache, 1));
	lru_list_print(g_LruCache);

	printf("[get]   key: %d val: %d\n",3,lRUCacheGet(g_LruCache, 3));
	lru_list_print(g_LruCache);

	printf("[get]   key: %d val: %d\n",4,lRUCacheGet(g_LruCache, 4));
	lru_list_print(g_LruCache);


	lRUCacheFree(g_LruCache);
	return 0;
}

int main3()
{
	int capacity = 1;
	g_LruCache = lRUCacheCreate(capacity);
	lru_list_print(g_LruCache);
	
	int key = 2;
	int value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//2
	printf("[get]   key: %d val: %d\n",key,lRUCacheGet(g_LruCache, key));
	lru_list_print(g_LruCache);

	key = 3;
	value = 2;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//2
	printf("[get]   key: %d val: %d\n",2,lRUCacheGet(g_LruCache, 2));
	lru_list_print(g_LruCache);

	//3
	printf("[get]   key: %d val: %d\n",3,lRUCacheGet(g_LruCache, 3));
	lru_list_print(g_LruCache);

	lRUCacheFree(g_LruCache);
	return 0;
}

int main()
{
	int capacity = 2;
	g_LruCache = lRUCacheCreate(capacity);
	lru_list_print(g_LruCache);
	
	int key = 2;
	int value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	key = 1;
	value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//2
	printf("[get]   key: %d val: %d\n",2,lRUCacheGet(g_LruCache, 2));
	lru_list_print(g_LruCache);

	key = 4;
	value = 1;
	lRUCachePut(g_LruCache,key,value);
	lru_list_print(g_LruCache);

	//1
	printf("[get]   key: %d val: %d\n",1,lRUCacheGet(g_LruCache, 1));
	lru_list_print(g_LruCache);

	//2
	printf("[get]   key: %d val: %d\n",2,lRUCacheGet(g_LruCache, 2));
	lru_list_print(g_LruCache);

	lRUCacheFree(g_LruCache);
	return 0;
}