数据结构与算法: 缓存置换算法
发布于: 3 小时前
本文主要记录和置换算法的一些介绍。
LRU Cache
LRU(Least Recently Used)，即最近最少使用。该缓存存在一个容量当容量达到最大时，最久没有访问的项目被删除。
可以使用双向链表和 Hash 表进行实现，最终可以达到
时间复杂度：
get和set都是O(1)，其中 Hash 定位以及链表操作的复杂度都是O(1)。
空间复杂度：
O(Capacity)
实现
LFU Cache
Least Frequently Used，即最近最不常用页面置换算法。将最近最少访问的项目替换掉
参考资料
版权声明: 本文为 InfoQ 作者【正向成长】的原创文章。
原文链接:【http://xie.infoq.cn/article/39a26e543e2dfac4e284826e7】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
正向成长 2018.08.06 加入
想要坚定地做大规模数据处理(流数据方向)，希望结合结合批处理的传统处理方式，以及之后流批混合处理方向进行学习和记录。
评论