我知道，也许标题有点令人困惑。然而，我认为我的实际问题是基本的。
我正在开发一个全新的 LRU 实现，我使用索引表将传入数据包的名称映射到 CS 中存储数据包内容的索引。
如下所示，每个传入数据包都存储在 CS 中，并且可以通过索引表进行寻址。
现在假设新数据包到达，正如我们所知，对于 LRU，其索引必须设置为 CS 的顶部(零)，并且需要升级其他索引，因此它们需要递增。
一种明显的解决方案是循环索引表中的所有条目并递增它们。
是否有任何解决方案或结构可用于解决此类问题？
最佳答案
我不明白你如何在描述中建立缓存的顺序。但为了回答你的问题，可以将 LRU 存储方法的时间复杂度降低到 O(1)。
经典的方法是使用以下两种数据结构:
双向链表:用于缓存中的顺序。每个节点存储一个数据元素(它扮演内容存储的角色)。
HashMap 将每个键与指向链表中节点的指针相关联。 (它起到索引表的作用)
因此，当您访问缓存中已存储的数据时，它必须位于列表的顶部，因此您从链表中删除相应的节点(在 O(1) 时间内，因为您可以访问其上一个和下一个节点)并将其存储在头部。
对于新数据更简单，只需将其存储在列表的头部并将您的(键，值)存储在 HashMap 中。
关于caching - 如何实现动态索引？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59198623/