如何实现动态索引？
How to implement dynamic indexes?
我知道，可能标题有点乱。但是，我认为我的实际问题是基本的。
我正在研究一个全新的 LRU 实现，我使用索引 Table 将传入数据包的名称映射到数据包内容存储在 CS 中的位置的索引。
如下图所示，每个传入数据包都存储在 CS 中，并且可以通过索引 Table 进行寻址。
现在假设有新的数据包到达，我们知道，对于LRU，它的索引必须设置在CS的顶部（零）并且它需要升级其他索引，因此它们需要递增。
一个明显的解决方案是遍历索引 Table 中的所有条目并递增它们。
是否有解决此类问题的解决方案或结构？
我在描述中没有看到您是如何建立缓存顺序的。但是要回答你的问题，可以将 LRU 存储方法的时间复杂度降低到 O(1)。
经典的做法是拥有这两个数据结构：
双向链表：缓存中的顺序。每个节点存储一个数据元素（它扮演您的内容存储的角色）。
HashMap 将每个key关联到指向链表中节点的指针。 （它起到了你索引的作用table）
所以当你访问缓存中已经存储的数据时，它必须在列表的顶部，所以你从链表中删除相应的节点（在 O(1) 时间内，因为你可以访问它的前一个和下一个节点）并将其存储在头部。
对于新数据来说更简单，只将它存储在列表的头部并将你的（键，值）存储在哈希图中。
我知道，可能标题有点乱。但是，我认为我的实际问题是基本的。
我正在研究一个全新的 LRU 实现，我使用索引 Table 将传入数据包的名称映射到数据包内容存储在 CS 中的位置的索引。
如下图所示，每个传入数据包都存储在 CS 中，并且可以通过索引 Table 进行寻址。
现在假设有新的数据包到达，我们知道，对于LRU，它的索引必须设置在CS的顶部（零）并且它需要升级其他索引，因此它们需要递增。
我在描述中没有看到您是如何建立缓存顺序的。但是要回答你的问题，可以将 LRU 存储方法的时间复杂度降低到 O(1)。
经典的做法是拥有这两个数据结构：
双向链表：缓存中的顺序。每个节点存储一个数据元素（它扮演您的内容存储的角色）。
HashMap 将每个key关联到指向链表中节点的指针。 （它起到了你索引的作用table）
所以当你访问缓存中已经存储的数据时，它必须在列表的顶部，所以你从链表中删除相应的节点（在 O(1) 时间内，因为你可以访问它的前一个和下一个节点）并将其存储在头部。
对于新数据来说更简单，只将它存储在列表的头部并将你的（键，值）存储在哈希图中。