6

以下のように、リアルデータベースに親と子のマッピングがあります。

relationship_id | parent_id | child_id
1               | 100009    | 600009
2               | 100009    | 600010
3               | 600010    | 100008

パフォーマンスを最適化するために、これらすべてのマッピングをメモリに保持したいと考えています。ここでは、子には複数の親があり、親には 2 つ以上の子があります。「グラフ」データ構造を使用する必要があると思います。

メモリへのデータの取り込みは、1 回限りのアクティビティです。私の懸念は、すべての子 (直接の子だけでなく) をリストするように依頼すると、できるだけ早くそれらを返す必要があることです。追加と削除はまれに発生します。どのデータ構造とアルゴリズムを使用すればよいですか?

検索時間を達成するためにMultiHashMapを試しましO(1)たが、冗長性が高くなります。

4

2 に答える 2

5

親子関係のグラフデータ構造を持っています。各GraphNodeは、子を1つだけ持つことができArrayListます。

次にHashMap、IDをGraphNodeにマップします。

無限ループを引き起こすサイクルを作成しないように（これが可能な場合）、何かを理解する必要があります。

于 2013-02-22T12:21:48.083 に答える
1

Node簡単に検索できるようにノード参照を格納するには、カスタム クラスとハッシュマップが必要です。

for each row in database
if parent node exists in map
  get it
else
  create it and add it

if child node exists in map
  get it
else
  create it and add it

set relationship between parent and child

ノードクラスは次のようになります。

public class Node {

  private int id;

  private List<Node> parents = new ArrayList<Node>();
  private List<Node> children = new ArrayList<Node>();

  //getters and setters

}
于 2013-02-22T12:24:12.677 に答える