我可以使用哪个Java集合类？

Question

我需要存储一组数据结构，这些数据结构由时间段（开始时间，结束时间）和此期间计数器组成，该计数器保存了某些复杂的计算结果。该数据结构的简化定义如下：

public class CounterBag {
    private Period period;   // collection key
    private Counter counter;
    // accessors
    // ...
}

Period 就像这样简单：

public class Period {
    public DateTime start;
    public DateTime end;
    // accessors
    // ...
}

我需要一个集合来存储由不同“Periods”定义的“CounterBag”对象。 该集合需要提供有效的按“long timeInMillis”进行查找（这是关键！），因此“HashMap”并不是真正的选择，因为我不想覆盖“CounterBag”的“equals”和“hashcode”（我需要它们两个）。 集合需要按“Period”排序（按结束日期）。 “Periods”具有灵活的持续时间，对于执行查找的部分未知。

我想知道是否有Java标准API或某些开源库中的现成集合可以帮助我解决这个问题？一种按日期排序的排序集合或排序映射，使得实现按日期进行高效查找成为可能。 按日期查找将返回一个“CounterBag”，其中包含日期所在的“Period”。感谢您的建议。

- aviad

Answer 1

你可以使用TreeMap作为一个有序集合（这样查找效率高）。

如果你的时间段有规律的间隔（这是最简单的形式），你不需要这样的集合。你只需要为每个时间段设置一个计数器，比如一个int[]数组。

- Peter Lawrey

---

谢谢，问题在于“Period”的开始和结束是灵活的，不为执行查找的部分所知，因此查找将通过日期而不是期间进行。 - aviad

Answer 2

我想延伸@Peter Lawrey的答案，使用具有自定义比较器的TreeMap来处理您的CounterBag。

这个比较器将确保返回在范围内的CounterBag。

查找效率取决于您比较器的实现。

- mprabhat

Answer 3

由于在足够的持续时间内，任何开始时间都有可能符合条件，因此按开始时间排序的简单ArrayList将是一种有效的方法，特别是如果允许重叠（产生多个结果）。您只需要迭代到第一个开始时间>请求的timeInMillis的记录即可。

- phatfingers

Answer 4

如果时间段不重叠，我建议使用 TreeMap<Period, CounterBag>。当您需要根据毫秒数获取 CounterBag 时，可以使用以下代码：

// Initialize map
Map<Period, CounterBag> map = new TreeMap<Period, CounterBag>();
map.put(...);

// Prepare "query"
long timeInMillis = ...;
Period fakePeriod = new Period(new Date(timeInMillis), new Date(timeInMillis));

// Get bag for given time.
CounterBag bag = map.get(fakePeriod);

在这种情况下，要么 Period 必须实现 Comparable 接口，要么您可以将自己的比较器传递给树。如果两个时间段重叠（在我们的情况下，如果某个真实时间段包含了我们的虚拟时间段，其开始和结束时间都等于 timeInMillis），则它们的比较应该返回 0。

- Mikita Belahlazau

Answer 5

我建议使用 TreeMap<Long, CounterBag>。您可以使用NavigableMap接口进行访问：

NavigableMap<Long, CounterBag> map = new TreeMap<Long, CounterBag>();
map.put(bag.period.end.toMillis(), bag); // Get end DateTime as a Long


long lookupLong = 10000L; // or whatever

/*
 * Retrieves the greatest Bag whose Period's end is
 * less than or equal to the Long
 */
CounterBag newBag = map.floorEntry(lookupLong).getValue();

- artbristol