C语言实现LRU缓存机制——哈希表+双向链表_c语言实现 lru 哈希表+双向链表

题目描述

题目来源：
https://leetcode-cn.com/problems/lru-cache/
运用你所掌握的数据结构，设计和实现一个LRU（最近最少使用）缓存机制。它应该支持以下操作：获取数据get和写入数据 put。
获取数据get（key）-如果关键字（key）存在于缓存中，则获取关键字的值（总是正数），否则返回-1。
写入数据put（key，value）-如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组[关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
要求：时间复杂度为O（1）：

思路：1

1、一开始想的是用一个类似于数组栈来实现，栈中的的数据结构为一个key值和value值：

类似于这样，在put的时候，如果栈中元素已满例如存放的数据如下：

下一步要存放（4，4），数据元素已满，那么依次下移元素：

在插入元素：（4，4）

这样就能保证插入的元素在最顶部，如果元素已满，把最久未使用的元素删除。
在Get的时候，如果元素在内部，则把该元素置顶，其他元素依次下移:代码如下：

typedef struct{    
	int key;   
 	int value;
 }Stack;
 typedef struct {    
 	Stack *S;
 	int top;    
 	int Max_size;
 } LRUCache;

LRUCache* lRUCacheCreate(int capacity) 
{    
	LRUCache *obj = (LRUCache *)malloc(sizeof(LRUCache));    
	obj->S = (Stack *)malloc(sizeof(Stack)*capacity);    
	obj->top = -1;    
	obj->Max_size=capacity;    
	return obj;
}
int lRUCacheGet(LRUCache* obj, int key) {
	
	int i = 0;    
	Stack temp;    
	int j = 0;    
	for(i;i<=obj->top;i++)    
	{        
		if(obj->S[i].key == key)        
		{            
			temp = obj->S[i];            
			for( j = i;j<obj->top;j++)            
			{                
				obj->S[j]=obj->S[j+1];            
			}            
			obj->S[j] = temp;            
			return temp.value;        
		}            
	}    
	return -1;
}
void lRUCachePut(LRUCache* obj, int key, int value) {
    	int i =0;    
    	int j = 0;    
    	Stack temp;    
    	for(i;i<=obj->top;i++)    
    	{        
    		if(obj->S[i].key == key)        
    		{            
    			obj->S[i].value = value;            
    			temp = obj->S[i];            
    			for(j=i;j<obj->top;j++)            
    			{                
    				obj->S[j]=obj->S[j+1];            
    			}            
    			obj->S[j] = temp;            
    			return ;        
    			}    
    		}    
    		if(i<obj->Max_size)    
    		{        
	    		obj->S[i].key = key;        
	    		obj->S[i].value = value;        
	    		obj->top++;        
	    		return ;    
	    	}else{        
	    		int temp_1 = i-1;               
	    		i=0;        
	    		for(i;i<obj->top;i++)        
	    		{            
	    			obj->S[i] = obj->S[i+1];        
	    		}        
	    		obj->S[temp_1].key = key;        
	    		obj->S[temp_1].value = value;        
	    		return ;   
	    	}
}
void lRUCacheFree(LRUCache* obj) {    free(obj);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

这一种思路的时间复杂度很大；

思路：二

题目要求时间复杂度为O（1）；
（1）数组的查找时间复杂度为1，但是增加数据和删除数据时时间复杂度很高
（2）链表无法做到更新，查找为1.
（3）哈希表数据是没有顺序的，没有办法找到最久未使用。
可以把链表和哈希表两中数据结构混合使用，哈希表中保存链表中数据的映射，可以快速找到链表中的数据，进而实现时间复杂度近似为1。
例如：要查找2这个数据，在哈希表中可以快速查找到2这个数，之后在链表中实现删除和增加元素。

具体思路：
（1）：对于get操作，首先判断key是否存在：如果key不存在，则返回一1
如果key存在，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
（2）对于put 操作，首先判断key是否存在：如果key 不存在，创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；。如果key存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部。

代码实现

typedef struct node{    
	int val;    
	int key;    
	struct node *pre;   
	struct node *next;
}Node,*LinkList;//双向链表节点结构
typedef struct {    
	LinkList store;//用来存放数据    
	LinkList *next;//使用拉链发处理冲突
}Hash;//哈希表数据结构
typedef struct {        
	int size;//当前缓存大小    
	int capacity;//缓存容量    
	Hash* table;//哈希表    
	LinkList head;// 指向最近使用的数据    
	LinkList tail;// 指向最久未使用的数据    
} LRUCache;
Hash * HashMap(Hash *table,int key,int capacity){    
	int addr = key % capacity;    
	return &table[addr];
}
void HeadInsertion(LinkList head, LinkList cur)
{//双链表头插法    
	if (cur->pre == NULL && cur->next == NULL)    
	{// cur 不在链表中                
		cur->pre = head;        
		cur->next = head->next;        
		head->next->pre = cur;        
		head->next = cur;    
	} else 
	{// cur 在链表中        
		LinkList first = head->next;//链表的第一个数据结点
		if ( first != cur)        
		{//cur 是否已在第一个            
		cur->pre->next = cur->next;//改变前驱结点指向        
		cur->next->pre = cur->pre;//改变后继结点指向         
		cur->next = first;//插入到第一个结点位置           
		cur->pre = head;            
		head->next = cur;            
		first->pre = cur;        
		}    
	}
}
LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* obj = (LRUCache*)malloc(sizeof(LRUCache));
    obj->table = (Hash*)malloc(capacity * sizeof(Hash));    
    memset(obj->table, 0, capacity * sizeof(Hash));    
    obj->head = (LinkList)malloc(sizeof(Node));    
    obj->tail = (LinkList)malloc(sizeof(Node));    //创建头、尾结点并初始化   
     obj->head->pre = NULL;    
     obj->head->next = obj->tail;    
     obj->tail->pre = obj->head;    
     obj->tail->next = NULL;    
     //初始化缓存 大小 和 容量     
     obj->size = 0;    
     obj->capacity = capacity;    
     return obj;
     }
int lRUCacheGet(LRUCache* obj, int key) {    
	Hash* addr = HashMap(obj->table, key, obj->capacity);//取得哈希地址    
	addr = addr->next;//跳过头结点    
	if (addr == NULL){       
	 return -1;    
	 }   
	 while ( addr->next != NULL && addr->store->key != key)    
	 {//寻找密钥是否存在        
	 	addr = addr->next;    
	 }   if (addr->store->key == key)   
	  {//查找成功        
	  	HeadInsertion(obj->head, addr->store);//更新至表头        
	  	return addr->store->val;    
	  }    
	  	return -1;
}
void lRUCachePut(LRUCache* obj, int key, int value) {
    Hash* addr = HashMap(obj->table, key, obj->capacity);//取得哈希地址    
    if (lRUCacheGet(obj, key) == -1)    
    {        
    	if (obj->size>= obj->capacity)
	{                        
		LinkList last = obj->tail->pre->pre;            	
		LinkList del = last->next;            
		last->next = obj->tail;            
		obj->tail->pre = last;                        
		Hash *delt = HashMap(obj->table,del->key,obj->capacity);//找到要删除的地址            
		Hash *help_delt = delt;            
		delt = delt->next;            
		while(delt->store->key != del->key)            
		{               
			 help_delt = delt;//删除的前一个节点                
			 delt = delt->next;            
		}            
		help_delt->next = delt->next;           
		 delt->store = NULL;            
		 delt->next=NULL;            
		 free(delt);

            Hash * new_insert = (Hash*)malloc(sizeof(Hash));
            new_insert->next = addr->next;            
            addr->next = new_insert;
            new_insert->store = del;            
            del->key = key;           
             del->val=value;            
             HeadInsertion(obj->head,del);                  
       }        
       else        
       {//LPU未满            
       Hash* new_node = (Hash *)malloc(sizeof(Hash));            		
       new_node->store = (LinkList)malloc(sizeof(Node));            
       new_node->next = addr->next;            
       addr->next = new_node;            
       new_node->store->pre  = NULL;            
       new_node->store->next = NULL;            
       new_node->store->val  = value;            
       new_node->store->key  = key;            
       HeadInsertion(obj->head,new_node->store);            
       (obj->size)++;                   
        }                  
   }    
   else   
    {        
    obj->head->next->val = value;//替换数据值    
    }
}
void lRUCacheFree(LRUCache* obj) {    
	free(obj->table);    
	free(obj->head);    
	free(obj->tail);    
	free(obj);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130