1

我正在处理以下格式的数据元组：[IP, number-of-bytes-served, time]。我在 IP 上创建了一个 HashMap 来计算为每个 IP 提供的字节数。然后，我意识到我需要删除一些最近最少使用的键值对来创建更多空间。我想创建一个时间限制，比如说 1 小时，然后删除在该期间没有任何操作的键值对。所以我需要为每对保存更新时间。事实上，为了获得良好的性能，让这些对按时间戳排序似乎是合理的。

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

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

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

4

3 回答 3

2

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

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

希望有帮助。

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

于 2013-03-11T19:39:33.833 回答
1

这是LinkedHashMap适合的情况，覆盖该removeEldestEntry()方法。该映射的键是 IP 地址，值是 的元组(bytes, last_update)。

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

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

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

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

虽然，老实说，我认为您最好使用基于大小的驱逐策略（将您的地图限制为固定数量的条目）。基于时间的策略会使您面临 DDOS 攻击，在这种情况下，您会同时收到大量条目，从而耗尽您的内存。

于 2013-03-11T19:18:20.023 回答
0

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

您可以将自己建立在一些结构中（TreeSet尤其TreeMap是），它们实现了由对象本身（Comparable接口）或Comparator. 如果您存储的项目保存了创建日期和更新日期，您可以实现一个比较器来帮助排序过程。

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

尽管如此，aHashMap是一个与排序无关的结构，因此在迭代它时仍然会遇到一些问题。ALinkedHashMap可以解决这个问题，但同样，这完全取决于您的数据类型限制。

于 2013-03-11T17:29:05.130 回答