2

この質問は、Adobe とのインタビューで私に投げかけられました。ハッシュマップは使えると答えましたが、彼は満足していませんでした。

ファイル 1

< tag1 >  
  < subtag1 >  
    < subsubtag1 >  
    </subsubtag1 >  
  < /subtag1 >  
< /tag1 >  
< tag2 >  
< /tag2 >

n個のそのようなファイル (つまり、XML ファイル) をメモリに保存する必要があります。次の操作を効率的に実行する目的で、これらのファイルをメモリに格納するために使用する Java データ構造の実装を記述します。

  1. 特定のファイル内の特定のタグにアクセスします。
  2. タグが存在するすべてのファイル内の特定のタグにアクセスします。

ノート：

  1. 何百万ものファイルが保存されています
  2. 各ファイルには数百万のタグが含まれており、各タグには数百万のサブタグが含まれている場合があります
4

3 に答える 3

0

について考えますTreeSet。

アクセス時間と取得時間は非常に高速であるため、すぐに見つけなければならない大量の並べ替えられた情報を格納する場合、TreeSet は優れた選択肢となります。

そんな感じ：

public class Storage{

  private String mTagName;
  private String mAttribute;
  private TreeSet<Storage> mTree; 
}

TreeSetそれ自体を含むクラス。再帰に適しています。

于 2013-09-21T20:06:16.107 に答える
0

HashMap の使用が問題だったとは思いません (下部に説明があります)。あなたのXMLに私が行くよりも属性が含まれていないと仮定するとHashMap<String, Element>（TreeMapも機能します）、StringはXMLタグであり、

class Element {
    Set<Files /* or something that represents them */> filesContainingTag;
    Map<String, Element> subTags;
}

そうすれば、指定された「タグ パス」を含むファイルがわかり、単一のファイルを取得できます。特定のファイルのタグにアクセスするには、この構造をタグで調べて、このファイルが にあるかどうかを確認しますfilesContainingTag。または、これらのファイルを何らかの方法で (たとえば、パスで) 識別する場合は、set の代わりに Map を使用します。

Tree* 構造の代わりに Hash* を使用する理由 前述のように - Tree* は、反復でソート順が必要な場合に適しています。他のほとんどの場合、Hash* の方が高速で使いやすいです (コンパレーターよりもハッシュ関数を実装する方が簡単です)。Hash* を使用したくない唯一のケースは、悪意のある入力が予想される場合です。使用しているハッシュ関数を誰かが知っていて、衝突に満ちたデータを提供する場合です。

于 2013-09-21T20:17:36.410 に答える