🔥字节高频面试算法：缓存算法LRU和LFU的简易实现

• 通用接口：既然是缓存，管理数据，那么必然有put()和get()以及delete()接口。

  • boolean put(int key, String value)
    • 需要考虑元素是否存在，缓存是否满的问题
    • 如果元素已经存在，则需要更新到最新的位置即可
    • 如果元素不存在，则需要需要插入数据到最新的位置
    • 如果缓存已满，则需要清除最老的一个元素，再进行插入更新
  • String get(int key)
    • 如果元素不存在，则返回空，
    • 存在的话，返回对于元素，并且更新元素只最新位置。
  • boolean delete(int x)
    • 如果元素不存在，则删除失败。
    • 如果元素存在，则进行删除。

• LRU相关：既然是管理最近最少数据的，则必须考虑元素顺序，以及管理最近元素

  • String getRecent()
    • 获取最近的元素，并重新更新到队尾
  • boolean makeRecently(Nodelj node)
    • 更新最近元素
  • boolean addRecently(int x, String value)
    • 新增最近元素
  • boolean deleteLeast()
    • 删除最近不使用的元素

• LFU相关：既然是管理最近最久数据的，则必须考虑元素频率

  • void increaseFreq(int key)
    • 提升频率
  • void pageElimination()
    • 替换操作，页面淘汰

存储底层元素的数据结构设计

• 数据结构需求
  • 需要一个结构来承接元素的先后顺序，且方便新增删除：链表
  • 在进行删除第一个元素和插入最后一个元素时，能快速定位：带头节点和尾节点的链表
  • 能方便在两端进行查找：带头节点和尾节点的双向链表
• 数据结构实现
  • 双向链表
    DuplexListljImpl
  • 双向链表节点
    Nodelj
• 该双向链表需要具备以下功能：
  • boolean insertLast(Nodelj node)
    • 将一个元素插入到链表尾部
  • boolean delete(Nodelj node)
    • 删除元素，并梳理节点关系
  • Nodelj deleteOld()
    • 删除并返回 链表首元素【当前链表中最早插入的元素】，即头节点指向的那个元素
  • Nodelj getLeast()
    • 返回 链表最后一个元素【最新插入的元素】，即尾节点指向的那个元素

源码