HashSet源码解析
前面我們花了一定的篇幅學(xué)習(xí)了HashMap的一些底層原理，以及簡單了解了HashSet和HashMap兩種集合的淵源，現(xiàn)在我們從HashSet源碼入手，來學(xué)習(xí)HashSet更細(xì)節(jié)的地方。
對于HashSet而言，它是基于HashMap實現(xiàn)的。HashSet底層采用HashMap來保存元素，因此HashSet底層其實比較簡單。
package java.util;
public class HashSet<E>
? ? extends AbstractSet<E>
? ? implements Set<E>, Cloneable, java.io.Serializable
{
? ? static final long serialVersionUID = -5024744406713321676L;
? ? // HashSet是通過map(HashMap對象)保存內(nèi)容的
? ? private transient HashMap<E,Object> map;
? ? // 定義一個虛擬的Object PRESENT是向map中插入key-value對應(yīng)的value
? ? // 因為HashSet中只需要用到key，而HashMap是key-value鍵值對；
? ? // 所以，向map中添加鍵值對時，鍵值對的值固定是PRESENT
? ? private static final Object PRESENT = new Object();
? ? // 默認(rèn)構(gòu)造函數(shù) 底層創(chuàng)建一個HashMap
? ? public HashSet() {
? ? ? ? // 調(diào)用HashMap的默認(rèn)構(gòu)造函數(shù)，創(chuàng)建map
? ? ? ? map = new HashMap<E,Object>();
? ? }
? ? // 帶集合的構(gòu)造函數(shù)
? ? public HashSet(Collection<? extends E> c) {
? ? ? ? // 創(chuàng)建map。
? ? ? ? // 為什么要調(diào)用Math.max((int) (c.size()/.75f) + 1, 16)，從 (c.size()/.75f) + 1 和 16 中選擇一個比較大的樹呢？ ? ? ? ?
? ? ? ? // 首先，說明(c.size()/.75f) + 1
? ? ? ? // ? 因為從HashMap的效率(時間成本和空間成本)考慮，HashMap的加載因子是0.75。
? ? ? ? // ? 當(dāng)HashMap的“閾值”(閾值=HashMap總的大小*加載因子) < “HashMap實際大小”時，
? ? ? ? // ? 就需要將HashMap的容量翻倍。
? ? ? ? // ? 所以，(c.size()/.75f) + 1 計算出來的正好是總的空間大小。
? ? ? ? // 接下來，說明為什么是 16 。
? ? ? ? // ? HashMap的總的大小，必須是2的指數(shù)倍。若創(chuàng)建HashMap時，指定的大小不是2的指數(shù)倍；
? ? ? ? // ? HashMap的構(gòu)造函數(shù)中也會重新計算，找出比“指定大小”大的最小的2的指數(shù)倍的數(shù)。
? ? ? ? // ? 所以，這里指定為16是從性能考慮。避免重復(fù)計算。
? ? ? ? map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
? ? ? ? // 將集合(c)中的全部元素添加到HashSet中
? ? ? ? addAll(c);
? ? }
? ? // 指定HashSet初始容量和加載因子的構(gòu)造函數(shù)
? ? public HashSet(int initialCapacity, float loadFactor) {
? ? ? ? map = new HashMap<E,Object>(initialCapacity, loadFactor);
? ? }
? ? // 指定HashSet初始容量的構(gòu)造函數(shù)
? ? public HashSet(int initialCapacity) {
? ? ? ? map = new HashMap<E,Object>(initialCapacity);
? ? }
? ? HashSet(int initialCapacity, float loadFactor, boolean dummy) {
? ? ? ? map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
? ? }
? ? // 返回HashSet的迭代器
? ? public Iterator<E> iterator() {
? ? ? ? // 實際上返回的是HashMap的“key集合的迭代器”
? ? ? ? return map.keySet().iterator();
? ? }
? ?//調(diào)用HashMap的size()方法返回Entry的數(shù)量，得到該Set里元素的個數(shù)
? ? public int size() {
? ? ? ? return map.size();
? ? }
? ?//調(diào)用HashMap的isEmpty()來判斷HaspSet是否為空
? ?//HashMap為null。對應(yīng)的HashSet也為空
? ? public boolean isEmpty() {
? ? ? ? return map.isEmpty();
? ? }
? ? //調(diào)用HashMap的containsKey判斷是否包含指定的key
? ? //HashSet的所有元素就是通過HashMap的key來保存的
? ? public boolean contains(Object o) {
? ? ? ? return map.containsKey(o);
? ? }
? ? // 將元素(e)添加到HashSet中，也就是將元素作為Key放入HashMap中
? ? public boolean add(E e) {
? ? ? ? return map.put(e, PRESENT)==null;
? ? }
? ? // 刪除HashSet中的元素(o)，其實是在HashMap中刪除了以o為key的Entry
? ? public boolean remove(Object o) {
? ? ? ? return map.remove(o)==PRESENT;
? ? }
? ? ?//清空HashMap的clear方法清空所有Entry
? ? public void clear() {
? ? ? ? map.clear();
? ? }
? ? // 克隆一個HashSet，并返回Object對象
? ? public Object clone() {
? ? ? ? try {
? ? ? ? ? ? HashSet<E> newSet = (HashSet<E>) super.clone();
? ? ? ? ? ? newSet.map = (HashMap<E, Object>) map.clone();
? ? ? ? ? ? return newSet;
? ? ? ? } catch (CloneNotSupportedException e) {
? ? ? ? ? ? throw new InternalError();
? ? ? ? }
? ? }
? ? // java.io.Serializable的寫入函數(shù)
? ? // 將HashSet的“總的容量，加載因子，實際容量，所有的元素”都寫入到輸出流中
? ? 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 (Iterator i=map.keySet().iterator(); i.hasNext(); )
? ? ? ? ? ? s.writeObject(i.next());
? ? }
? ? // java.io.Serializable的讀取函數(shù)
? ? // 將HashSet的“總的容量，加載因子，實際容量，所有的元素”依次讀出
? ? private void readObject(java.io.ObjectInputStream s)
? ? ? ? throws java.io.IOException, ClassNotFoundException {
? ? ? ? // Read in any hidden serialization magic
? ? ? ? s.defaultReadObject();
? ? ? ? // Read in HashMap capacity and load factor and create backing HashMap
? ? ? ? int capacity = s.readInt();
? ? ? ? float loadFactor = s.readFloat();
? ? ? ? map = (((HashSet)this) instanceof LinkedHashSet ?
? ? ? ? ? ? ? ?new LinkedHashMap<E,Object>(capacity, loadFactor) :
? ? ? ? ? ? ? ?new HashMap<E,Object>(capacity, loadFactor));
? ? ? ? // Read in size
? ? ? ? int size = s.readInt();
? ? ? ? // Read in all elements in the proper order.
? ? ? ? for (int i=0; i<size; i++) {
? ? ? ? ? ? E e = (E) s.readObject();
? ? ? ? ? ? map.put(e, PRESENT);
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
從上述HashSet源代碼可以看出，它其實就是一個對HashMap的封裝而已。所有放入HashSet中的集合元素實際上由HashMap的key來保存，而HashMap的value則存儲了一個PRESENT，它是一個靜態(tài)的Object對象。
HashSet的絕大部分方法都是通過調(diào)用HashMap的方法來實現(xiàn)的，因此HashSet和HashMap兩個集合在實現(xiàn)本質(zhì)上是相同的。
根據(jù)HashMap的一個特性: 將一個key-value對放入HashMap中時，首先根據(jù)key的hashCode()返回值決定該Entry的存儲位置，如果兩個key的hash值相同，那么它們的存儲位置相同。如果這個兩個key的equalus比較返回true。那么新添加的Entry的value會覆蓋原來的Entry的value，key不會覆蓋。因此,如果向HashSet中添加一個已經(jīng)存在的元素，新添加的集合元素不會覆蓋原來已有的集合元素。
現(xiàn)在我們通過一個實際的例子來看看是否真正理解了HashMap和HashSet存儲元素的細(xì)節(jié):
class Name
{
? ? private String first;
? ? private String last;
? ? public Name(String first, String last)?
? ? {
? ? ? ? this.first = first;
? ? ? ? this.last = last;
? ? }
? ? public boolean equals(Object o)?
? ? {
? ? ? ? if (this == o)
? ? ? ? {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? if (o.getClass() == Name.class)
? ? ? ? {
? ? ? ? ? ? Name n = (Name)o;
? ? ? ? ? ? return n.first.equals(first)
? ? ? ? ? ? ? ? && n.last.equals(last);
? ? ? ? }
? ? ? ? return false;
? ? }
}
public class HashSetTest
{
? ? public static void main(String[] args)?
? ? {
? ? ? ? Set<Name> s = new HashSet<Name>();
? ? ? ? s.add(new Name("abc", "123"));
? ? ? ? System.out.println(
? ? ? ? ? ? s.contains(new Name("abc", "123")));
? ? }?
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
上面程序中向HashSet里添加了一個new Name(“abc”,”123”)對象之后，立即通過程序判斷該HashSet里是否包含一個new Name(“abc”,”123”)對象。粗看上去，很容易以為該程序會輸出true。
實際上會輸出false。因為HashSet判斷兩個對象相等的標(biāo)準(zhǔn)是想通過hashCode()方法計算出其hash值，當(dāng)hash值相同的時候才繼續(xù)判斷equals()方法。而如上程序我們并沒有重寫hashCode()方法。所以兩個Name類的hash值并不相同，因此HashSet會把其當(dāng)成兩個對象來處理。
所以，當(dāng)我們要將一個類作為HashMap的key或者存儲在HashSet的時候。通過重寫hashCode()和equals(Object object)方法很重要，并且保證這兩個方法的返回值一致。當(dāng)兩個類的hashCode()返回一致時，應(yīng)該保證equasl()方法也返回true。當(dāng)給上述Name類增加如下方法:
public void hashCode(){
return first.hashCode()+last.hashCode();
}
1
2
3
4
此時我們測試的方法會返回true。
---------------------?
作者：不能說的秘密go?
來源：CSDN?
原文：https://blog.csdn.net/canot/article/details/51240251?
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接！
總結(jié)
以上是生活随笔為你收集整理的HashSet源码解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 源码分析-HashSet、LinkedH
- 下一篇： java集合（6）：TreeMap源码分