前言
這篇文章的目的如下：
- HashSet是如何保證元素的不重復(fù)和無序
- HashSet的增刪（改查？）原理
- CopyOnWriteArraySet支持并發(fā)的原理
- CopyOnWriteArraySet的增刪（改查？）原理
如果不想看分析過程，可直接拉到文章末尾看結(jié)論
先來看看 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();
}
我們從以上接口發(fā)現(xiàn)Set并沒有g(shù)et和set方法，也就是沒有查和改，為什么呢？原因如下：
- 因?yàn)镾et是無序的，沒有通過index來進(jìn)行查詢
- 同樣是因?yàn)镾et是無序的，也就是沒有辦法通過Index來進(jìn)行修改
1 HashSet如何保證元素不重復(fù)？
要弄清楚HashSet如何保證里面的元素不重復(fù)，得從以下兩個(gè)方面入手：
- 它底層的存儲(chǔ)結(jié)構(gòu)是什么？
- 插入時(shí)是如何判斷元素是否存在？
當(dāng)我們弄清楚上面兩個(gè)問題之后我們也可以明白HashSet為什么是無序的了。
1）HashSet的底層存儲(chǔ)邏輯
且看源碼：
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的底層存儲(chǔ)結(jié)構(gòu)是一個(gè)HashMap，并且HashSet的元素作為該Map的Key進(jìn)行存儲(chǔ)，HashMap的Key的存儲(chǔ)是無序并且不可重復(fù)，這就解釋了HashSet中如何保證元素不重復(fù)
2）插入邏輯
public boolean add(E e) {return map.put(e, PRESENT)==null;}
直接put到map當(dāng)中
3）總結(jié)
由以上內(nèi)容我們可以知道HashSet的底層存儲(chǔ)結(jié)構(gòu)是HashMap，并且插入到HashSet中元素作為map的key進(jìn)行存儲(chǔ)，這就保證HashSet的一下特點(diǎn)：
- HashSet中的元素不重復(fù)的
- HashSet中的元素是無序的
2 HashSet增刪（改查？）原理
我們從上一小節(jié)了解到HashSet的底層存儲(chǔ)結(jié)構(gòu)是HashMap，那么它的增刪也就是map的put和remove
1）增
public boolean add(E e) {return map.put(e, PRESENT)==null;}
直接put到map當(dāng)中
2）刪
public boolean remove(Object o) {return map.remove(o)==PRESENT;}
直接在map中移除即可，非常簡(jiǎn)單
3 CopyOnWriteArraySet為什么能支持并發(fā)？
在搞清楚CopyOnWriteArraySet為什么能支持并發(fā) 這個(gè)問題之前，我們先來想想以下幾個(gè)問題：
- HashSet對(duì)應(yīng)的并發(fā)類為什么叫CopyOnWriteArraySet，而不是叫CopyOnWriteHashSet呢？
- CopyOnWriteArraySet和CopyOnWriteArrayList有沒有關(guān)系？
我想一旦我們弄清楚上面兩個(gè)問題我們就是知道 CopyOnWriteArraySet為什么能支持并發(fā)？
了
先來看看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>();
}
...
}
從源碼中神奇地發(fā)現(xiàn)CopyOnWriteArraySet的底層存儲(chǔ)結(jié)構(gòu)竟然是CopyOnWriteArrayList，那么我們就可以知道它的名字的由來了，并且知道它支持并發(fā)的原理跟CopyOnWriteArrayList是一樣的。
4 CopyOnWriteArraySet的增刪（改查？）原理
1）增
public boolean add(E e) {
return al.addIfAbsent(e);
}
看方法名我們就是如果CopyOnWriteArrayList中不存在某元素才會(huì)添加成功
2）刪
public boolean remove(Object o) {
return al.remove(o);
}
直接從CopyOnWriteArrayList中移除
5 總結(jié)
- HashSet是如何保證元素的不重復(fù)和無序
答：因?yàn)镠ashSet的底層存儲(chǔ)結(jié)構(gòu)是HashMap，并且HashSet中的元素是作為Map的Key存儲(chǔ)到Map中，所以HashMap中Key是不重復(fù)且無序，所以HashSet中的元素也就是不重復(fù)和無序的
- HashSet的增刪（改查？）原理
HashSet的增刪原理很簡(jiǎn)單，就是map的put和remove，為什么沒有改查呢？那是因?yàn)镠ashSet中的元素是無序的，沒辦法根據(jù)索引進(jìn)行查詢和修改
- CopyOnWriteArraySet支持并發(fā)的原理
CopyOnWriteArraySet之所以叫CopyOnWriteArraySet，是因?yàn)樗牡讓哟鎯?chǔ)結(jié)構(gòu)是CopyOnWriteArrayList，同時(shí)也就是保證了它的并發(fā)安全性
- CopyOnWriteArraySet的增刪（改查？）原理
CopyOnWriteArraySet繼承了AbstractSet，跟HashSet一樣只有增刪，沒有改查，增刪原理也就是調(diào)用CopyOnWriteArrayList的增刪方法，只不過增的時(shí)候需要判斷一下List中是否存儲(chǔ)該元素
