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

Question

我正在以以下格式处理数据元组: IP，字节数-服务，时间.我在IP上创建了一个HashMap来计算每个IP的字节数。然后，我意识到我需要删除一些最近使用最少的键值对来创造更多的空间。我想要创建一个时间约束，比方说1小时，并删除键值对，在这段时间内不采取任何行动。因此，我需要为每对节省更新时间。事实上，对于一个好的性能来说，按时间戳排序对似乎是合理的。

因此，我想要做的是根据键值对的创建或更新时间来维护一个排序列表。我需要明确地知道这些创建和更新时间。我想出了两个不同的想法，但现在完全确定了使用哪一个和如何使用。以下是我的两个想法：

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

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

Answer 1

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

我最后使用了一个ConcurrentHashMap，因为多个用户会话一次可以活动，并且每30分钟运行一次清理以清除陈旧的会话数据。我的想法是，由于应用程序需要更快的性能来处理会话数据，所以我将会话id作为关键。当我需要清除最古老的数据时，只需获取一个值和排序的列表(前提是该类实现了Comparable，或者您可以为其编写一个Comparator )，因为这不是“经常”完成的。

希望这能有所帮助。

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

Answer 2

在这种情况下，LinkedHashMap是适当的，它覆盖了removeEldestEntry()方法。这个映射的关键是IP地址，值将是(bytes, last_update)的一个元组。

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

• 如果map不包含IP的条目，则创建一个具有字节数的新条目。
• 如果map确实包含一个条目，那么从其中获取字节数，并通过将新字节添加到旧条目来创建一个新条目。然后将新条目put()到地图中，替换旧条目。

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

重写removeEldestEntry()，如果时间超出您的范围，则返回true。

不过，老实说，我认为你最好采用基于大小的驱逐策略(将地图限制在固定数量的条目上)。基于时间的策略会让您面临DDOS攻击，在这种情况下，您将有大量的条目同时出现，耗尽了您的内存。

Answer 3

要按创建/更新时间进行排序，您需要有时间进行比较。这意味着您的对象必须知道它是何时创建/更新的。这可以通过在创建对象时默认设置version字段并在对象更新时使用new Date()设置来实现。

您可以使用一些结构(特别是TreeSet和TreeMap )来实现由对象本身定义的顺序(Comparable接口)或Comparator。如果存储在创建ir更新时保存日期的项，则可以实现一个比较器，该比较器可以帮助排序过程。

如果仅限于LinkedList和HashMap，则必须使用Collections#Sort对列表进行排序。在HashMap的情况下，您必须对它的条目集进行排序，但是由于无法修改它，您必须以这种方式生成一个新的排序映射。

不过，HashMap是一个与排序无关的结构，所以在迭代它时仍然会遇到一些问题。LinkedHashMap可以解决这个问题，但同样地，这取决于您的数据类型限制。