1

我正在阅读一些来自 Enthuware 考试模拟器的示例问题。我遇到了一个问题，其问题陈述是这样的

您正在设计一个将缓存对象的类。当提供对象标识符时，它应该能够存储和检索对象。此外，此类应通过跟踪对象的“最后访问时间”来工作。因此，如果它的容量已满，它应该只删除最长未访问的对象。

您将使用哪个集合类来存储对象？

给出的可能选项是

  1. 哈希集
  2. 数组列表
  3. LinkedHashMap
  4. 链表
  5. 树状图

模拟器给出的正确答案是LinkedHashMap。我会引用模拟器给出的解释。

LinkedHashMap 类按照插入时间的顺序维护元素。此属性可用于构建所需的缓存，如下所示：

  1. 像往常一样插入键值对，其中键是对象标识符，值是要缓存的对象。

  2. 当请求一个键时，将其从 LinkedHashMap 中移除，然后再次插入。这将确保这对标记为最新插入。

  3. 如果容量已满，则删除第一个元素。

请注意，您不能简单地再次插入键值（不先将其删除），因为重新插入操作不会影响对的位置。

我只理解第一点。仍然是以下问题。

  1. 在第 1 点中它指出，该值将是要缓存的对象吗？缓存如何像这样应用？
  2. 从第 2 点开始，我无法理解。

有人可以向我解释这个概念吗？谢谢。

4

5 回答 5

4

我相信您应该从示例中获取“缓存”，并保留一粒盐：它旨在提供一些上下文，但并不完全相关。

这里的缓存可能意味着从集合中检索一个值，而不是访问数据源并从那里获取它。

至于你的第二个问题：

当请求一个键时，将其从 LinkedHashMap 中移除，然后再次插入。这将确保这对标记为最新插入。

考虑以下地图：

身份证 | 值
1 | 杰克
5 | 约翰
3 | 珍妮

在这种情况下Jack，先进入，然后再John进入Jenny。现在我们要检索 的缓存值John。如果我们想这样做，我们首先检索他的唯一标识符 ( 5) 的值，然后我们得到对象John作为结果。现在我们有了缓存值，但是跟踪上次访问时间的要求还没有完成。因此我们删除他并再次添加他，基本上将他放在最后。

身份证 | 值
1 | 杰克
3 | 珍妮
5 | 约翰

John 保持缓存状态，但现在他的访问时间已更新。每当地图已满时，您都会删除第一个项目（这实际上是最长时间未访问的项目）。

如果地图的最大尺寸为3并且我们尝试添加Jeff，我们会得到以下情况：

身份证 | 价值
3 | 珍妮
5 | 约翰
7 | 杰夫

第一项 ( Jack) 以及最近访问的对象将被删除，为新对象（最近访问的对象）腾出位置。

于 2013-08-25T13:25:36.927 回答
2

In point-1 it states, the value will be the object to be cached? How does caching apply like this?

Caching an object here means storing the created objects, in some collections, so that they can be retrieved later. Now as the requirement is to store and retrieve objects using it's key, clearly a Map is the option here, which will store the mapping from object's Key to the object itself.

Also, LinkedHashMap is suitable, because it maintains the insertion order. So, the first object you create, will be the first in the that map.

When a key is requested, remove it from the LinkedHashMap and then insert it again. This will make sure that this pair marked as inserted latest.

Again, take a look at the requirement. It says, the elements that haven't be accessed for long, should be removed. Now suppose an object which is at the first position, hasn't been accessed for long. So, when you access it now, you wouldn't want to be still in the first position, because in that case, when you remove the first elements, you will be removing the elements you just accessed.

That is why you should remove the element, and insert it back, so that it is placed at the end.

If the capacity is full, remove the first element.

As it's already clear, the first element is the one, which was inserted first, and has the oldest access time. So, you should remove the first element only, as the requirement says:

if its capacity is full, it should remove only the object that hasn't been accessed the longest.

于 2013-08-25T13:24:25.230 回答
2

第一步，确定您是否需要 Set、Map 或 List。

  1. 列表保留顺序。
  2. 地图允许快速、基于键的项目查找。
  3. 集合提供基于身份的成员资格，换句话说，没有重复。

您可能想要按键查找，所以它是某种地图。但是，您还想保持秩序。乍一看，LinkedHashMap 似乎是赢家，但事实并非如此。

LinkedHashMap 保留插入顺序，并且您希望保留访问顺序。要将一个元素扭曲成另一个元素，您必须在访问每个元素时将其删除并重新添加。这是非常浪费的，并且会受到时间问题的影响（在可能的原子添加和读取之间）。

您可以通过维护两个内部数据结构来简化两者。

  1. 用于快速访问的 HashMap。
  2. 根据访问时间快速重新排序的链接列表。

当您插入时，hashmap 存储一个链表节点，谁的键是链表节点中存储的数据对象的键。该节点被添加到列表的“较新”端。

当您访问时，hashmap 会拉起链表节点，然后将其移除并插入到链表的头部。（并返回数据）。

当您删除时，hashmap 会拉起链表节点，并将其从链表中删除，并清除 hashmap 条目。

删除过期条目时，从链表的旧端删除，不要忘记清除hashmap条目。

通过这样做，您构建了自己的 LinkedHashMap，但它根据访问时间而不是插入顺序进行跟踪。

于 2013-08-25T13:35:23.393 回答
1

他们忽略了三个非常重要的点：

  1. 与 一起LinkedHashMap，确定何时开始删除对象的机制是必要的。最简单的一种是将计数器availableCapacity初始化为最大容量并相应地递减/递增。另一种方法是将size()的LinkedHashMap与maximumCapacity变量进行比较。
  2. （LinkedHashMap特别是它的values()）假定包含指向缓存对象/结构的唯一指针。如果保留任何其他指针，则假定它们是瞬态的。
  3. 缓存将在 LRU 制度下进行管理。

这就是说，并回答您的问题：

  1. 是的。
  2. 根据定义，firstLinkedHashMap 中的项目是第一个插入的（“最旧的”）。如果每次使用缓存条目时，它都会被删除并重新插入到映射中，它会被放置在列表的末尾，从而成为“最新的”。 first永远是最久未使用的那个。“第二”以下，以此类推。这就是为什么前面的元素被删除的原因。
于 2013-08-25T13:46:16.377 回答
0

LinkedHashMap stores items in the order they were inserted. They're using one to implement an LRU cache. The keys are the object identifiers. The values are the items to be cached. Maps have a very fast lookup time, which is what makes the map a cache. It's faster to do the lookup than to

Inserting items into the map puts them at the end of the map. So every time you read something, you take it out and put it back on the end. Then, when you need more room in your cache, you chop off the first element. That's the one that hasn't been used in the longest time, because it made its way all the way to the front.

于 2013-08-25T13:24:28.917 回答