Как я могу эффективно получить все строки из HashMap, которые соответствуют регулярному выражению / префиксу [Java]

Question

У меня есть HashMap, в котором есть куча строковых данных, я хочу, чтобы люди могли искать строки, вводя строку поиска, и HashMap должен выдавать все данные, соответствующие этой строке поиска.

например:

---

Строка поиска: Do

Результаты:

Собака

Додо

Осел

Доритос

---

Каким образом я могу достичь этого, сохранив при этом сложность времени?

Answer 1

TreeMap - это NavigableMap, который представляет собой SortedMap, позволяющий найти запись с первым ключом, меньшим или равным заданному значению, следующую запись с ключом после заданного значения или даже подкарту со всеми записи между начальным и конечным значением.

Если вы ищете все записи, начинающиеся с «Do», первая запись, которая не является частью этого набора, будет заканчиваться «Dp» или некоторым более поздним значением. Как правило, первый префикс, который не соответствует, всегда можно найти, увеличивая последний символ префикса, который вы ищете. Вот как вы можете использовать это для решения вашей проблемы:

public void search(NavigableMap<String, String> navmap, String searchTerm) {
    String stopTerm = incrementLastChar(searchTerm);
    System.out.format("Searching range [%s, %s)%n", searchTerm, stopTerm);
    SortedMap<String, String> range = navmap.subMap(searchTerm, stopTerm);
    for (Map.Entry<String, String> entry : range.entrySet()) {
        System.out.println(entry.getKey());
    }
}

public String incrementLastChar(String term) {
    char[] chars = term.toCharArray();
    chars[chars.length - 1] += 1;
    return new String(chars);
}

Поместите данные, которые вы хотите найти, в TreeMap. Я не знаю, каковы ваши значения, поэтому я просто сделал это TreeMap от String до String. Передайте его как NavigableMap вместе с префиксом, который вы хотите найти. Я создал вспомогательный метод для создания термина остановки. Это самый низкий префикс, который не находится в диапазоне, который вы хотите найти. Метод поиска распечатывает диапазон, который он ищет, и ключи всех найденных предметов.