java - 在(散列)映射中搜索上一个最接近的日期/字符串

Question

我遇到了一个问题，我可能需要重新设计我的数据结构。

现在我有很多按时间顺序排列的信息，并将其保存在 HashMap 中，键是日期，它也是new Info()的成员。

hashMap.put(date.toString(), new Info(date, ...))

日期间隔为 5 分钟

2012-02-15 22:45:00.0
2012-02-15 22:50:00.0
2012-02-15 22:55:00.0
2012-02-15 23:00:00.0
...
2012-02-25 12:10:00.0
2012-02-25 12:15:00.0

到目前为止，通过获取 key 很容易获取信息，并且速度是恒定时间
hashMap.get(date.toString())

到目前为止，当我从那里的 HashMap 中获取日期时，一切都很好。但现在信息时间顺序可能存在差距。在下面的示例中，缺少 2012-02-15 22:50:00.0，因此在搜索该日期时我会得到 NPE。
在这种情况下，我必须找到上一个最接近的时间。

2012-02-15 22:45:00.0
2012-02-15 22:55:00.0
2012-02-15 23:00:00.0 ...

if (hashMap.get(date.toString()) != null) {
   // found it
} else {
   return previousTime(date.toString())
}

我可以创建一个 LinkedHashMap，而 previousTime 可以只是 iterate over the collection直到我找到最近的日期。但最坏的情况是 O(n) 复杂度。对于此类任务是否有更好的数据结构或者仅使用 LinkedHashMap？像 here 这样的 SortedMap ？但最初的 put 成本高昂，并且会占用更多内存。

Answer 1

对我来说这听起来像 NavigableMap例如 TreeMap 正是您正在寻找的。虽然您确实不应该使用日期的 String 形式作为键...但请使用 Date 本身。