带日期范围的HashMap

我需要找到一些值非常快速基于多键。关键是由： < Int userId, String measureName, Date startDate, Date endDate > 和值是一个双。带日期范围的HashMap

问题是我不得不要求表示一天的值，而不是日期范围。因此，如果我要求userId，measureName和一天，则数据结构必须以startDate和endDate（日期范围之间没有重叠）之间的值作为回答。

我不明白哪一个是更好的数据结构来实现这一点。 HashMap类？ TreeMap的？ MultiKeyMap？ RangeMap？帮帮我！ :)

2013-03-12 user2088834

您对每个用户/度量组合可能有多少个条目？ – 2013-03-12 21:54:41

如果你不考虑智能计量/时间系列。寻找其他解决方案类似于时间序列 – 2013-03-12 21:56:28

不算太多，比方说100，问题在于问了很多时间。（对于经常被调用的函数，80k次） – user2088834 2013-03-12 21:56:50

我认为你应该使用TreeMap和类似的方法： http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#floorEntry(K) http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#higherEntry(K) 但相比之下功能只能使用一个日期 - 的startDate或结束日期。由于这些范围不重叠，所以这不应该成为问题，并且可以使用TreeMap提及的方法。

例如：如果你决定在比较endDate（以及除了其他日期等领域）使用比你应该使用方法floorEntry

来源

2013-03-12 21:58:01 kkonrad

虽然没有重叠，但可能有日期不在开始/结束日期范围内... – matts 2013-03-12 22:02:19

...但是您应该只需比较结束日期一次。 – jahroy 2013-03-12 22:03:22

@jahroy哦，我明白了;我误解了，并认为这个建议是直接使用日期作为映射关键字。 – matts 2013-03-12 22:07:13

TreeMap的用户键对象将是最好的。你会碰到这样的：

... 
TreeMap<MyMultiKey,Double> map = ... 

class MyMultiKey implements Comparable<MyMultiKey>{ 
... 
}

假设MyMultiKey的compareTo法实施正确排序您的多按键，可以在每次你想使用map.floorKey(MyMultiKey m)来搜索特定日期时间创建一个新的MyMultiKey实例和map.higherKey(MyMultiKey m)，以确保您找到一个开始和结束时间包含您在新密钥实例中指定日期的密钥。

来源

2013-03-12 22:03:21 CodeBlind

我推荐一些用户/测量部分密钥的地图。该值将是一个元组的排序数组（日期范围，floatval）。在此数组中，您可以对包含当天的日期范围执行二分搜索。

来源

2013-03-12 22:15:10 Ingo

Map和订购List的组合怎么样？该变换图具有的userId和measureName复合键，则该值的日期范围和双value的排序的列表：

Map<Key,List<Entry>> data = new HashMap<>(); 
List<Entry> entries = data.get(new Key(userId, measureName)); 
int i = Collections.binarySearch(entries, new Entry(searchDate,searchDate, 0.0)); 
double value = i < 0 ? 0.0 : entries.get(i).value;

Key具有使用其成员userId和measureName实施hashCode()和equals()。 Entry必须实现Comparable<Entry>其中compareTo()如果一个范围是另一个范围的一部分，则返回0（如果startDate比较> = 0且endDate比较为< = 0，则startDate比较为< = 0且endDate比较> = 0或0）否则比较startDate +（endDate-startDate）/ 2（范围的中间），无论双重value。

如果您主要阅读并且不修改此结构，它应该很快。如果使用太多，比较将被编译为本地。如果该功能仅适用于单个用户并且只能测量，则只能使用排序列表，如果只有单个用户，则可以创建Map<UserId<Map<MeasureName,List<Entry>>>>类似结构。

先尝试一个简单的解决方案，然后进行测量，只在需要时进行性能优化。

来源

2013-03-12 22:49:54

带日期范围的HashMap

回答

相关问题