Tìm kiếm một phần trong HashMap

Question

Tôi cần tạo loại sách điện thoại. Nó chứa tên & số. Bây giờ khi tôi nhập các chữ cái phù hợp với danh sách nên được trả lại. Ví dụ dưới đây, khi tôi gõ H, một danh sách chứa Harmer, Harris, Hawken, Hosler nên được trả về. Khi gõ Ha thì danh sách chỉ chứa Harmer, Harris, Hawken nên được trả về.

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

Bất kỳ ý tưởng nào đạt được điều đó? Cảm ơn trước.

Answer 1

Vâng, một HashMap không phải là cấu trúc dữ liệu phù hợp cho việc này. Như Bozho đã nói, một Trie sẽ là một trong những quyền.

Với công cụ on-board Java, một TreeMap (hoặc bất kỳ SortedMap, trên thực tế) có thể được sử dụng:

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

Kết quả thậm chí sẽ được sắp xếp theo chủ chốt.

Dưới đây là một ví dụ sử dụng:

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

Nếu bạn muốn lọc prefix của bạn để không phải phụ thuộc vào trường hợp khác nhau, sử dụng một sánh phù hợp cho bản đồ của bạn (như một Collator với một thiết lập sức mạnh phù hợp, hoặc String.CASE_INSENSITIVE_ORDER) .

Answer 2

Điều này yêu cầu cấu trúc dữ liệu Trie. Xem this question để triển khai java. Tôi đã sử dụng this one.

Answer 3

Đặt tất cả trong một MultiMap (hoặc chỉ lưu trữ Danh sách dưới dạng giá trị trong HashMap của bạn). Đối với "Nâu", lưu trữ:

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

Nếu sau đó bạn thêm "Bradley":

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

vv ...

sau đó có một bản đồ để lập bản đồ "Nâu" hoặc "Bradley" đến số điện thoại.

Answer 4

Sử dụng guava Multimap sẽ giảm bớt giải pháp của bạn.

Khóa là chữ cái đầu tiên của tên, giá trị là Collection chứa tất cả các cặp tên-điện thoại bắt đầu bằng tên (ký tự đầu tiên).

Ví dụ:

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

}