HashSetはソートジョブを内部で実行しますか？

Question

私のSetはソートされていることがあります。ここ

は一例であり：

public class SetOfInteger { 
    public static void main(String[] args) { 
     Random rand = new Random(47); 
     Set<Integer> intset = new HashSet<>(); 
     for (int i = 0; i < 10; i++) { 
      int j = rand.nextInt(30); 
      System.out.print(j + " "); 
      intset.add(j); 
     } 
     System.out.println(); 
     System.out.println(intset); 
    } 
} 

結果は、setがソートされていないことを示しています。

8 5 13 11 1 29 28 20 12 7 
[1, 20, 5, 7, 8, 11, 12, 29, 28, 13] 

私は声明の中でi < 20に終了式を変更すると、結果はsetがソートになっていることを示しています。

8 5 13 11 1 29 28 20 12 7 18 18 21 19 29 28 28 1 20 28 
[1, 5, 7, 8, 11, 12, 13, 19, 18, 21, 20, 29, 28] 

これは奇妙なのですか？私はそれを説明する方法が分からないので、助けが必要です。ありがとうございます。

Answer 1

ハッシュセットがソートされる保証がないため、手動でソートする必要があります。必要であれば、あなたが望む機能を提供しますこれもTreeSetのを使用することができますが、HashSetのを使用したい場合は、とにかく、この試してみてください。

Set intset = new HashSet(); 
List sortedIntList = new ArrayList(intset); 
Collections.sort(sortedIntList); 

Answer 2

A HashSetのソートされた反復を保証するものではありませんが、非常に特殊な状況下で、その内部データを構造はbucket sortのように動作します。

具体的には、[0,65535]の範囲の整数キーと最大のキーより大きいテーブルサイズの場合、キーが格納されているバケットのインデックスはキー自体に等しいので、イテレータバケツ順に反復し、要素をソートされた順序で発行します。

Answer 3

興味深い質問です。セットは、その要素を格納するためにarray of linked listを使用します。 hashCode()は、Setに格納されるオブジェクトの位置を（間接的に）見つけるために使用されます。

同じ位置に格納する必要のあるオブジェクトが2つある場合、オブジェクトはその位置のリンクリストの次のスロットに格納されます。

アレイのサイズは動的で、その中のオブジェクトの数に応じて実行時間が計算されます。それは確かではありませんが、Setがサイズを増やしている可能性があるため、あなたの数字がソートされていると見なします。 hashCode()は数値に依存するため、順次計算されます。ループのサイズが大きくなると、配列のサイズが大きくなるため、衝突はなく、出力はソートされます。

でも、私の答えが誤解を招かないように強調したいと思います。同じシーケンスを生成します修正されていないHashSetの反復処理を行う：HashSetはHashSetのの繰り返し順序が定義されていない要素

Answer 4

の任意の順序を保証するものではありません、唯一の保証は、それが一貫しているということです。

コメント者が述べたように、クラスは各要素のhashCodeメソッドを使用して、特定の数のビンにを格納します。たとえば、20ビンを使用している場合は、ビンインデックスとしてo.hashCode() % 20を取ることができます。各ビンはリスト内にいくつかの項目を持つことができ、それらはequalsメソッドで区別されます。したがって、Integerのハッシュがそのint値であっても、順序は自然な整数の順序である必要はありません。

さらに、セットは要素の挿入および削除時に負荷率を監視します。フリービンの割合、最大ビンリストサイズ、1ビン当たりの平均アイテム数などを考慮してください。適切であると判断すると再ハッシュが実行されます。つまり、要素の格納に使用されるビンの数が変更されるため、o.hashCode() % nのnが変更されるためビンインデックスが変更されます。 すべての要素が新しい場所に「再シャッフル」されます（これはコストのかかる操作です）。これにより、要素を追加した後に表示される異なる順序が説明されます。

Answer 5

あなたの質問は、商品の注文がの場合、セットが大きくなるにつれてが変わることを指摘しています。しかし、保存されている順番を数えることはできません。 Setには1つの保証があります。各種類の要素の1つがです。さらなる保証を提供する他のSetオブジェクトがありますが、単純なHashSetは注文の保証はありません。

再注文は、内部的にHashSetが格納される方法による内部改造です。非常に単純化された考え方では、HashSetには値を格納するための特定の数の「スロット」があり、これは通常はプライムでなくても奇数です。 getHashCode()のハッシュコードは、オブジェクトをスロットに割り当てるために使用されます。ハッシュコードの衝突が発生すると、HashSetは等価演算子equals()を使用して、オブジェクトが実際に一意であるかどうかを判断します。

あなたはHashSetいくつかに項目を追加すると起こる：

• オブジェクトは、内部のスロットに
  • を割り当てられているハッシュコードは、その後、さらに場合、それは
  • に属するものをスロットを見つけるためにハッシュされますスロットの衝突がある場合は、平等をテストします。それは同じオブジェクトだ場合はオブジェクトの数が、スロットの数を超えた場合、我々はそのスロット
• にリストに追加されていない場合、我々は、それを破棄し、HashSetニーズが
  • は、作成自体のサイズを変更するには通常、まだ既存のアイテムは、スロットの新しいコレクションに再マップされている奇数または素数
  • あるスロットの大きなセットは - 順序を変更することができる場所です

最終的には、オブジェクトが魔法のようにソートされている場合、それは実装されたものではなく、TreeSetを使用してセットアイテムにソート順を課す場合を除きます。

Answer 6

よくある回答がありますが、この特定の状況で何が起こったのか正確に説明しようとするものはありません。そのため、私はHashSetの仕組みについての説明を追加するのではなく、私はその理解を当然と考えています。

default constructor of HashSetは、容量が16で負荷率が0.75のセットを作成します。つまり、16個のビンがあり、16 * 0.75 = 12のユニークエレメントを挿入すると、この容量が増えます。

最初のケースでは、数字は16で割り算されたときに剰余でソートされます。セットはテーブルサイズ16で始まり、各要素をビンに「ハッシュ」します。x % 16。それから12要素があるとき、それはテーブルを成長させ、再ハッシュを実行しました（明らかでない場合はJavier Martinの答えを参照）。おそらくテーブルを32に増やします（それがどのように成長するかについての情報はthe java 6 docです。バケツの数はそれが意味するところであれば、「おおよそ」倍になります。）これは30以下の各整数を独自のビンに与えたので、各ビンを順番に反復して順番に反復しました。 64未満の数字を挿入した場合、反復がソートされる前に、32 * 0.75 = 24の要素を挿入する必要があることがわかります。

ビンを割り当てるこの方法は、動作が保証されていないです。。他のJavaバージョン/実装のHashSetは、オブジェクトのhashCode()の値が単純に余りを取るよりも複雑な処理を行うかもしれません。 （ruakhとコメントのふわふわしたように - ありがとう！）