Java集合---HashSet的源(yuan)碼分析
一(yi)、 HashSet概述：
HashSet實(shi)(shi)現Set接口，由哈希表（實(shi)(shi)際上是一個HashMap實(shi)(shi)例）支(zhi)持。它(ta)(ta)不(bu)保證set 的(de)迭代順序；特別是它(ta)(ta)不(bu)保證該(gai)順序恒久不(bu)變。此(ci)類(lei)允許使用null元素(su)。
二、 HashSet的實(shi)現：
對于HashSet而言，它是(shi)基于HashMap實現的，HashSet底層(ceng)使用(yong)(yong)HashMap來(lai)保存(cun)所(suo)有元素，因此HashSet 的實現比較(jiao)簡單，相(xiang)關(guan)HashSet的操作(zuo)，基本上都是(shi)直接調用(yong)(yong)底層(ceng)HashMap的相(xiang)關(guan)方(fang)法來(lai)完成，
HashSet的源(yuan)代(dai)碼如(ru)下(xia)：
1 public class HashSet<E>
2 extends AbstractSet<E>
3 implements Set<E>, Cloneable, java.io.Serializable
4{
5 static final long serialVersionUID = -5024744406713321676L;
6
7 // 底層使用HashMap來保存HashSet中所有元(yuan)素。
8 private transient HashMap<E,Object> map;
9
10 // 定義一個虛擬的Object對象作(zuo)為(wei)HashMap的value，將此(ci)對象定義為(wei)static final。
11 private static final Object PRESENT = new Object();
12
13 /**
14 * 默認的無參(can)構造(zao)器(qi)，構造(zao)一個空的HashSet。
15 *
16 * 實(shi)際(ji)底層會初始化一個空的HashMap，并使用默認初始容量為16和加載因子0.75。
17 */
18 public HashSet() {
19 map = new HashMap<E,Object>();
20 }
21
22 /**
23 * 構造(zao)一個包含(han)指定(ding)(ding)collection中(zhong)(zhong)的(de)(de)(de)元素(su)的(de)(de)(de)新(xin)set。
24 *
25 * 實際底(di)層使用默認的(de)(de)(de)加載因(yin)子0.75和足以包含(han)指定(ding)(ding)
26 * collection中(zhong)(zhong)所有元素(su)的(de)(de)(de)初始容量來創建(jian)一個HashMap。
27 * @param c 其(qi)中(zhong)(zhong)的(de)(de)(de)元素(su)將存放(fang)在此set中(zhong)(zhong)的(de)(de)(de)collection。
28 */
29 public HashSet(Collection<? extends E> c) {
30 map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
31 addAll(c);
32 }
33
34 /**
35 * 以(yi)指(zhi)定的(de)(de)initialCapacity和(he)loadFactor構(gou)造一(yi)(yi)個(ge)空(kong)的(de)(de)HashSet。
36 *
37 * 實際底層以(yi)相應(ying)的(de)(de)參數構(gou)造一(yi)(yi)個(ge)空(kong)的(de)(de)HashMap。
38 * @param initialCapacity 初(chu)始容(rong)量。
39 * @param loadFactor 加(jia)載因(yin)子(zi)。
40 */
41 public HashSet(int initialCapacity, float loadFactor) {
42 map = new HashMap<E,Object>(initialCapacity, loadFactor);
43 }
44
45 /**
46 * 以指定的(de)initialCapacity構造一個(ge)空(kong)的(de)HashSet。
47 *
48 * 實際(ji)底層(ceng)以相應的(de)參數(shu)及(ji)加載因子(zi)loadFactor為0.75構造一個(ge)空(kong)的(de)HashMap。
49 * @param initialCapacity 初始容量。
50 */
51 public HashSet(int initialCapacity) {
52 map = new HashMap<E,Object>(initialCapacity);
53 }
54
55 /**
56 * 以指定的(de)initialCapacity和loadFactor構造一個(ge)新的(de)空鏈接哈(ha)希(xi)集合(he)。
57 * 此構造函(han)數(shu)為包訪問權限(xian)，不對(dui)(dui)外公開，實(shi)(shi)際(ji)只(zhi)是(shi)是(shi)對(dui)(dui)LinkedHashSet的(de)支持。
58 *
59 * 實(shi)(shi)際(ji)底層(ceng)會以指定的(de)參數(shu)構造一個(ge)空LinkedHashMap實(shi)(shi)例來(lai)實(shi)(shi)現。
60 * @param initialCapacity 初始容量。
61 * @param loadFactor 加(jia)載因子。
62 * @param dummy 標記。
63 */
64 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
65 map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
66 }
67
68 /**
69 * 返(fan)回對此(ci)set中(zhong)(zhong)元(yuan)(yuan)素(su)(su)(su)進行(xing)迭代(dai)(dai)的(de)迭代(dai)(dai)器(qi)。返(fan)回元(yuan)(yuan)素(su)(su)(su)的(de)順序并不(bu)是特定的(de)。
70 *
71 * 底(di)層(ceng)(ceng)(ceng)實(shi)際調用底(di)層(ceng)(ceng)(ceng)HashMap的(de)keySet來返(fan)回所有(you)的(de)key。
72 * 可見HashSet中(zhong)(zhong)的(de)元(yuan)(yuan)素(su)(su)(su)，只(zhi)是存放(fang)在(zai)了底(di)層(ceng)(ceng)(ceng)HashMap的(de)key上，
73 * value使用一(yi)個static final的(de)Object對象標(biao)識。
74 * @return 對此(ci)set中(zhong)(zhong)元(yuan)(yuan)素(su)(su)(su)進行(xing)迭代(dai)(dai)的(de)Iterator。
75 */
76 public Iterator<E> iterator() {
77 return map.keySet().iterator();
78 }
79
80 /**
81 * 返(fan)回(hui)此set中(zhong)的(de)(de)(de)元(yuan)素(su)(su)的(de)(de)(de)數量（set的(de)(de)(de)容量）。
82 *
83 * 底層實際(ji)調用HashMap的(de)(de)(de)size()方法(fa)返(fan)回(hui)Entry的(de)(de)(de)數量，就(jiu)得到該Set中(zhong)元(yuan)素(su)(su)的(de)(de)(de)個(ge)數。
84 * @return 此set中(zhong)的(de)(de)(de)元(yuan)素(su)(su)的(de)(de)(de)數量（set的(de)(de)(de)容量）。
85 */
86 public int size() {
87 return map.size();
88 }
89
90 /**
91 * 如果此set不(bu)包含(han)任何元素，則返回true。
92 *
93 * 底層(ceng)實際調(diao)用(yong)HashMap的isEmpty()判(pan)斷(duan)該HashSet是否為空。
94 * @return 如果此set不(bu)包含(han)任何元素，則返回true。
95 */
96 public boolean isEmpty() {
97 return map.isEmpty();
98 }
99
100 /**
101 * 如(ru)果此set包(bao)(bao)含指(zhi)(zhi)定元(yuan)素(su)，則返(fan)回(hui)true。
102 * 更確切地講，當且僅(jin)當此set包(bao)(bao)含一個滿足(o==null ? e==null : o.equals(e))
103 * 的(de)e元(yuan)素(su)時，返(fan)回(hui)true。
104 *
105 * 底層(ceng)實際調(diao)用(yong)HashMap的(de)containsKey判斷是否包(bao)(bao)含指(zhi)(zhi)定key。
106 * @param o 在此set中的(de)存在已得到測試的(de)元(yuan)素(su)。
107 * @return 如(ru)果此set包(bao)(bao)含指(zhi)(zhi)定元(yuan)素(su)，則返(fan)回(hui)true。
108 */
109 public boolean contains(Object o) {
110 return map.containsKey(o);
111 }
112
113 /**
114 * 如果(guo)(guo)此(ci)set中(zhong)(zhong)尚未(wei)包含指定(ding)元(yuan)(yuan)素(su)(su)(su)，則(ze)添(tian)加(jia)(jia)指定(ding)元(yuan)(yuan)素(su)(su)(su)。
115 * 更確切(qie)地講(jiang)，如果(guo)(guo)此(ci) set 沒有包含滿足(e==null ? e2==null : e.equals(e2))
116 * 的(de)(de)元(yuan)(yuan)素(su)(su)(su)e2，則(ze)向(xiang)此(ci)set 添(tian)加(jia)(jia)指定(ding)的(de)(de)元(yuan)(yuan)素(su)(su)(su)e。
117 * 如果(guo)(guo)此(ci)set已包含該(gai)元(yuan)(yuan)素(su)(su)(su)，則(ze)該(gai)調(diao)用(yong)不更改(gai)set并返回(hui)(hui)(hui)false。
118 *
119 * 底(di)層實際(ji)將(jiang)(jiang)將(jiang)(jiang)該(gai)元(yuan)(yuan)素(su)(su)(su)作(zuo)為key放入HashMap。
120 * 由(you)于HashMap的(de)(de)put()方法(fa)添(tian)加(jia)(jia)key-value對時，當新放入HashMap的(de)(de)Entry中(zhong)(zhong)key
121 * 與集合(he)中(zhong)(zhong)原有Entry的(de)(de)key相同（hashCode()返回(hui)(hui)(hui)值相等(deng)，通過(guo)equals比較也(ye)(ye)返回(hui)(hui)(hui)true），
122 * 新添(tian)加(jia)(jia)的(de)(de)Entry的(de)(de)value會將(jiang)(jiang)覆(fu)蓋原來(lai)Entry的(de)(de)value，但key不會有任何改(gai)變，
123 * 因(yin)此(ci)如果(guo)(guo)向(xiang)HashSet中(zhong)(zhong)添(tian)加(jia)(jia)一個已經(jing)存在的(de)(de)元(yuan)(yuan)素(su)(su)(su)時，新添(tian)加(jia)(jia)的(de)(de)集合(he)元(yuan)(yuan)素(su)(su)(su)將(jiang)(jiang)不會被放入HashMap中(zhong)(zhong)，
124 * 原來(lai)的(de)(de)元(yuan)(yuan)素(su)(su)(su)也(ye)(ye)不會有任何改(gai)變，這(zhe)也(ye)(ye)就滿足了Set中(zhong)(zhong)元(yuan)(yuan)素(su)(su)(su)不重復的(de)(de)特性。
125 * @param e 將(jiang)(jiang)添(tian)加(jia)(jia)到此(ci)set中(zhong)(zhong)的(de)(de)元(yuan)(yuan)素(su)(su)(su)。
126 * @return 如果(guo)(guo)此(ci)set尚未(wei)包含指定(ding)元(yuan)(yuan)素(su)(su)(su)，則(ze)返回(hui)(hui)(hui)true。
127 */
128 public boolean add(E e) {
129 return map.put(e, PRESENT)==null;
130 }
131
132 /**
133 * 如(ru)(ru)果(guo)指(zhi)定(ding)元(yuan)(yuan)素(su)存在(zai)于此set中(zhong)，則將其移除。
134 * 更(geng)確切地講(jiang)，如(ru)(ru)果(guo)此set包(bao)含一個(ge)滿足(o==null ? e==null : o.equals(e))的元(yuan)(yuan)素(su)e，
135 * 則將其移除。如(ru)(ru)果(guo)此set已包(bao)含該元(yuan)(yuan)素(su)，則返(fan)(fan)回(hui)true
136 * （或者：如(ru)(ru)果(guo)此set因調(diao)用而發生(sheng)更(geng)改(gai)，則返(fan)(fan)回(hui)true）。（一旦調(diao)用返(fan)(fan)回(hui)，則此set不(bu)再包(bao)含該元(yuan)(yuan)素(su)）。
137 *
138 * 底層實際調(diao)用HashMap的remove方法刪(shan)除指(zhi)定(ding)Entry。
139 * @param o 如(ru)(ru)果(guo)存在(zai)于此set中(zhong)則需要(yao)將其移除的對象(xiang)。
140 * @return 如(ru)(ru)果(guo)set包(bao)含指(zhi)定(ding)元(yuan)(yuan)素(su)，則返(fan)(fan)回(hui)true。
141 */
142 public boolean remove(Object o) {
143 return map.remove(o)==PRESENT;
144 }
145
146 /**
147 * 從此(ci)set中移除所有(you)元素。此(ci)調用(yong)(yong)返回后(hou)，該set將為空。
148 *
149 * 底(di)層實(shi)際(ji)調用(yong)(yong)HashMap的clear方法清空Entry中所有(you)元素。
150 */
151 public void clear() {
152 map.clear();
153 }
154
155 /**
156 * 返回此(ci)HashSet實例的(de)淺表副(fu)本：并沒(mei)有復制這些元素本身。
157 *
158 * 底(di)層實際調用HashMap的(de)clone()方法，獲取HashMap的(de)淺表副(fu)本，并設置到 HashSet中。
159 */
160 public Object clone() {
161 try {
162 HashSet<E> newSet = (HashSet<E>) super.clone();
163 newSet.map = (HashMap<E, Object>) map.clone();
164 return newSet;
165 } catch (CloneNotSupportedException e) {
166 throw new InternalError();
167 }
168 }
}
三(san)、 相關(guan)說明：
對于HashSet中保存的對象，請注意正確重寫其equals和hashCode方法，以保證放入(ru)的對象的唯(wei)一性。