ハッシュマップの部分検索

Question

私は電話帳のようなものを作成する必要があります。それは名前&の番号を含んでいます。文字を入力すると、リストが返されます。以下の例では、Hをタイプすると、Harmer、Harris、Hawken、Hoslerを含むリストが返されます。タイプが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"); 

どのように達成できますか？ ありがとうございます。

Answer 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のような）あなたのマップに適したコンパレータを使用しないようにしたい場合。

Answer 2

これは、Trieデータ構造を必要とします。 Javaの実装については、this questionを参照してください。私はthis oneを使用しました。

Answer 3

すべてをマルチマップに入れます（または、ListをHashMapの値として保存するだけです）。 "ブラウン" の場合、店舗：

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

後で "ブラッドリー" を追加した場合：

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

等...

その後、 "ブラウン" や "ブラッドリー" をマッピングするための別のマップを持っています電話番号に。

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

}