1

それぞれに識別番号が付いnたオブジェクトがあります。私はそれらをソートしていませんが、インデックスの範囲を(0, n-1)使用してそれらを識別しています。できるだけ早くアクセスしたい。ArrayList が最適なオプションであると思います。次のようにしてn、ArrayList の位置に識別子を持つオブジェクトをインデックス付きで追加しますn。

list.add(identifier, object);

問題は、オブジェクトを追加するときに、並べ替えられていないオブジェクトを追加IndexOutOfBounds Exceptionしているためsize()、以前の位置も満たされることはわかっていますが、 が小さいことです。

別のオプションは HashMap を使用することですが、これはパフォーマンスを低下させると思います。

上記の動作を持つコレクションを知っていますか?

4

4 に答える 4

2

上記の動作を持つコレクションを知っていますか?

普通の古い Java 配列が必要なようです。コレクションとして必要な場合は、「Arrays.asList(...)」を使用してListラッパーを作成します。

配列/コレクションから要素を追加または削除する必要がある場合、これは機能しませんが、問題の説明からは必要ないように思えます。

要素を追加/削除する必要がある場合(特定の位置で要素を更新するために使用するのとは異なりset、Peter Lawrey のアプローチが最適です。

対照的に、 aHashMap<Integer, Object>は高価な代替手段になります。大まかな見積もりでは、「インデックス作成」操作は少なくとも 10 倍遅くなり、データ構造は同等の配列またはArrayList型と比較して 10 倍のスペースを必要とするでしょう。ハッシュ テーブル ベースのソリューションは、配列が大きくてまばらな場合にのみ (パフォーマンスの観点から) 実行可能な代替手段となります。

于 2012-10-15T08:27:28.933 に答える
1

インデックスの順序が狂うことがあります。これには、後で入力される可能性のあるダミー エントリを追加する必要があります。

int indexToAdd = ...
E elementToAdd = ...

while(list.size() <= indexToAdd) list.add(null);
list.set(indexToAdd, elementToAdd);

これにより、リストの現在の末尾を超えてエントリを追加できます。

List.add(int, E)とList.set(int, E)の両方の Javadoc は次のように述べています。

IndexOutOfBoundsException - インデックスが範囲外の場合 (index < 0 || index > size())

末尾を超えてエントリを追加しようとすると

List list = new ArrayList();
list.add(1, 1);

あなたが得る

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
    at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:612)
    at java.util.ArrayList.add(ArrayList.java:426)
    at Main.main(Main.java:28)
于 2012-10-15T08:20:24.513 に答える
0

少なくとも 2 つの良い選択肢があると思います。

1 つ目は、適切な長さに初期化されたストレートな Java 配列を使用し、次の構文でオブジェクトを追加する方法です。

    theArray[i] = object;

2 つ目は、HashMap を使用し、次の構文でオブジェクトを追加することです。

    theMap.put(i, object);

あなたが心配しているパフォーマンスの問題はわかりませんが、範囲内の要素の追加、クリア (配列から) または削除 (HashMap から)、および特定のインデックス (またはキー、 HashMap) は両方の構造ですべて O(1) です。また、どちらも良くないと思われる場合は、ウィキペディアのデータ構造のリストを参照することをお勧めします。

于 2012-10-15T08:34:55.970 に答える
0

どれだけ高価になるかはわかりませんHashMap<Integer, T>。Integer.hashCode()非常に効率的ですが、アイテムの数が増えるにつれて、データを新しいより大きな配列にコピーすることだけが本当にコストのかかる操作になる可能性があります。ただし、 がわかっている場合は、通常の配列nを使用できます。

Map<Integer, T>別の方法として、ハッシュ コードではなくそれ自体を使用する独自のものを実装することもできますInteger。これを行う前に、配列が十分でないか、十分HashMapに効率的でないかを確認してください!

于 2012-10-15T08:23:44.403 に答える