Java中的set是一個不包含重復元素的集合，確切地說，是不包含e1.equals(e2)的元素對。Set中允許添加null。Set不能保證集合里元素的順序。
在往set中添加元素時，如果指定元素不存在，則添加成功。也就是說，如果set中不存在(e==null?e1==null:e.queals(e1))的元素e1,則e1能添加到set中。
下面以set的一個實現類HashSet為例，簡單介紹一下set不重復實現的原理：
|
1
2
3
4
5
6
7
8
9
10
|
package com.darren.test.overide;public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; }} |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
package com.darren.test.overide;import java.util.HashSet;import java.util.Set;public class HashSetTest { public static void main(String[] args) { String a = new String("A"); String b = new String("A"); CustomString c = new CustomString("B"); CustomString d = new CustomString("B"); System.out.println("a.equals(b) == " + a.equals(b)); System.out.println("c.equals(d) == " + c.equals(d)); Set<Object> set = new HashSet<Object>(); set.add(a); set.add(b); set.add(c); set.add(d); System.out.println("set.size() == " + set.size()); for (Object object : set) { System.out.println(object); } }} |
運行結果如下：
|
1
2
3
4
5
6
|
a.equals(b) == truec.equals(d) == falseset.size() == 3com.darren.test.overide.CustomString@2c39d2A com.darren.test.overide.CustomString@5795ce |
也許你已經看出關鍵來了，沒錯就是equals方法。這么說還是不恰當，準確的說應該是equals和hashcode方法。為什么這么說呢，讓我們改一改CustomString類在進行測試：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
package com.darren.test.overide;public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } @Override public Boolean equals(Object obj) { if (this == obj) { return true; } else if (obj instanceof CustomString) { CustomString customString = (CustomString) obj; return customString.value.equals(value); } else { return false; } }} |
測試結果：
|
1
2
3
4
5
6
|
a.equals(b) == truec.equals(d) == trueset.size() == 3com.darren.test.overide.CustomString@12504e0A com.darren.test.overide.CustomString@1630eb6 |
這次的equals返回值都為true，但是set的size還是3
讓我們繼續改
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package com.darren.test.overide;public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } @Override public int hashCode() { // return super.hashCode(); return 1; }} |
再看結果：
|
1
2
3
4
5
6
|
a.equals(b) == truec.equals(d) == falseset.size() == 3com.darren.test.overide.CustomString@1com.darren.test.overide.CustomString@1A |
只重寫hashCode方法，不重寫equals方法也不行
最后再改一改
|
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
|
package com.darren.test.overide;public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } @Override public Boolean equals(Object obj) { if (this == obj) { return true; } else if (obj instanceof CustomString) { CustomString customString = (CustomString) obj; return customString.value.equals(value); } else { return false; } } @Override public int hashCode() { // return super.hashCode(); return 1; }} |
最后結果：
|
1
2
3
4
5
|
a.equals(b) == truec.equals(d) == trueset.size() == 2com.darren.test.overide.CustomString@1A |
可以了，證明需要重寫equals方法和hashCode方法，來看原理：
java.lnag.Object中對hashCode的約定：
1.在一個應用程序執行期間，如果一個對象的equals方法做比較所用到的信息沒有被修改的話，則對該對象調用hashCode方法多次，它必須始終如一地返回同一個整數。
2.如果兩個對象根據equals(Objecto)方法是相等的，則調用這兩個對象中任一對象的hashCode方法必須產生相同的整數結果。
3.如果兩個對象根據equals(Objecto)方法是不相等的，則調用這兩個對象中任一個對象的hashCode方法，不要求產生不同的整數結果。但如果能不同，則可能提高散列表的性能。
在HashSet中，基本的操作都是有HashMap底層實現的，因為HashSet底層是用HashMap存儲數據的。當向HashSet中添加元素的時候，首先計算元素的hashcode值，然后用這個（元素的hashcode）%（HashMap集合的大?。?1計算出這個元素的存儲位置，如果這個位置位空，就將元素添加進去；如果不為空，則用equals方法比較元素是否相等，相等就不添加，否則找一個空位添加。
如下是HashSet的部分源碼：
|
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
144
145
146
147
|
package java.util;public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; // 底層使用HashMap來保存HashSet中所有元素。 private transient HashMap<E,Object> map; // 定義一個虛擬的Object對象作為HashMap的value，將此對象定義為static final。 private static final Object PRESENT = new Object(); /** * 默認的無參構造器，構造一個空的HashSet。 * * 實際底層會初始化一個空的HashMap，并使用默認初始容量為16和加載因子0.75。 */ public HashSet() { map = new HashMap<E,Object>(); } /** * 構造一個包含指定collection中的元素的新set。 * * 實際底層使用默認的加載因子0.75和足以包含指定 * collection中所有元素的初始容量來創建一個HashMap。 * @param c 其中的元素將存放在此set中的collection。 */ public HashSet(Collection< extends E> c) { map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } /** * 以指定的initialCapacity和loadFactor構造一個空的HashSet。 * * 實際底層以相應的參數構造一個空的HashMap。 * @param initialCapacity 初始容量。 * @param loadFactor 加載因子。 */ public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<E,Object>(initialCapacity, loadFactor); } /** * 以指定的initialCapacity構造一個空的HashSet。 * * 實際底層以相應的參數及加載因子loadFactor為0.75構造一個空的HashMap。 * @param initialCapacity 初始容量。 */ public HashSet(int initialCapacity) { map = new HashMap<E,Object>(initialCapacity); } /** * 以指定的initialCapacity和loadFactor構造一個新的空鏈接哈希集合。 * 此構造函數為包訪問權限，不對外公開，實際只是是對LinkedHashSet的支持。 * * 實際底層會以指定的參數構造一個空LinkedHashMap實例來實現。 * @param initialCapacity 初始容量。 * @param loadFactor 加載因子。 * @param dummy 標記。 */ HashSet(int initialCapacity, float loadFactor, Boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor); } /** * 返回對此set中元素進行迭代的迭代器。返回元素的順序并不是特定的。 * * 底層實際調用底層HashMap的keySet來返回所有的key。 * 可見HashSet中的元素，只是存放在了底層HashMap的key上， * value使用一個static final的Object對象標識。 * @return 對此set中元素進行迭代的Iterator。 */ @Override public Iterator<E> iterator() { return map.keySet().iterator(); } /** * 返回此set中的元素的數量（set的容量）。 * * 底層實際調用HashMap的size()方法返回Entry的數量，就得到該Set中元素的個數。 * @return 此set中的元素的數量（set的容量）。 */ @Override public int size() { return map.size(); } /** * 如果此set不包含任何元素，則返回true。 * * 底層實際調用HashMap的isEmpty()判斷該HashSet是否為空。 * @return 如果此set不包含任何元素，則返回true。 */ @Override public Boolean isEmpty() { return map.isEmpty(); } /** * 如果此set包含指定元素，則返回true。 * 更確切地講，當且僅當此set包含一個滿足(o==null ? e==null : o.equals(e)) * 的e元素時，返回true。 * * 底層實際調用HashMap的containsKey判斷是否包含指定key。 * @param o 在此set中的存在已得到測試的元素。 * @return 如果此set包含指定元素，則返回true。 */ @Override public Boolean contains(Object o) { return map.containsKey(o); } /** * 如果此set中尚未包含指定元素，則添加指定元素。 * 更確切地講，如果此 set 沒有包含滿足(e==null ? e2==null : e.equals(e2)) * 的元素e2，則向此set 添加指定的元素e。 * 如果此set已包含該元素，則該調用不更改set并返回false。 * * 底層實際將將該元素作為key放入HashMap。 * 由于HashMap的put()方法添加key-value對時，當新放入HashMap的Entry中key * 與集合中原有Entry的key相同（hashCode()返回值相等，通過equals比較也返回true）， * 新添加的Entry的value會將覆蓋原來Entry的value，但key不會有任何改變， * 因此如果向HashSet中添加一個已經存在的元素時，新添加的集合元素將不會被放入HashMap中， * 原來的元素也不會有任何改變，這也就滿足了Set中元素不重復的特性。 * @param e 將添加到此set中的元素。 * @return 如果此set尚未包含指定元素，則返回true。 */ @Override public Boolean add(E e) { return map.put(e, PRESENT)==null; } /** * 如果指定元素存在于此set中，則將其移除。 * 更確切地講，如果此set包含一個滿足(o==null ? e==null : o.equals(e))的元素e， * 則將其移除。如果此set已包含該元素，則返回true * （或者：如果此set因調用而發生更改，則返回true）。（一旦調用返回，則此set不再包含該元素）。 * * 底層實際調用HashMap的remove方法刪除指定Entry。 * @param o 如果存在于此set中則需要將其移除的對象。 * @return 如果set包含指定元素，則返回true。 */ @Override public Boolean remove(Object o) { return map.remove(o)==PRESENT; } /** * 從此set中移除所有元素。此調用返回后，該set將為空。 * * 底層實際調用HashMap的clear方法清空Entry中所有元素。 */ @Override public void clear() { map.clear(); }} |
總結
以上就是本文關于hashset去除重復值原理實例解析的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/zpf336/article/details/42397415
