Поиск через коллекции в Java

Question

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

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

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

Answer 1

Looping с String.contains() является способ, если вы не хотите, чтобы двигаться в некоторых тяжелых артиллерия, как Lucene.

Answer 2

Короткая индексация коллекции с помощью чего-то вроде 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 3

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

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

Answer 4

Если производительность важна, вы можете использовать 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)