Какую коллекцию 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 
    // ... 
} 

мне нужно иметь набор, который содержит объекты, определенные CounterBag отчетливым Periods. Коллекция должна обеспечивать эффективный поиск (здесь подвох!) По long timeInMillis, так HashMap это не вариант, так как я не хочу, чтобы перезаписать equals и hashcode из CounterBag (мне нужно их обоих). Сбор необходимо отсортировать по Period (по дате окончания). Period s имеют гибкую продолжительность, которая не известна той части, которая будет выполнять поиск.

Интересно, есть ли коллекция из коробки в стандартном API Java или в какой-то библиотеке с открытым исходным кодом, которая может помочь мне в ее решении? Какой-то сортированный набор или отсортированная карта, которая позволяет реализовать эффективный поиск по дате. Поиск по дате вернет CounterBag с Period.

Оцените свои предложения.

Answer 1

Вы можете использовать TreeMap в качестве отсортированных коллекций (что делает поиск эффективный)

Если периоды имеют регулярные интервалы (это самая простая форма) вам не нужна такая коллекция. У вас может быть только счетчик для каждого интервала. например a int[]

Answer 2

Я бы просто сказал @Peter Lawrey ответ, используйте TreeMap с помощью специального компаратора для вашего CounterBag.

Этот компаратор будет обеспечивать возврат CounterBag в пределах диапазона.

Эффективность поиска зависит от реализации компаратора.

Answer 3

Если периоды не перекрываются, я бы предложил использовать 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 или передать свой собственный компаратор к дереву. Сравнение двух периодов должно возвращать 0, если они перекрываются (в нашем случае, если некоторый реальный период включает наш поддельный период с начальным и конечным временем, равным timeInMillis).

Answer 4

Предлагаю 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(); 

Answer 5

Потому что потенциально любое время старта может претендовать, учитывая достаточную продолжительность, простой ArrayList отсортирован по времени начала был бы эффективный подход, особенно если перекрывается разрешено (дающее множественным Результаты). Вы будете перебирать только до первой записи, где время начала> запрошено timeInMillis.