HashSetとCopyOnWriteArraySet

前言

この文章の目的は以下の通りです。

HashSetはどのように要素の重複と無秩序を保証するか

HashSetの追加削除(変更?)原理

CopyOnWriteArraySetは同時の原理

をサポートする

CopyOnWriteArraySetの追加削除(変更?)原理

分析過程を見たくなければ、直接文章の最後に引いて結論を読むことができます.
まずSetインタフェースを見てみましょう

 1 public interface Set extends Collection {
 2  
 3     int size();
 4     boolean isEmpty();
 5     boolean contains(Object o);
 6     Object[] toArray();
 7      T[] toArray(T[] a);
 8     boolean add(E e);
 9     boolean remove(Object o);
10     boolean containsAll(Collection> c);
11     boolean addAll(Collection extends E> c);
12     boolean retainAll(Collection> c);
13     boolean removeAll(Collection> c);
14     boolean equals(Object o);
15     int hashCode();
16 }

私たちは以上のインタフェースからSetがgetとsetの方法を持っていないことを発見しました.つまり、調べたり変えたりしていません.なぜですか.理由は次のとおりです.

Setは無秩序であるためindexによるクエリがない

も同様にSetが無秩序であるため、つまりIndexによる修正ができない

である.

1 HashSetはどのように要素が重複しないことを保証しますか?

HashSetがどのようにして中の要素が重複しないことを保証するかを明らかにするには、以下の2つの面から始めなければなりません.

その最下位のストレージ構造は何ですか?

挿入時に要素が存在するかどうかをどのように判断しますか?

私たちが上記の2つの問題を明らかにした後、HashSetがなぜ無秩序なのかを理解することができます.

1）HashSetの下位ストレージロジック

ソースコードを見てみましょう.

 1 public class HashSet
 2     extends AbstractSet
 3     implements Set, Cloneable, java.io.Serializable{
 4     static final long serialVersionUID = -5024744406713321676L;
 5 
 6     private transient HashMap map;
 7 
 8     // Dummy value to associate with an Object in the backing Map
 9     private static final Object PRESENT = new Object();
10 
11     /**
12      * Constructs a new, empty set; the backing HashMap instance has
13      * default initial capacity (16) and load factor (0.75).
14      */
15     public HashSet() {
16         map = new HashMap<>();
17     }
18     ...
19 }

HashSetの下位ストレージ構造はHashMapであり,HashSetの要素はこのMapのKeyとして格納され,HashMapのKeyの格納は無秩序で繰り返し不可能であることを示し,HashSetにおいてどのように要素が繰り返されないことを保証するかを説明した.

2）挿入ロジック

public boolean add(E e) {return map.put(e, PRESENT)==null;}

直接mapにputする

3）まとめ

以上より、HashSetの下位ストレージ構造がHashMapであり、mapのキーとしてHashSetに挿入された要素が格納されていることがわかり、HashSetの特徴を保証します.

HashSetの要素が重複しない

HashSetの要素は無秩序な

である

2 HashSet追加削除(変更?)げんり

前のセクションでは、HashSetの最下位ストレージ構造がHashMapであることを理解しました.では、その削除はmapのputとremoveです.

1）増加

public boolean add(E e) {return map.put(e, PRESENT)==null;}

直接mapにputする

2）削除

public boolean remove(Object o) {return map.remove(o)==PRESENT;}

mapから直接削除すれば簡単です

3 CopyOnWriteArraySetはなぜコンカレントをサポートできるのですか?

CopyOnWriteArraySetがなぜコンカレントをサポートできるのかを明らかにする前に、次のいくつかの問題を考えてみましょう.

HashSet対応の同時クラスはなぜCopyOnWriteArraySetと呼ばれ、CopyOnWriteHashSetとは呼ばれないのでしょうか.

CopyOnWriteArraySetとCopyOnWriteArrayListは関係ありますか?

上記の2つの問題を明らかにすると、CopyOnWriteArraySetがなぜ同時サポートできるのかを知っていると思います.にさせておく
まず、CopyOnWriteArraySetのソースコードの一部を見てみましょう.

 1 public class CopyOnWriteArraySet extends AbstractSet
 2         implements java.io.Serializable {
 3     private static final long serialVersionUID = 5457747651344034263L;
 4 
 5     private final CopyOnWriteArrayList al;
 6 
 7     /**
 8      * Creates an empty set.
 9      */
10     public CopyOnWriteArraySet() {
11         al = new CopyOnWriteArrayList();
12     }
13     ...
14 }

ソースコードからCopyOnWriteArraySetの下位ストレージ構造がCopyOnWriteArrayListであることが不思議にわかり、名前の由来を知ることができ、CopyOnWriteArrayListと同じ原理をサポートしていることがわかります.
附:CopyOnWriteArrayList原理解析

4 CopyOnWriteArraySetの追加削除(変更?)げんり

1）増加

public boolean add(E e) {
    return al.addIfAbsent(e);
}

メソッド名を見ると、CopyOnWriteArrayListに要素が存在しない場合に追加に成功します.

2）削除

public boolean remove(Object o) {
    return al.remove(o);
}

CopyOnWriteArrayListから直接削除

5まとめ

HashSetはどのように要素の重複と無秩序を保証します
答え:HashSetの下位ストレージ構造はHashMapであり、HashSetの要素はMapのKeyとしてMapに格納されているため、HashMapのKeyは重複せず無秩序であるため、HashSetの要素は重複しない無秩序である

HashSetの追加削除(変更?)げんり
HashSetの削除原理は簡単です.mapのputとremoveです.どうして変更しなかったのですか.それはHashSetの要素が無秩序なため、インデックスに基づいてクエリーや変更ができないからです.

CopyOnWriteArraySetは同時の原理をサポートする
CopyOnWriteArraySet CopyOnWriteArraySetと呼ばれるのは、最下位のストレージ構造がCopyOnWriteArrayListであり、同時セキュリティが保証されているからです.

CopyOnWriteArraySetの追加削除(変更?)げんり
CopyOnWriteArraySetはAbstractSetを継承しており、HashSetと同様に添削のみであり、改ざんはされていない.添削原理はCopyOnWriteArrayListを呼び出す添削方法であるが、増設する場合はリストにその要素が格納されているか否かを判断する必要がある