HashMap中的部分搜索

我需要創建電話簿類的東西。它包含名稱&號碼。現在當我輸入字母匹配列表時應該返回。對於下面給出的例子，當我鍵入H時，應該返回包含Harmer，Harris，Hawken，Hosler的列表。當輸入哈然後列出只包含哈默，哈里斯，霍肯應歸還。HashMap中的部分搜索

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

任何想法如何實現它？在此先感謝。

來源

2011-07-15 Partha

你確定使用'HashMap'所有的東西是這樣一個好主意？我認爲不同的數據結構可能會更好。 –

你只在尋找第一個字母，還是在你輸入的時候刪除列表？例如，輸入「Ha」是否消除了「Hosler」？ –

是的，HashMap不是正確的數據結構。正如Bozho所說，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）。

來源

2011-07-15 21:31:06

+1正確的想法;考慮大寫/小寫問題以及 –

@PaŭloEbermann：爲什麼Trie，它是如何節省空間{http://stackoverflow.com/questions/8265476/trie-saves-space-but-how}？ –

也可以使用前綴+「\ uffff」作爲結尾。 – Tires

這需要一個Trie數據結構。有關java實現的信息，請參閱this question。我用this one。

來源

2011-07-15 21:20:40 Bozho

感謝Bozho你的鏈接很有用！但是，這個問題接近3年後纔得到解答。現在是否有更好的解決方案，您可能會注意到？ –

http://code.google.com/p/patricia-trie/我用那 – Bozho

把它全部放在一個MultiMap中（或者只是將List存儲爲你的HashMap中的值）。對於「布朗」，店：

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

如果以後添加「布拉德利」：

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

等等

則有另一種地圖繪製「布朗」或「布拉德利」到電話號碼。

來源

2011-07-15 21:27:06 dgrant

在這個數據結構中添加和刪除東西將會非常昂貴。 –

我同意。但我們甚至不知道他的「電話簿」有多大。我寧願先做簡單的事情，然後再進行優化。這似乎是最簡單的事情。 – dgrant

訪問將是O（1），而對於樹，它將是log（n）。如果你正在做一些類似自動完成的事情，這不是更重要嗎？數據集多久更新一次？如果獲得更頻繁的設置，誰在乎添加/刪除速度有多慢。在這裏添加和刪除甚至不是我認爲不好的壞東西。 – dgrant

-1

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

}

來源

2011-07-16 00:46:04

HashMap中的部分搜索

回答

相關問題