23

java.util.HashSetに追加されたすべてのオブジェクトがObject.equals（）とObject.hashCode（）を決定論的な方法で実装する場合、HashSetに対する反復順序は、追加されたすべての同一の要素セットに対して同一であることが保証されます。それらが追加された順序？

ボーナスの質問：挿入順序も同じ場合はどうなりますか？

（同じHashSet初期化を使用するSun JDK6を想定しています。）

編集：私の元の質問は明確ではありませんでした。これは、HashSetの一般的な契約ではなく、JDK6でのSunのHashSetの実装が決定論に関する保証として提供するものです。それは本質的に非決定論的ですか？イテレータが使用する順序に影響を与えるものは何ですか？

4

9 に答える 9

21

絶対違う。

バケットの衝突がある場合は常に、挿入順序が反復順序に直接影響します。

2つの要素が同じバケットに入ると、少なくとも衝突処理と反復の実装が単純な場合（およびSunの要素が単純な場合）、最初に挿入された要素が反復中に返される最初の要素にもなりますjava.util.HashMap。

于 2010-04-24T13:39:17.713 に答える
12

このようなものに対する「公式の」保証はありません。同じHashSet実装のインスタンスで、同じ方法で初期化された場合に、おそらく当てはまると思います。しかし、たとえばJava5と6では反復順序が異なる場合があります。

また、再ハッシュのために、異なるサイズで初期化された同じHashSet実装のインスタンスでは異なる場合があります。つまり、100個の要素と2つのセットがあり、1つは100より大きいサイズで初期化され、もう1つははるかに小さいサイズである場合、2番目の要素は再割り当てされ、要素がいっぱいになるまで数回再ハッシュされます。これにより、同じバケットにマップされた要素が異なる順序で追加される（したがって繰り返される）可能性があります。

Java4以降ではLinkedHashSet、反復順序がその要素が挿入された順序になることを保証するものがあります。

于 2010-04-24T13:30:27.327 に答える
10

以前のコメントを確認/賛成したかった。つまり、一貫した順序でHashSetの反復に依存しないでください。これにより、システムにバグが発生する可能性があります。

次の場合でも、HashSetで反復順序が一貫していないバグを見つけて修正しました。

  • 挿入順序は同じです。
  • 有効なequals（）およびhashCode（）メソッドを持つクラスのオブジェクト。

そして、LinkedHashSetを使用して修正しました。

以前のポスターに感謝します:)

于 2010-11-05T21:02:28.637 に答える
9

javadocによると：

このクラスは、ハッシュテーブル（実際にはHashMapインスタンス）に裏打ちされたSetインターフェイスを実装します。セットの反復順序については保証されません。特に、順序が時間の経過とともに一定に保たれることを保証するものではありません。[...]このクラスのイテレータメソッドによって返されるイテレータはフェイルファストです。イテレータが作成された後、いつでもセットが変更された場合

そして方法iterator：

このセットの要素に対するイテレータを返します。要素は特定の順序で返されません。

ですから、そのような仮定はできないと思います。

于 2010-04-24T13:29:51.163 に答える
3

HashSetに入れるものの反復順序については、決して想定しないでください。その契約では、HashSetを信頼することはできないと明示的に規定されているためです。挿入順序を維持する場合はLinkedHashSetを使用し、自然順を維持する場合はTreeSetを使用します。

于 2010-04-24T13:42:05.537 に答える
2

表示される順序オブジェクトは、HashSetのバケットの最終的な数によって異なります。負荷率や初期容量を変更することで、要素の最終的な順序を変更できます。

次の例では、これらの構成がそれぞれ異なる順序になっていることがわかります。

public static void main(String...args) throws IOException {
    printOrdersFor(8, 2);
    printOrdersFor(8, 1);
    printOrdersFor(8, 0.5f);
    printOrdersFor(32, 1f);
    printOrdersFor(64, 1f);
    printOrdersFor(128, 1f);
}

public static void printOrdersFor(int size, float loadFactor) {
    Set<Integer> set = new HashSet<Integer>(size, loadFactor);
    for(int i=0;i<=100;i+=10) set.add(i);
    System.out.println("new HashSet<Integer>("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set);
}

プリント

new HashSet<Integer>(8, 2.0) adding 0,10, ... 100 => [0, 50, 100, 70, 40, 10, 80, 20, 90, 60, 30]
new HashSet<Integer>(8, 1.0) adding 0,10, ... 100 => [0, 50, 100, 70, 20, 80, 10, 40, 90, 30, 60]
new HashSet<Integer>(8, 0.5) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 20, 80, 90, 30, 60]
new HashSet<Integer>(32, 1.0) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 80, 20, 90, 60, 30]
new HashSet<Integer>(64, 1.0) adding 0,10, ... 100 => [0, 70, 10, 80, 20, 90, 30, 100, 40, 50, 60]
new HashSet<Integer>(128, 1.0) adding 0,10, ... 100 => [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
于 2010-11-05T21:37:01.113 に答える
1

いいえ、これは保証されていません。

まず、異なるJVMはHashSetアルゴリズムを異なる方法で実装する可能性があるため（HashSet仕様に準拠している限り）、異なるJVMで異なる結果が得られます。

第2に、アルゴリズムは、さまざまなバケット（ハッシュテーブルアルゴリズムの一部）を構築するときに、非決定論的要因に依存する場合があります。

于 2010-04-24T13:29:45.433 に答える
0

Java開発者は、答えが「いいえ」であるとみなしてほしいと確信しています。特に、ハッシュテーブルの場合、ハッシュが衝突するオブジェクト（同じhashCode％size）が順序に関係なく同じ順序で観察されることを保証するために、このプロパティを必要としない他のすべての人にとってなぜ遅くなるのでしょうか。入れますか？

于 2010-04-24T13:31:19.020 に答える
0

そのような仮定はできません。javadocによると：

このクラスは、ハッシュテーブル（実際にはHashMapインスタンス）に裏打ちされたSetインターフェイスを実装します。セットの反復順序については保証されません。特に、順序が時間の経過とともに一定に保たれることを保証するものではありません。

最も近い方法は、挿入順序を維持するLinkedHashSetを使用することです。

于 2010-04-24T13:40:59.113 に答える