Búsqueda parcial en HashMap

Question

Necesito crear cosas de la guía telefónica. Contiene el número de nombre &. Ahora cuando escribo letras, se debe devolver la lista de coincidencias. Para el ejemplo que se muestra a continuación, cuando escribo H, se debe devolver una lista que contenga Harmer, Harris, Hawken, Hosler. Cuando escriba Ha, entonces la lista que contiene solo Harmer, Harris, Hawken debe ser devuelta.

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"); 

¿Alguna idea de cómo lograrlo? Gracias de antemano.

Answer 1

Sí, un HashMap no es la estructura de datos correcta para esto. Como dijo Bozho, un Trie sería el correcto.

Con las herramientas de a bordo de Java, un TreeMap (o cualquier SortedMap, en realidad) podrían utilizarse:

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; 
} 

La salida incluso sería solucionado por la clave.

Aquí un ejemplo de uso:

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); 
} 

Si desea que su filtro de prefijo que no sea en función de las diferencias de casos, utilizar un comparador adecuado para su mapa (como un Collator con un ajuste de resistencia adecuada, o String.CASE_INSENSITIVE_ORDER) .

Answer 2

Esto requiere una estructura de datos Trie. Ver this question para implementaciones de java. Usé this one.

Answer 3

Ponlo todo en un MultiMap (o simplemente almacena una lista como el valor en tu HashMap). Por "Brown", de la tienda:

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

Si posteriormente añade "Bradley":

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

etc ...

luego tener otro mapa a otro "Brown" o "Bradley" al número de teléfono.

Answer 4

Utilizar guava Multimap facilitará su solución.

La clave es la primera letra del nombre, el valor es un Collection que contiene todos los pares de nombre-teléfono cuyo nombre se inicia con la tecla (primera letra).

Ejemplo:

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+"]"; 
     } 

}