電話帳のデータ構造を設計する

Question

名前と電話番号を格納するための電話帳のデータ構造を設計する。

Map<String,int> 
Map<int,String> 

に従いますが、それはmemory.Canの誰もが、他の解決策を提案する二回必要と

我々は2つのハッシュマップを使用することができますか？

Answer 1

もう1つの可能性は、文字列をtrieに格納し、各文字列の末尾を示す '$'記号を付けることです。各ステップに二重にリンクされたポインタを使用し、それぞれの '$'（終わりの名前）からその番号（配列またはリスト内）までの二重リンクポインタを保持します。

今、あなたが名前から電話を取得したいとき：あなたは携帯電話から名前を取得したいとき

find the '$' indicating the end of the word for this string. 
it is connected to a number in a list - that is your number. 

：

find the number, it is connected to a '$' sign. 
follow the up-links all the way to the root, this will get you the name (reversed). 
reverse it and you are done. 

も、私がコメントで言ったように（あなたの文字列がかなり大きいと仮定し、マップが実際の文字列ではなく文字列へのポインタ/参照を保持していると仮定すると、必要な記憶領域は2倍にならず、はるかに優れていると仮定できます。

Answer 2

2領域マップ（または「双方向マップ」）は、その キーのものと同様 その値の一意性を維持 マップです。この制約により、バイマーク は、 であり、このバイマップと同じ のエントリを含むが、 のキーと値を逆にした別のバイマップである「逆ビュー」をサポートすることができます。

http://guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/common/collect/BiMap.html

BiMap<String, Integer> biMap = HashBiMap.create(); 

biMap.put("Mike", 123); 
biMap.put("John", 456); 
biMap.put("Steven", 789); 

BiMap<Integer, String> invertedBiMap = biMap.inverse(); 

編集：Multimaps

Multimap<String, String> multimap = HashMultimap.create(); 
multimap.put("John", "111111111"); 
multimap.put("John", "222222222"); 
multimap.put("Mike", "333333333"); 

System.out.println(multimap.get("John")); //[222222222, 111111111] 

for(Map.Entry<String, String> entry : multimap.entries()){ 
    if(entry.getValue().equals("222222222")){ 
     System.out.println(entry.getKey()); //John 
    } 
} 
//or 

Multimap<String, String> inverted = HashMultimap.create(); 
Multimaps.invertFrom(multimap, inverted); 
System.out.println(inverted.get("222222222")); //[John] 

Answer 3

一人が複数の番号を持つことができ、1つの数が一人以上の家族の（メンバーに属することができます）。ニック氏によると、一般的な電話番号は数字以外の文字を持つことができます。すべての文字列はMap<String,int>の代わりにMap<String,List<String>>を使用しているか、または冗長性を避けるために文字列へのポインタ（C++の用語）のみを使用している可能性があります（Map<String*,List<String*>>）。

Answer 4

電話ディレクトリを実装するためにバイナリ検索ツリーを使用するのが最良の方法です。携帯電話の連絡先リストの実際の実装について考えてみましょう。アルファベット順にソートされています。マップテンプレートを使用する場合、ソートされたリストは取得されません。マップの要素をソートすることはできません。それは効果的ではありません。

これを行う唯一の方法は、バイナリツリー方法です。新しいエントリを追加している間は、順序通りに挿入されます。だから、それ以上のソートは必要ありません。すでに注文されています。バイナリツリーの場合は、left_tree <ルートとルート< right_treeを覚えておいてください。