c/c++数据结构设计

Question

马上过年了，去某公司面试了下，遇到一个算法题，想与各位请教下，我面试现场给出的答案不够高效，存在问题，感觉面试的不好。

有如下数据结构，在内存中最多保留10w份，有两个进程，主进程来根据md5查询这个结构里的文件信息，如果没有则丢给线程去查询，然后将查到的结果(file_info信息)插入到内存这个结构中。

主进程查询一次后则增加vist_times一次，当内存中存了10w份后，线程需要添加时，根据vist_times删除访问量最少的1w份。

有没有已有成熟的结构，比如c++ stl能够高效实现这个功能?

由于主进程只查询 线程写入查到信息，是否需要加锁?

typedef struct _file_info
{
    char md5[32];
    //文件其它信息

    //信息访问次数
    uint64_t  vist_times;
    
}file_info;

Answer 1

看题目描述，我感觉是想做缓存，根据LRU算法淘汰最少访问的节点。

这里需要两种查询，一是根据 md5 查询到这个数据结构，二是查询 vist_times 值最小的节点。

一可以用哈希表或红黑树完成，对应std::map或者std::unordered_map；二可以通过优先队列完成，堆，二项队列，斐波那契额堆都可以，对应std::priority_queue。

主线程查询就用map从md5映射到file_info的指针查询。子线程插入要把结构的指针同时插入map和priority_queue，如果到达10万份，就从priority_queue查询顶端的1万分。需要加锁。

这里由于是另一个辅助线程负责更新缓存，淘汰也是每次淘汰1万个，这样优先队列可以省去，每次达到10万就用类似快速排序的算法查找第9万大的数字，然后遍历缓存，删除所有不大于第9万大的数字的节点。这样可能会多删除几个节点，也会把CPU压力集中。

如果是面试的话，答得好后续应该还会问别的，比如换成LRU要如何实现，如何避免一次偶然访问的数据白白占用缓存，遍历所有数据的时候需不需要缓存，有没有可能快速判断一个md5一定不在缓存里，安达尔定律等等。