算法: 实现LRU缓存，读取、写入O(1)实现

你猜阅读：755 2020-10-19 15:34:36 评论：0

这题应该见的不少了，写写记录一下。

实现该功能分析:

(1) O(1) 时间完成查找，那除了 hash 别无选择。

(2) LRU 最近最少使用算法，为了方便数据的淘汰。需要对最近访问的数据放未访问数据之前。

用双向链表实现即可。(通常情况下，双向链表读取、插入的时间复杂度都是O(n), 但是如果知道插入位置，则可以实现O(1)实现。)

实现: hash存key对应的数据在双向链表中的位置，就可以完成该功能。

具体代码:

 1 #include <iostream> 
 2 #include <list> //std::list双向链表实现 
 3 #include <map> 
 4  
 5 const int MAX_VALUE_LEN = 32; 
 6 const int MAX_ELEMENT_NUM = 3; 
 7  
 8 struct CacheNode{ 
 9     int key; 
10     int len; 
11     char data[MAX_VALUE_LEN]; 
12 }; 
13  
14 class LRU{ 
15 public: 
16     //默认10个原始 
17     LRU(int max_num = MAX_ELEMENT_NUM); 
18     ~LRU(); 
19  
20     //数据获取 
21     bool get(const int key, char *data, int &len); 
22  
23     //新增数据 
24     bool set(const int key, const char* data, const int len); 
25  
26     //打印数据 
27     void print_list(); 
28 private: 
29     
30     //更新节点的链接 
31     //访问元素后, 需要将元素放置在list 头部 
32     int update_node_link(const int key); 
33  
34     int _max_num; 
35     std::list<CacheNode*> _list; 
36     std::map<int, std::list<CacheNode*>::iterator> _map; 
37 };

标签:加密算法面试

声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。