Частичный поиск в HashMap

Мне нужно создать телефонную книгу. Он содержит имя и номер. Теперь, когда я набираю буквы, соответствующий список должен быть возвращен. В приведенном ниже примере, когда я печатаю H, список, содержащий Хармер, Харрис, Хокен, Хослер, должен быть возвращен. Когда тип Ha, тогда список, содержащий только Harmer, Harris, Hawken должен быть возвращен.

  Map<String, String> nameNum = new HashMap<String, String>();

  nameNum.put("Brown", "+1236389023");
  nameNum.put("Bob", "+1236389023");
  nameNum.put("Harmer", "+1236389023");
  nameNum.put("Harris", "+1236389023");
  nameNum.put("Hawken", "+1236389023");
  nameNum.put("Hosler", "+1236389023");

Любая идея, как это достичь? Заранее спасибо.

Ответы

Ответ 1

Да, HashMap не является подходящей структурой данных для этого. Как сказал Божо, Trie будет правильным.

С встроенными инструментами Java на самом деле можно использовать TreeMap (или любой SortedMap):

public <V> SortedMap<String, V> filterPrefix(SortedMap<String,V> baseMap, String prefix) {
    if(prefix.length() > 0) {
        char nextLetter = prefix.charAt(prefix.length() -1) + 1;
        String end = prefix.substring(0, prefix.length()-1) + nextLetter;
        return baseMap.subMap(prefix, end);
    }
    return baseMap;
}

Выход будет даже отсортирован по ключу.

Вот пример использования:

SortedMap<String, String> nameNum = new TreeMap<String, String>();
// put your phone numbers

String prefix = ...;
for(Map.Entry<String,String> entry : filterPrefix(nameNum, prefix).entrySet()) {
    System.out.println(entry);
}

Если вы хотите, чтобы ваш префиксный фильтр не зависел от различий в регистре, используйте подходящий компаратор для вашей карты (например, Collator с подходящей настройкой силы или String.CASE_INSENSITIVE_ORDER).

Ответ 2

Это вызывает структуру данных Trie. См. этот вопрос для реализации Java. Я использовал этот.

Ответ 3

Поместите все это в MultiMap (или просто сохраните List как значение в вашем HashMap). Для "Брауна" сохраните:

"B"->["Brown"]
"BR"->["Brown"]
"BRO"->["Brown"]

Если вы позже добавите "Bradley":

"B"->["Brown", "Bradley"]
"BR"->["Brown", "Bradley"]
"BRO"->["Brown"]
"BRA"->["Bradley"]

и т.д...

то есть еще одна карта, чтобы нанести на карту "Браун" или "Брэдли" на номер телефона.

Ответ 4

Использовать guava Multimap облегчит ваше решение.

Ключ - это первая буква имени, значение - Collection, содержащее все пары имя-телефон, имя которого начинается с ключа (первая буква).

Пример:

    public void test(){
      //firstLetter -> list of name-phone pair
      Multimap<String, Pair> mMap =  ArrayListMultimap.create();

      put(mMap, "Brown",  "+1236389023");
      put(mMap, "Bob",    "+1236389023");
      put(mMap, "Harmer", "+1236389023");
      put(mMap, "Harris", "+1236389023");
      put(mMap, "Hawken", "+1236389023");
      put(mMap, "Hosler", "+1236389023");

      //Test
      System.out.println(mMap.get("H"));
   }

   void put(Multimap<String, Pair> mMap, String name, String phone){
      mMap.put(name.substring(0,1), new Pair(name, phone));
   }

   public static class Pair{
      String name;
      String phone;

      public Pair(String name, String phone) {
         this.name = name;
         this.phone = phone;
      }

      @Override
      public String toString() {
         return "Pair [name="+name+", phone="+phone+"]";
      }

}