6

名前のリストがあり、各人が 1 つの電話番号を持つシステムを実装しています。名前から電話番号を調べたり、電話番号から名前を調べたりできる必要があります。

名前から電話番号へのハッシュテーブルと、電話番号から名前へのハッシュテーブルの 2 つのハッシュテーブルを使用することで、これを実行できることがわかっています。その後、O(1) 時間でどちらの方向にも上を向くことができます。ただし、これはあまりにも多くのデータを保存しているようです。すべての名前と電話番号が 2 回保存されます。

これをより効率的に行う方法はありますか？名前と電話番号を保存するには、どのデータ構造を使用すればよいですか?

関連する場合は、Javaでコーディングしています。

どうもありがとう！

4

3 に答える 3

8

Javaは、すぐに使用できる双方向ハッシュテーブルを提供していません。2つのハッシュテーブルに依存するソリューションは、サードパーティのライブラリ（2つのハッシュテーブルを非表示にする）を使用したり、の大部分を再実装したりしない限り、最高のソリューションですHashMap<K,V>。

そうすれば、O（1）時間でどちらの方向にも見上げることができます。しかし、これは私があまりにも多くのデータを保存しているようです-すべての名前とすべての電話番号が2回保存されています。

必ずしもそうとは限りません。電話番号を表す同じオブジェクトを使用できます。その場合、電話番号には1つのオブジェクトがあり、2つのハッシュテーブルから2つの参照が保存されます。

于 2012-11-09T19:48:38.637 に答える
5

HashBiMap基本的に2つHashMapのが舞台裏でリンクされているGuavaを使用することを検討してください。BiMapインターフェイスとその関連記事も参照してください。

于 2012-11-09T19:48:14.047 に答える
1
  1. オブジェクト自体は一度だけ保存され、両方のマップには保存されないことに注意してください。必要な参照の数は2倍だけなので、それほど悪くはないかもしれません。
  2. その機能を提供するGauvaBiMap（およびそのインターフェイスHashBiMap）を使用できます
于 2012-11-09T19:48:24.727 に答える