JavaのListからユニークなデータを集める最速の方法

Question

私の質問の基礎は、はJavaのListオブジェクトを指定しています。ユニークなデータのコレクションを返す最も速い方法は何ですか？

より具体的なバージョンでは、2d ArrayList（テーブルのように考える）があり、指定した列のインデックスをループして一意のデータを返す必要があります。

はここに私の現在の設定です：私は1に不明確なセットのサイズと負荷率にプラスワンの初期容量を設定するとき

public Set<Object> getDistinctColumnData(int colIndex) { 

    //dataByIndex = List<List<Object>> 

    Set<Object> colDistinctData = new HashSet<Object>(dataByIndex.size() + 1, 1f) ; 

    for(List<Object> row : dataByIndex) { 
     colDistinctData.add(row.get(colIndex)) ; 
    } 

    return colDistinctData ; 

} 

私は小さなパフォーマンスのゲインを得た（私の考えでは、それは勝ちましたそれが100％に達するまで成長する必要はありません。元のセットがすでに100％異なっていても（あるいは間違っていますか？）、それは起こらないはずです。

速い方法がありますか？

Answer 1

ただ2つのユニークなコレクションを持っていれば速くなると思います。 dataByIndexリストを更新するだけでなく、dataSet Collection（Set）も更新します。あなたのdataByIndexリストに挿入すると、あなたのデータセットセットにも入れます。次に、必要に応じてデータセットを使用します。セットは、セットであるという性質上、一意性を維持します。

Answer 2

容量と負荷係数を指定した値に設定することはあまり意味がないと思います。どのようなハッシュ関数を使用していますか？リンクされたリストにダウングレードすることはできますか？

Answer 3

HashSetの初期容量をさらに増やすと、平均的なパフォーマンスの向上が期待できます。これは、リスト内のオブジェクトのハッシュ値の分布が、衝突がより起こりやすいようなものである可能性があるためです。

たとえば、重複する値がないにもかかわらず、最初の挿入を除いてすべてが衝突になります。 （整数のJavaハッシュ関数は整数そのものの値であり、HashSetは衝突時にオープンアドレッシングと線形プロービングを使用します）。

[0,10,1,2,3,4,5,6,7] 

さらに悪いことに、挿入する前にすべての空き領域をチェックする必要があるためです。最後の例0で

[0, 5, 25, 125] 

はインデックス0 5に入れます、最初は5％のサイズ（すなわち。5）として、インデックス0になり0に等しいので、インデックス1 125に行くのインデックス0に行くだろう、 0はインデックス0に、5はインデックス1に、25はインデックス2にあります.3回のチェック後に最終的にインデックス3に125を挿入することができます。

これにより、最初の容量を増やすと、平均）、衝突が発生した場合に必要なチェック数が減少します（平均でも同様）。デフォルトでは、javaはパフォーマンスとメモリ使用のバランスが良いと0.75という負荷係数を使用します。したがって、0.75の負荷係数で除算し、1を加算すると、最初の容量が大きくなるはずです。