Поиск по коллекциям в Java

Question

У меня есть файл свойств java, содержащий пару ключ / значение названий стран и кодов. Я загружу содержимое этого файла в коллекцию, такую ​​как List или HashMap.

Затем я хочу, чтобы пользователи могли искать страну, например, если они введут «Aus» в текстовое поле и нажмут кнопку «Отправить», тогда я хочу выполнить поиск в моей коллекции, содержащей пару ключ / значение. кодов / названий стран (например, AUS => Австралия) и верните те страны, которые соответствуют.

Есть ли более эффективный способ сделать это, кроме циклического перебора элементов коллекции и использования charAt()?

Answer 1

Если важна производительность, вы можете использовать TreeSet или TreeMap для хранения названий стран, и для определения стран, начинающихся с данной строки, можно использовать следующее.

NavigableMap<String, String> countries = new TreeMap<String, String>();
countries.put("australia", "Australia");
...

String userText = ...
String tmp = userText.toLower();
List<String> hits = new ArrayList<String>();
Map.Entry<String, String> entry = countries.ceilingEntry(tmp);
while (entry != null && entry.getKey().startsWith(tmp)) {
    hits.add(entry.getValue());
    entry = map.higherEntry(entry.getKey());
}
// hits now contains all country names starting with the value of `userText`, 
// ignoring differences in letter case.

Это O(logN), где N - количество стран. В отличие от линейного поиска коллекции составляет O(N)

Answer 2

Цикл с String.contains () - это путь, если вы не хотите двигаться в какой-нибудь тяжелой артиллерии, такой как Lucene .

Answer 3

Если не индексировать коллекцию через что-то вроде Lucene , то вам придется вручную проверять, просматривая все элементы. Вы можете использовать startsWith вместо циклического перебора строки:

String userText = ...
for (Map.Entry<String, String> entry : map) {
    boolean entryMatches = entry.getKey().startsWith(userText);
    ...

Или используйте регулярные выражения:

Pattern pattern = Pattern.compile(userText);

for (Map.Entry<String, String> entry : map) {
    boolean entryMatches = pattern.matcher(entry.getKey()).find();
    ...

Answer 4

Поскольку список достаточно мал для загрузки в память, отсортируйте его, а затем выполните бинарный поиск, используя статический метод java.util.Collections.binarySearch (). Это возвращает индекс и работает независимо от того, находится ли точная строка в списке или нет (хотя, если это не так, она возвращает отрицательное число, поэтому обязательно проверьте это). Затем, начиная с этого индекса, просто итеративно вперед, чтобы найти все строки с этим префиксом. Как хороший побочный эффект, полученный результат будет в алфавитном порядке.

Чтобы сделать все это без учета регистра, не забудьте преобразовать в нижний регистр при загрузке списка и, конечно, преобразуйте префикс в нижний регистр перед поиском.