创建按Java中的创建/更新时间排序的有序HashMap

Question

我正在使用以下格式的数据元组：[IP，字节数，时间]。我在IP上创建了一个HashMap来计算为每个IP服务的字节数。然后，我意识到我需要删除最近最少使用的键值对来创建更多空间。我想创建一个时间约束，比如说1小时，并且在那段时间内没有动作的情况下删除键值对。所以我需要保存每一对的更新时间。事实上，对于具有按时间戳排序的对的良好性能来说似乎是合理的。

因此，我想要做的是维护一个基于键值对的创建或更新时间的排序列表。我需要明确地了解这些创建和更新时间。我提出了两个不同的想法，但现在确切地确定要使用哪一个以及如何使用。这里是我的两个想法：

• 我需要一个LinkedList头指向最近更新的键值对的时间戳，并有这个键值对点列表节点。
• 我需要根据其创建/更新时间以排序顺序维护HashMap。也许我需要用整数值和长指示时间戳将整数值更改为对象。

而问题是如何在Java中实现这些功能以实现高效的添加/删除/获取性能？或者我可以使用哪些库来获取按创建/更新时间排序的HashMap？

Answer 1

要按创建/更新时间进行排序，您需要有时间进行比较。这意味着当被创建/更新时，您的对象将必须知道。通过在创建对象时默认设置version字段并在更新对象时将其设置为new Date()，可以相对容易地完成此操作。

有您能立足自己（TreeSet和TreeMap，尤其是）谁落实对象本身（Comparable接口）或Comparator定义的顺序结构。如果您存储更新时保存日期的项目，则可以实施可帮助排序过程的比较器。

如果您仅限于使用LinkedList和HashMap，则必须使用例如Collections#Sort对列表进行排序。在HashMap的情况下，您必须对Entry Set进行排序，但由于无法对其进行修改，因此必须以这种方式生成新的已排序映射。

尽管如此，HashMap是一种与排序无关的结构，因此在遍历它时仍然会遇到一些问题。 A LinkedHashMap可以解决这个问题，但同样，这一切都取决于您的数据类型限制。

Answer 2

这是一个适合LinkedHashMap的情况，覆盖了removeEldestEntry()方法。这张地图的关键是IP地址，值将是(bytes, last_update)的一个元组。

首先，您需要使用“访问顺序”创建您的地图：这意味着任何对地图条目的访问都会将该条目移动到列表的末尾（MRU）。然后，在获得新记录时执行以下操作：

• 如果映射不包含IP的条目，请创建一个包含字节数的新条目。
• 如果map确实包含一个条目，请获取其中的字节数，并通过将新的字节添加到old来创建新条目。然后put()新的进入地图，取代旧的。

您的元组应自动设置时间字段为当前时间。但是，要理解的是，你并不真正关心时间，它只是一个用于从列表中删除项目的属性。

覆盖removeEldestEntry()，如果时间超出范围，则返回true。

虽然，老实说，我认为你会更好地使用基于尺寸的驱逐战略（限制你的地图数量固定）。基于时间的策略会让您遇到DDOS攻击，在这种情况下，您有大量条目一次进入，耗尽您的内存。

Answer 3

提供我的两分钱......我最近做了类似的事情（当时我不知道LinkedHashMap），我需要跟踪一些会话信息。

我最终使用了ConcurrentHashMap，因为一次可以激活多个用户会话，并且每30分钟运行一次清理以清除陈旧的会话数据。我的思考过程是，由于应用程序需要更快的性能来处理会话数据，因此我将会话ID保留为关键字。当我需要清除最旧的数据时，只需抓取数值列表并进行排序（假设该类实现了Comparable，或者您可以为其编写Comparator），因为这不是“经常”完成的。

希望有所帮助。

PS。我很好奇这与LinkedHashMap实施相比如何？