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
