Доступный для поиска список объектов в Java
Я хочу создать большое (~300 000 записей) Список сам определенные объекты класса Drug. Каждый Препарат имеет идентификатор, и я хочу смочь искать Наркотики в логарифмическое время с помощью того идентификатора. Какой Список я должен использовать? Как я объявляю, что это должно быть доступно для поиска с помощью идентификатора?
7 ответов
Различные реализации интерфейса Map должны делать то, что вы хотите.
Просто не забудьте переопределить метод hashCode () вашего класса Drug, если вы планируете использовать HashMap.
Разве вы не использовали бы TreeMap вместо List, используя идентификатор в качестве ключа?
Я знаю, что я довольно много говорю об этом утверждении, но, как все говорили, разве это не совсем так для Map?
Если для вас важен поиск по ключу, возможно, вам нужно использовать карту, а не список. Из Java Collections Trail :
Три универсальных реализации Map - это HashMap, TreeMap и LinkedHashMap. Если вам нужны операции SortedMap или упорядоченная по ключу итерация представления коллекции, используйте TreeMap; если вам нужна максимальная скорость и не заботится о порядке итераций, используйте HashMap; если вам нужна производительность, близкая к HashMap , и итерация порядка размещения , используйте LinkedHashMap.
Из-за большого количества записей вы можете рассмотреть возможность использования базы данных вместо того, чтобы хранить все в памяти.
Если вы все еще хотите сохранить это в памяти, вы можете взглянуть на b-деревья.
public class Drug implements Comparable<Drug> {
public int compareTo(Drug o) {
return this.id.compareTo(o.getId());
}
}
Затем в вашем списке вы можете использовать binarySearch
List<Drug> drugList; <--- List of all drugs
Drug drugToSearchFor; <---- The drug that you want to search for, containing the id
// Sort before search
Collections.sort(drugList);
int index = Collections.binarySearch(drugList, drugToSearchFor);
if (index >= 0) {
return true;
} else {
return false;
}
Вы можете использовать любой список, и пока он отсортирован, вы можете использовать бинарный поиск. Но я бы использовал Map, которая выполняет поиск за O(1).