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

实现该功能分析:

(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 };

 

发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

算法: skiplist 跳跃表代码实现和原理讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。