搜索前一个最近的日期/字符串在（散列）地图

Question

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

现在我有很多按时间顺序排列的信息，并将它保存在Hashmap中，其中的密钥是date，它也是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

到目前为止，它很容易被拿到钥匙和速度获取信息是恒定的时间
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？ SortedMap like here？但最初put将是昂贵的，它会占用更多的内存。

Answer 1

这听起来像我NavigableMap如TreeMap正是你在找什么。尽管您不应该使用日期的String格式作为您的密钥...使用Date本身。

Answer 2

但是最糟糕的情况是O（n）的复杂性

多大将这个n为？即使它是一百万，我也不认为这是一个问题。不止这可能是一个问题，但在你担心速度之前，我想你会首先耗尽内存。从找到问题日期的位置开始，每5分钟进行一次反向迭代。