JAva集合----HashSet
8591 ワード
一.前言
JAva集合------set
HashSetはSetインタフェースの実装クラスであり、もちろんSetインタフェースが指定したいくつかの仕様がある.つまり、集合内のすべての要素が一意である場合、HashSetはどのようにして追加された要素の一意性を保証するのか、equals以外に他の方法が含まれているのか.次に、HashSetのソースコードについて詳しく説明します.
二.深く解析する.
1.概要
以下、ソースコードからのコメントを参照します.
HashSetは、ハッシュテーブル(実際にはHashMapインスタンス)によってサポートされるSetインタフェースを実装する.setの反復順序を保証しません.(すなわち、順序を追加する)特に、順序が恒久的に変わらないことを保証しない.null要素の使用を許可します.
HashSetは同期ではありません.複数のスレッドが同時に1つのハッシュsetにアクセスし、少なくとも1つのスレッドがsetを変更した場合、外部同期を維持する必要があります.これは、通常、setを自然にカプセル化したオブジェクトに対して同期操作を行うことによって行われる.このようなオブジェクトが存在しない場合はCollectionsを使用する.synchronizedSetメソッド「パッケージ」set.セットへの予期せぬ非同期アクセスを防止するには、作成時にこの操作を完了することが望ましい:Set s=Collections.synchronizedSet(new HashSet(…));
このようなiteratorメソッドが返す反復器は急速に失敗します.反復器を作成した後、setを変更すると、反復器自体のremoveメソッドを通過しない限り、いつでも任意の方法で変更すると、IteratorはConcurrentModificationExceptionを放出します.したがって、反復器は、ある不確定な時間に任意の不確定な動作が発生するリスクを冒さずに、同時修正に直面してすぐに完全に失敗します.
反復器の迅速な失敗は、一般的には、非同期の同時修正が発生するかどうかについて、いかなるハードウェア保証もできないため、保証されません.高速失敗反復器はC o n c u r r e n t ModificationExceptionを投げ出すために最善を尽くしています.したがって、このような反復器の正確性を向上させるために、この異常に依存するプログラムを作成することは、反復器の迅速な失敗行為がバグの検出にのみ使用されるべきであるという誤りである.
2.変数
HashSet自身が増加した変数は3つしかありません
3.コンストラクタ
HashSetのいくつかの変数とコンストラクタから分かるように、内部のプロセスは、初期容量の指定や成長係数の指定など、内部でHashMapを作成するために使用されます.
4.add方法
HashSetの内部はHashMapによって提供され、HashSetの要素はHashMapのキーとして機能し、valueは同じオブジェクト、すなわちPRESENTである.
ここで,HashSetが要素の一意性をどのように保証するかという問題は,実際にはHashMapにおいてkeyの一意性をどのように保証するかに変換される.
次はHashMapのputメソッドで
HashSetが1つの要素が重複しているかどうかを判断する場合、以下のようにまとめられる. keyのhashCodeによって配列位置に位置決めされ、nullの場合、最初に追加すると重複しません. nullでなければhashCodeにはスレーブ(ハッシュ競合)が存在する可能性があるのでequalsと組み合わせて判断する必要がある. keyがnullまたはnullでない場合、hashが等しい場合、key==がtrue、すなわち同じオブジェクトを返し、繰り返し(keyがnullと同じオブジェクトであると判断した場合) . keyがnullでない場合、同じオブジェクトではありません(==falseを返します)が、equalsはtrueを返し、依然として繰り返します(この場合、定義したオブジェクトが等しい場合、equalsはtrueを返します).
したがって,クラスに対してequalsを書き換えると,equalsがtrueを返すときhashCodeが同じ値を返し,hashCodeが異なる値を返すときequalsがfalseを返すことを保証する.
1つのオブジェクトがHashSetで実際に使用されているかどうかを判断するため,判断を行う.
5.その他
実はHashSetの判断が繰り返される原理が分かっていれば,削除など他の操作に対しては簡単であり,いずれも検索プロセスに基づいている.他の方法,すなわちHashMapを併用することで,ここでは深く検討しない.
JAva集合------set
HashSetはSetインタフェースの実装クラスであり、もちろんSetインタフェースが指定したいくつかの仕様がある.つまり、集合内のすべての要素が一意である場合、HashSetはどのようにして追加された要素の一意性を保証するのか、equals以外に他の方法が含まれているのか.次に、HashSetのソースコードについて詳しく説明します.
二.深く解析する.
1.概要
以下、ソースコードからのコメントを参照します.
HashSetは、ハッシュテーブル(実際にはHashMapインスタンス)によってサポートされるSetインタフェースを実装する.setの反復順序を保証しません.(すなわち、順序を追加する)特に、順序が恒久的に変わらないことを保証しない.null要素の使用を許可します.
HashSetは同期ではありません.複数のスレッドが同時に1つのハッシュsetにアクセスし、少なくとも1つのスレッドがsetを変更した場合、外部同期を維持する必要があります.これは、通常、setを自然にカプセル化したオブジェクトに対して同期操作を行うことによって行われる.このようなオブジェクトが存在しない場合はCollectionsを使用する.synchronizedSetメソッド「パッケージ」set.セットへの予期せぬ非同期アクセスを防止するには、作成時にこの操作を完了することが望ましい:Set s=Collections.synchronizedSet(new HashSet(…));
このようなiteratorメソッドが返す反復器は急速に失敗します.反復器を作成した後、setを変更すると、反復器自体のremoveメソッドを通過しない限り、いつでも任意の方法で変更すると、IteratorはConcurrentModificationExceptionを放出します.したがって、反復器は、ある不確定な時間に任意の不確定な動作が発生するリスクを冒さずに、同時修正に直面してすぐに完全に失敗します.
反復器の迅速な失敗は、一般的には、非同期の同時修正が発生するかどうかについて、いかなるハードウェア保証もできないため、保証されません.高速失敗反復器はC o n c u r r e n t ModificationExceptionを投げ出すために最善を尽くしています.したがって、このような反復器の正確性を向上させるために、この異常に依存するプログラムを作成することは、反復器の迅速な失敗行為がバグの検出にのみ使用されるべきであるという誤りである.
2.変数
HashSet自身が増加した変数は3つしかありません
// UID
static final long serialVersionUID = -5024744406713321676L;
// HashSet map
private transient HashMap map;
// HashSet
// Map key--value
// value
private static final Object PRESENT = new Object();
3.コンストラクタ
// ， HashMap
public HashSet() {
map = new HashMap<>();
}
//
public HashSet(Collection extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// HashSet
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// HashSet
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// default
// LinkedHashSet
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSetのいくつかの変数とコンストラクタから分かるように、内部のプロセスは、初期容量の指定や成長係数の指定など、内部でHashMapを作成するために使用されます.
4.add方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashSetの内部はHashMapによって提供され、HashSetの要素はHashMapのキーとして機能し、valueは同じオブジェクト、すなわちPRESENTである.
ここで,HashSetが要素の一意性をどのように保証するかという問題は,実際にはHashMapにおいてkeyの一意性をどのように保証するかに変換される.
次はHashMapのputメソッドで
public V put(K key, V value) {
//
// key hash
// key
return putVal(hash(key), key, value, false, true);
}
// ，
// ：JDK 10
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab;
Node p;
int n, i;
// table null
//table 0
//resize() 。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// key hashCode hash
// null 。
// 。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
//
// hash key key
// key equals 。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//
else if (p instanceof TreeNode)
// 。
else {
}
//e null ,put null
if (e != null) { // existing mapping for key
V oldValue = e.value;
..
return oldValue;
}
}
// ，
// ， ， null.
// HashSet add map.put(e, PRESENT)==null;
// true , ， 。
// e != null ， ，
//map.put(e, PRESENT)==null; false
return null;
}
}
HashSetが1つの要素が重複しているかどうかを判断する場合、以下のようにまとめられる.
したがって,クラスに対してequalsを書き換えると,equalsがtrueを返すときhashCodeが同じ値を返し,hashCodeが異なる値を返すときequalsがfalseを返すことを保証する.
1つのオブジェクトがHashSetで実際に使用されているかどうかを判断するため,判断を行う.
5.その他
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
@SuppressWarnings("unchecked")
public Object clone() {
try {
HashSet newSet = (HashSet) super.clone();
newSet.map = (HashMap) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out HashMap capacity and load factor
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
// Write out size
s.writeInt(map.size());
// Write out all elements in the proper order.
for (E e : map.keySet())
s.writeObject(e);
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read capacity and verify non-negative.
int capacity = s.readInt();
if (capacity < 0) {
throw new InvalidObjectException("Illegal capacity: " +
capacity);
}
// Read load factor and verify positive and non NaN.
float loadFactor = s.readFloat();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// Read size and verify non-negative.
int size = s.readInt();
if (size < 0) {
throw new InvalidObjectException("Illegal size: " +
size);
}
// Set the capacity according to the size and load factor ensuring that
// the HashMap is at least 25% full but clamping to maximum capacity.
capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
HashMap.MAXIMUM_CAPACITY);
// Constructing the backing map will lazily create an array when the first element is
// added, so check it before construction. Call HashMap.tableSizeFor to compute the
// actual allocation size. Check Map.Entry[].class since it's the nearest public type to
// what is actually created.
SharedSecrets.getJavaObjectInputStreamAccess()
.checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));
// Create backing HashMap
map = (((HashSet>)this) instanceof LinkedHashSet ?
new LinkedHashMap<>(capacity, loadFactor) :
new HashMap<>(capacity, loadFactor));
// Read in all elements in the proper order.
for (int i=0; i spliterator() {
return new HashMap.KeySpliterator<>(map, 0, -1, 0, 0);
}
実はHashSetの判断が繰り返される原理が分かっていれば,削除など他の操作に対しては簡単であり,いずれも検索プロセスに基づいている.他の方法,すなわちHashMapを併用することで,ここでは深く検討しない.