Java Collectionsに関するお知らせ

翻訳By Long Luo
次の質問StackoverflowでJava collectionsについて最も多くの質問と議論をします.これらの問題を読む前に、Java Collectionsのインタフェースとクラスレベルの関係を図解する3分間の速読が必要です.
1.LinkedListはいつ使いますか?ArrayListはいつ使いますか?
ArrayListは本質的に配列である.その要素はインデックス値から直接アクセスできます.しかし、配列がいっぱいになった場合、より大きな配列を再割り当てし、すべての要素を新しい配列に移動するにはO(n)の時間がかかります.もちろん、既存の配列から要素を追加または削除するには、既存の要素を移動する必要があります.これはArrayListを使用する上で最大の不便点かもしれません.
LinkedListは両端チェーンテーブルです.そのため、チェーンテーブルの中央にある要素を取得するには、チェーンテーブルのヘッダから検索する必要があります.一方、チェーンテーブルの要素を追加または削除するのは、ローカルで変更するだけでよいため、すぐにできます.
次の表では、最も速い場合の比較に時間がかかることをまとめています.
Method
Arraylist
LinkedList
get(index)
O(1)
O(n)
add(E)
O(n)
O(1)
add(E, index)
O(n)
O(n)
remove(index)
O(n)
O(n)
Iterator.remove()
O(n)
O(1)
Iterator.add(E)
O(n)
O(1)
実行時間にかかわらず、大規模なリストではメモリの使用量を追加する必要があります.LinkedListの各nodeには、前後の2つのnodeを接続するために少なくとも2つの追加のポインタが必要です.ArrayListでは要素値を配列格納するだけでよい.
2.コンテナを巡る場合、効率的に要素を除去する操作と同等ですか?
最も正確な方法は、次のコードに示すように、コンテナを巡回するときにIterator.remove()でコンテナを修正することです.

Iterator itr = list.iterator();
while(itr.hasNext()) {
// do something
   itr.remove();
}

もう1つの非常に高周波で使用されていますが、正しくないコードは次のとおりです.

for(Integer i: list) {
  list.remove(i);
}

上のコードを実行するとConcurrentModificationExceptionが得られます.なぜなら、このリストを横切るために反復器が生成された後(forループで)、使用されるからです.同時に、このリストはIterator.remove()によって変更された.Java言語では、あるスレッドがコンテナを変更している場合、別のスレッドが遍歴することは許されません.
3.Listをint[]に変換する方法
最も速い方法は、Apache Commons LangライブラリのArrayUtilsを使用する可能性があります.

int[] array = ArrayUtils.toPrimitive(list.toArray(new Integer[0]));

JDKではショートカットはありません.リストがList.toArray()に変換されるので、Integer[]は使用できません.正しい方法は次のとおりです.

int[] array = new int[list.size()];
for(int i=0; i < list.size(); i++) {
  array[i] = list.get(i);
}

4.int[]をリストに変換する方法
最も速い方法は、Apache Commons LangライブラリのArrayUtilsで、以下のようになります.

List list = Arrays.asList(ArrayUtils.toObject(array));

JDKにもショートカットはありません.

int[] array = {1,2,3,4,5};
List list = new ArrayList();
for(int i: array) {
  list.add(i);
}

5.容器を濾過する最善の方法は何ですか.
GuavaまたはApache Commons Langなどのサードパーティ製パッケージを使用してこの機能を満たすことができます.彼らはfilter()方法(in Collections 2 of Guava and in CollectionUtils of Apache)を提供しています.filter()メソッドは、予め判断された要素を返します.
JDKでは、実現が難しくなります.良いニュースはJava 8で、断言が入ります.しかし、コンテナ全体を巡るために反復器を使用する必要があります.

Iterator itr = list.iterator();
while(itr.hasNext()) {
int i = itr.next();
if (i > 5) { // filter all ints bigger than 5
      itr.remove();
   }
}

もちろん、GuavaやApacheの実装を真似て、新しいPredicateインタフェースを導入することもできます.ほとんどの高級開発者はそうします.

public interface Predicate<T> {
boolean test(T o);
}

