前言
這篇文章的目的如下:
- HashSet是如何保證元素的不重複和無序
- HashSet的增删(改查?)原理
- CopyOnWriteArraySet支援并發的原理
- CopyOnWriteArraySet的增删(改查?)原理
如果不想看分析過程,可直接拉到文章末尾看結論
先來看看 Set接口
public interface Set<E> extends Collection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
boolean equals(Object o);
int hashCode();
}
我們從以上接口發現Set并沒有get和set方法,也就是沒有查和改,為什麼呢?原因如下:
- 因為Set是無序的,沒有通過index來進行查詢
- 同樣是因為Set是無序的,也就是沒有辦法通過Index來進行修改
1 HashSet如何保證元素不重複?
要弄清楚HashSet如何保證裡面的元素不重複,得從以下兩個方面入手:
- 它底層的存儲結構是什麼?
- 插入時是如何判斷元素是否存在?
當我們弄清楚上面兩個問題之後我們也可以明白HashSet為什麼是無序的了。
1)HashSet的底層存儲邏輯
且看源碼:
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
...
}
我們可以看出來HashSet的底層存儲結構是一個HashMap,并且HashSet的元素作為該Map的Key進行存儲,HashMap的Key的存儲是無序并且不可重複,這就解釋了HashSet中如何保證元素不重複
2)插入邏輯
public boolean add(E e) {return map.put(e, PRESENT)==null;}
直接put到map當中
3)總結
由以上内容我們可以知道HashSet的底層存儲結構是HashMap,并且插入到HashSet中元素作為map的key進行存儲,這就保證HashSet的一下特點:
- HashSet中的元素不重複的
- HashSet中的元素是無序的
2 HashSet增删(改查?)原理
我們從上一小節了解到HashSet的底層存儲結構是HashMap,那麼它的增删也就是map的put和remove
1)增
public boolean add(E e) {return map.put(e, PRESENT)==null;}
直接put到map當中
2)删
public boolean remove(Object o) {return map.remove(o)==PRESENT;}
直接在map中移除即可,非常簡單
3 CopyOnWriteArraySet為什麼能支援并發?
在搞清楚_CopyOnWriteArraySet為什麼能支援并發_ 這個問題之前,我們先來想想以下幾個問題:
- HashSet對應的并發類為什麼叫CopyOnWriteArraySet,而不是叫CopyOnWriteHashSet呢?
- CopyOnWriteArraySet和CopyOnWriteArrayList有沒有關系?
我想一旦我們弄清楚上面兩個問題我們就是知道 CopyOnWriteArraySet為什麼能支援并發?
了
先來看看CopyOnWriteArraySet的部分源碼:
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private static final long serialVersionUID = 5457747651344034263L;
private final CopyOnWriteArrayList<E> al;
/**
* Creates an empty set.
*/
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
...
}
從源碼中神奇地發現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的增删(改查?)原理