1概要
この記事では、
HashSetについて詳しく説明します。これは最も人気のある
Set__実装の1つであり、またJava Collections Frameworkの不可欠な部分です。
2
HashSet
の紹介
HashSet
は、Java Collections APIの基本的なデータ構造の1つです。
この実装の最も重要な側面を思い出しましょう。
-
一意の要素を格納し、nullを許可します
-
それは
HashMap
に支えられています -
広告掲載順位は維持されません
-
スレッドセーフではありません
この内部の
HashMap
は、
HashSet
のインスタンスが作成されたときに初期化されます。
public HashSet() {
map = new HashMap<>();
}
HashMap
がどのように機能するかをもっと深く知りたいのなら、
ここで焦点を絞った記事
を読むことができます。
3.
API
このセクションでは、最も一般的に使用されている方法を検討し、簡単な例をいくつか見ていきます。
3.1.
add()
add()
メソッドは、要素をセットに追加するために使用できます。
メソッド規約では、要素がセットに存在していない場合にのみ追加されるように指定されています
要素が追加された場合、メソッドは
trueを返し、それ以外の場合は
false.__を返します。
以下のように
HashSet
に要素を追加することができます。
@Test
public void whenAddingElement__shouldAddElement() {
Set<String> hashset = new HashSet<>();
assertTrue(hashset.add("String Added"));
}
実装の観点からは、
add
メソッドは非常に重要なものです。実装の詳細は、
HashSet
が内部でどのように機能し、
HashMapの
put__メソッドを利用するかを示しています。
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
map
変数は、内部のバッキング__HashMapへの参照です。
private transient HashMap<E, Object> map;
最初にリンク:/java-hashcode[
hashcode
]に慣れることをお勧めします。これは、要素がハッシュベースのデータ構造でどのように編成されているかについて詳細に理解するためです。
要約すると:
-
HashMap
は、デフォルト容量が16の
buckets
の配列です。
elements – 各バケットは異なるハッシュコード値に対応します
** さまざまなオブジェクトが同じハッシュコード値を持つ場合、それらはに格納されます。
シングルバケツ
**
load factor
に達すると、新しい配列が2倍になります
前の要素のサイズとすべての要素が再ハッシュ化されて再配布されます
対応する新しいバケット間
** 値を取得するには、キーをハッシュし、それを変更してから、
複数のオブジェクトがある場合は、対応するバケットと潜在的なリンクリストを検索します。
3.2.
contains()
-
contains
メソッドの目的は、与えられた
HashSet
内に要素が存在するかどうかをチェックすることです** 要素が見つかれば
true
を返し、そうでなければ
false.
HashSet
の要素を確認することができます。
@Test
public void whenCheckingForElement__shouldSearchForElement() {
Set<String> hashsetContains = new HashSet<>();
hashsetContains.add("String Added");
assertTrue(hashsetContains.contains("String Added"));
}
オブジェクトがこのメソッドに渡されるたびに、ハッシュ値が計算されます。その後、対応するバケットの場所が解決されてトラバースされます。
3.3.
remove()
指定された要素が存在する場合、このメソッドは指定された要素をセットから削除します。
セットに指定された要素が含まれている場合、このメソッドは
true
を返します。
実用的な例を見てみましょう。
@Test
public void whenRemovingElement__shouldRemoveElement() {
Set<String> removeFromHashSet = new HashSet<>();
removeFromHashSet.add("String Added");
assertTrue(removeFromHashSet.remove("String Added"));
}
3.4.
clear()
セットからすべてのアイテムを削除しようとするときにこのメソッドを使います。
基礎となる実装は、基礎となる__HashMapからすべての要素を単純に消去します。
実際に見てみましょう。
@Test
public void whenClearingHashSet__shouldClearHashSet() {
Set<String> clearHashSet = new HashSet<>();
clearHashSet.add("String Added");
clearHashSet.clear();
assertTrue(clearHashSet.isEmpty());
}
3.5.
サイズ()
これはAPIの基本的なメソッドの1つです。
HashSet
に存在する要素の数を識別するのに役立つので、これは頻繁に使用されます。
基礎となる実装は、単に計算を
HashMapのsize()
メソッドに委任します。
実際に見てみましょう。
@Test
public void whenCheckingTheSizeOfHashSet__shouldReturnThesize() {
Set<String> hashSetSize = new HashSet<>();
hashSetSize.add("String Added");
assertEquals(1, hashSetSize.size());
}
3.6.
isEmpty()
このメソッドを使用して、
HashSet
の特定のインスタンスが空かどうかを判断できます。セットに要素が含まれていない場合、このメソッドは
true
を返します。
@Test
public void whenCheckingForEmptyHashSet__shouldCheckForEmpty() {
Set<String> emptyHashSet = new HashSet<>();
assertTrue(emptyHashSet.isEmpty());
}
3.7.
iterator()
このメソッドは
Set
の要素のイテレータを返します。
要素は特定の順序では訪問されず、反復子はフェイルファスト
です。
ここで、ランダムな反復順序を観察できます。
@Test
public void whenIteratingHashSet__shouldIterateHashSet() {
Set<String> hashset = new HashSet<>();
hashset.add("First");
hashset.add("Second");
hashset.add("Third");
Iterator<String> itr = hashset.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
}
-
イテレータの独自のremoveメソッド以外の方法でイテレータが作成された後でセットが変更された場合、
Iterator
は
ConcurrentModificationException
をスローします。
実際に見てみましょう。
@Test(expected = ConcurrentModificationException.class)
public void whenModifyingHashSetWhileIterating__shouldThrowException() {
Set<String> hashset = new HashSet<>();
hashset.add("First");
hashset.add("Second");
hashset.add("Third");
Iterator<String> itr = hashset.iterator();
while (itr.hasNext()) {
itr.next();
hashset.remove("Second");
}
}
別の方法として、イテレータのremoveメソッドを使用していたとしたら、例外が発生することはありませんでした。
@Test
public void whenRemovingElementUsingIterator__shouldRemoveElement() {
Set<String> hashset = new HashSet<>();
hashset.add("First");
hashset.add("Second");
hashset.add("Third");
Iterator<String> itr = hashset.iterator();
while (itr.hasNext()) {
String element = itr.next();
if (element.equals("Second"))
itr.remove();
}
assertEquals(2, hashset.size());
}
非同期の同時変更がある場合は、厳密な保証をすることは不可能であるため、反復子のフェイルファースト動作は保証できません。
フェイルファストイテレータはベストエフォートベースで
ConcurrentModificationException
をスローします。したがって、その正しさのためにこの例外に依存するプログラムを書くのは間違っているでしょう。
4
HashSet
は一意性をどのように維持しますか?
オブジェクトを
HashSet
に入れると、オブジェクトの
hashcode
値を使用して、要素がまだセットに含まれていないかどうかを判断します。
各ハッシュコード値は、計算されたハッシュ値が同じであるさまざまな要素を含むことができる特定のバケット位置に対応します。
しかし、同じ
ハッシュコード
を持つ2つのオブジェクトは等しくないかもしれません
。
そのため、同じバケット内のオブジェクトは
equals()
メソッドを使用して比較されます。
5
HashSet
のパフォーマンス
HashSet
のパフォーマンスは、主に2つのパラメータ – その初期容量
と
負荷率__によって影響を受けます。
要素を集合に追加するのに予想される時間の複雑さは
O(1)
であり、これは最悪のシナリオでは
O(n)
になる可能性があります(1バケットしか存在しない)容量。**
重要な注意:JDK 8以降、http://openjdk.java.net/jeps/180[最悪の場合の時間の複雑さは
O(log ** n)
]
負荷率は最大充填レベルとは何かを表し、それを超えるとセットのサイズを変更する必要があります。
initial capacity
と
load factor
のカスタム値を使って
HashSet
を作成することもできます。
Set<String> hashset = new HashSet<>();
Set<String> hashset = new HashSet<>(20);
Set<String> hashset = new HashSet<>(20, 0.5f);
最初のケースでは、デフォルト値が使用されます。初期容量は16、負荷率は0.75です。 2番目に、デフォルトの容量をオーバーライドし、3番目に、両方をオーバーライドします。
初期容量が小さいとスペースの複雑さは軽減されますが、高価なプロセスである再ハッシュの頻度が高くなります。
一方、
初期容量が大きいと、反復コストと初期メモリ消費量が増加します。 +
経験則として:
-
高い初期容量は、結合された多数のエントリーに適しています
ほとんどまたはまったく繰り返しなしで
** 少ない初期容量は、多くの繰り返しを伴う少数のエントリに適しています
したがって、この2つのバランスを正しくとることが非常に重要です。通常、デフォルトの実装は最適化されており、問題なく動作します。要件に合わせてこれらのパラメータを調整する必要があると感じる場合は、慎重に行う必要があります。
6. 結論
この記事では、
HashSet
の有用性、その目的、およびその基礎となる作業について概説しました。一定の時間パフォーマンスと重複を避けることができることを考えると、ユーザビリティの点でそれがいかに効率的かを見ました。
私たちはAPIからの重要なメソッドのいくつかを研究しました。それらが開発者としてどのように
HashSet
をその可能性に使用するのを助けることができるか。
いつものように、コードスニペットはhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[over on GitHub]にあります。