public static  void filter(Collection collection, Predicate predicate) {
if ((collection != null) && (predicate != null)) {
       Iterator itr = collection.iterator();
while(itr.hasNext()) {
            T obj = itr.next();
if (!predicate.test(obj)) {
               itr.remove();
            }
        }
    }
}

次のコードを使用してコンテナをフィルタできます.

filter(list, new Predicate() {
public boolean test(Integer i) { 
return i <= 5; 
    }
});

6.リストをSetに変換する最も簡単な方法は何ですか?
同じものをどのように定義するかによって、2つの方法ができます.第1の方法は、1つのリストをHashSetに入れ、その後、hashCode()によって複製を識別することである.ほとんどの場合、正常に動作します.しかし、比較方法を指定する必要がある場合は、自分の比較器を定義できる場合は、2つ目の方法を使用する必要があります.

Set set = new HashSet(list);
Set set = new TreeSet(aComparator);
set.addAll(list);

7.ArrayListで重複する要素を削除する方法
この問題は前の問題と非常に関係がある.
ArrayListの要素の順序に関心がない場合は、リストをsetに入れて重複する要素を削除し、リストに戻すのが賢明です.コードは次のとおりです.

ArrayList** list = ... // initial a list with duplicate elements
Set set = new HashSet(list);
list.clear();
list.addAll(set);

順序に関心がない場合は、標準JDKでLinkedHashSetにリストを入れることができます.要素の順序は変わりません.
8.コンテナのソート
Java言語では、コンテナのソートにはいくつかの方法があります.すべての方法は、容器の容姿順序または特定の比較器に基づいている.自然な順序では、要素の比較インタフェースを実現する必要があります.Collections.sort()は、リストを巡回することができる.JAvadocでは、このソートが安定であり、性能がnlog(n)であることが説明されている.
PriorityQueueは、順序付けされたキューを提供します.PriorityQueueとCollections.sort()の違いは、PriorityQueueが常に順序付けされたキューを維持していることですが、キューからヘッダノードを取得するしかありません.PriorityQueue.get(4)などの内部要素をランダムに取得することはできません.
コンテナに重複が存在しない場合、TreeSetは別の選択です.PriorityQueueと同様に、ライフサイクル内で順序付けされたsetが維持されています.TreeSetから最も低い要素と最も高い要素を取得できますが、要素にランダムにアクセスすることはできません.
簡単に言えば、  Collections.sort()は一時的な順序リストにすぎません.PriorityQueueとTreeSetは常に順序付けされていますが、その要素にインデックスでアクセスすることはできません.
9. Collections.emptyList() vs new instance
この問題は、emptyMap()とemptySet()の比較にも適用される.
2つのメソッドはいずれも空のリストを返しますが、  Collections.emptyList()は、不変のリストを返します.これは、 のリストに新しい要素を追加することを忘れてはいけないことを意味します.この背景の下で、Collections.emptyList()呼び出しのたびに、実際には空のテーブルのインスタンスは作成されません.また、既存の空のインスタンスを服用します.デザインモデルのSingletonに詳しいなら、私の言う意味がわかります.頻繁に呼び出すと、よりパフォーマンスが向上します.
10. Collections.copy
ソース・リストを宛先リストにコピーするには、2つの方法があります.1つの方法は、ArrayListのコンストラクタを使用することです.

ArrayList dstList = new ArrayList(srcList);

もう1つの方法は、Collections.copy()を使用することである.最初の行に注意して、最初にリストを割り当てました.このリストの最小長は目的のリストの長さです.Javadocに従って安定し、目的リストも最低でもソースリストの長さです.

ArrayList dstList = new ArrayList(srcList.size());
Collections.copy(dstList, srcList);

2つの方法は都市の浅いコピーで、それではこの2つの方法の違いはどこですか?
まず、Collections.copy()は、すべてのソースリストを収容するのに十分なスペースがない場合でも、宛先リストの容量を再割り当てしない.もちろん、IndexOutOfBoundsException異常が放出されます.このようなメリットは何ですか?理由の1つは、ArrayListで新しいリストを再割り当てするのではなく、配列を多重化したい場合に、方法が線形の時間内に完了することを保証することです.Collections.copy()はリストにしか使用できませんが、ArrayListのパラメータはコンテナクラスであってもよいので、より広く適用されます.
以上!