54

问答题 54 /69

设计并实现一个LRU Cache

参考答案

下面是一个参考思路
• 重要数据结构:key-value存储、LRU存储;
• key-value存储:hash_table/map,LRU:链表,因为可以快速实现增加、删除
• 如何更新Cache: 找到key在链表中的位置,删除并将它插到表头,同时更新key到链表位置的映射
• 快速找到最不常访问的元素:链表尾