JavaのHashSetはどのように機能しますか？

可能性の重複：
How does Java hashmap work?JavaのHashSetはどのように機能しますか？

誰かがJavaの仕事にどのようにHashSets私に説明し、なぜ彼らはのArrayListを使用するよりも高速ですができますか？

2012-02-02 madCode

ですかどうかは、使用するものによってまったく異なります。 HashMap は、例えば、ArrayList よりも高速に索引で検索することはできません。それはコレクションを操作することで、*高速化が可能になりますが、それはどのように物を追加するかによって異なります。 – cHao

*アルゴリズムの紹介*などのデータ構造とアルゴリズムに関する良い本を拾い読みし、ハッシュテーブルについて読んでください。 –

http://docs.oracle.com/javase/tutorial/collections/ – JSager

ArrayListとは異なり、Setとなります。ArrayListは複製できません。さまざまな目的で作成されています。また、注文とは異なり、リストとは異なります。

第2の - HashSetは、O(1)要素のシーク時間を可能にするhash tableデータ構造上に構築されます。あなたが例えば要素の反復にしたい場合は - - 通常HashSet [悪いためキャッシュのパフォーマンスの中でより速く、その後になりますArrayListでそれをやって何度も、HashSetは遅く、その後ArrayListであることを

は

注意ハッシュの、実際のところ、他の理由]

出典

2012-02-02 20:56:32 amit

HashSetは、実際には値が常に同じHashMapです。

の仕方が多くの場所で記述されています（「ハッシュテーブル」ともいいます）。つまり、キー（オブジェクト）のハッシュを生成し、それらをテーブルに配置します。次に、キーを探すたびに、そのハッシュが計算され、テーブル内のバケットが直接参照されます。つまり、マップにアクセスする操作が1つ（最高の場合）だけです。

HashSetにはキーが含まれているだけなので、.contains(..)はO(1)です。これとremove(..)は、HashSetがArrayList（これはO（n））よりも速い唯一の操作です。反復は同じであり、加算も同じです。

出典

2012-02-02 20:56:03 Bozho

説明的な答えに追加するだけで、反復はO（n）でなければならず、加算はO（1）時間の複雑さでなければなりません。ちょうどHashMapと同じです。チェックするための良いコンセプトは、より多くのデータがデータ構造に格納される（負荷係数でチェックされる）リハッシュです。そのため、より大きなテーブルを作成しなければならないため、平均挿入時間が増加します。 –

うち、例えばオーバーを反復し、はArrayListにを追加高速です。

そしてちょっと、ソートハッシュセットもできません。

しかし、最も速いのはNoOpです。 NoOpほど離れたところには何もありません。確かに、それは多くのことをしない、NoOp。しかし、それは本当に速いです！

あなたは「より速い」と考えているものをより正確にする必要があります。

出典

2012-02-02 21:01:59

これらは2つの異なるデータ構造です。

HashSetの背後にある概念はキープロービングです。
I.入力キーの変換を使用して、配列内の値の位置のインデックスを取得します。
アレイがランダムアクセスを許可するので、これは定数O(1)です。

配列にも裏打ちされているので、arraylistもアクセスのためにO(1)です。ランダムアクセスと挿入の場合のみです。

あなたはあなただけのキーを変換し、配列にアクセスHashSetとは違った値に到達するために、リスト内のすべてのelemementsを検索する必要があるため検索はしかし、ArrayListのためO(N)操作です。 HashSetの検索はO(1)

出典

2012-02-02 21:03:45 Cratylus

JavaのHashSetはどのように機能しますか？

答えて

関連する問題