Java中的set是一个不包含重复元素的集合，确切地说，是不包含e1.equals(e2)的元素对。Set中允许添加null。Set不能保证集合里元素的顺序。

在往set中添加元素时，如果指定元素不存在，则添加成功。也就是说，如果set中不存在(e==null ? e1==null : e.queals(e1))的元素e1,则e1能添加到set中。

下面以set的一个实现类HashSet为例，简单介绍一下set不重复实现的原理：

  1. package com.darren.test.overide;
  2. public class CustomString {
  3. private String value;
  4. public CustomString() {
  5. this("");
  6. }
  7. public CustomString(String value) {
  8. this.value = value;
  9. }
  10. }
package com.darren.test.overide;

public class CustomString {

    private String value;

    public CustomString() {

        this("");

    }

    public CustomString(String value) {

        this.value = value;

    }

}
  1. package com.darren.test.overide;
  2. import java.util.HashSet;
  3. import java.util.Set;
  4. public class HashSetTest {
  5. public static void main(String[] args) {
  6. String a = new String("A");
  7. String b = new String("A");
  8. CustomString c = new CustomString("B");
  9. CustomString d = new CustomString("B");
  10. System.out.println("a.equals(b) == " + a.equals(b));
  11. System.out.println("c.equals(d) == " + c.equals(d));
  12. Set<Object> set = new HashSet<Object>();
  13. set.add(a);
  14. set.add(b);
  15. set.add(c);
  16. set.add(d);
  17. System.out.println("set.size() == " + set.size());
  18. for (Object object : set) {
  19. System.out.println(object);
  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. a.equals(b) == true
  2. c.equals(d) == false
  3. set.size() == 3
  4. com.darren.test.overide.CustomString@2c39d2
  5. A
  6. com.darren.test.overide.CustomString@5795ce
a.equals(b) == true

c.equals(d) == false

set.size() == 3

com.darren.test.overide.CustomString@2c39d2

A

com.darren.test.overide.CustomString@5795ce

也许你已经看出关键来了，没错就是equals方法。这么说还是不恰当，准确的说应该是equals和hashcode方法。为什么这么说呢，让我们改一改CustomString类在进行测试：

  1. package com.darren.test.overide;
  2. public class CustomString {
  3. private String value;
  4. public CustomString() {
  5. this("");
  6. }
  7. public CustomString(String value) {
  8. this.value = value;
  9. }
  10. @Override
  11. public boolean equals(Object obj) {
  12. if (this == obj) {
  13. return true;
  14. } else if (obj instanceof CustomString) {
  15. CustomString customString = (CustomString) obj;
  16. return customString.value.equals(value);
  17. } else {
  18. return false;
  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. a.equals(b) == true
  2. c.equals(d) == true
  3. set.size() == 3
  4. com.darren.test.overide.CustomString@12504e0
  5. A
  6. com.darren.test.overide.CustomString@1630eb6
a.equals(b) == true

c.equals(d) == true

set.size() == 3

com.darren.test.overide.CustomString@12504e0

A

com.darren.test.overide.CustomString@1630eb6

这次的equals返回值都为true，但是set的size还是3

让我们继续改

  1. package com.darren.test.overide;
  2. public class CustomString {
  3. private String value;
  4. public CustomString() {
  5. this("");
  6. }
  7. public CustomString(String value) {
  8. this.value = value;
  9. }
  10. @Override
  11. public int hashCode() {
  12. // return super.hashCode();
  13. return 1;
  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. a.equals(b) == true
  2. c.equals(d) == false
  3. set.size() == 3
  4. com.darren.test.overide.CustomString@1
  5. com.darren.test.overide.CustomString@1
  6. A
a.equals(b) == true

c.equals(d) == false

set.size() == 3

com.darren.test.overide.CustomString@1

com.darren.test.overide.CustomString@1

A

只重写hashCode方法，不重写equals方法也不行

最后再改一改

  1. package com.darren.test.overide;
  2. public class CustomString {
  3. private String value;
  4. public CustomString() {
  5. this("");
  6. }
  7. public CustomString(String value) {
  8. this.value = value;
  9. }
  10. @Override
  11. public boolean equals(Object obj) {
  12. if (this == obj) {
  13. return true;
  14. } else if (obj instanceof CustomString) {
  15. CustomString customString = (CustomString) obj;
  16. return customString.value.equals(value);
  17. } else {
  18. return false;
  19. }
  20. }
  21. @Override
  22. public int hashCode() {
  23. // return super.hashCode();
  24. return 1;
  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. a.equals(b) == true
  2. c.equals(d) == true
  3. set.size() == 2
  4. com.darren.test.overide.CustomString@1
  5. A
a.equals(b) == true

c.equals(d) == true

set.size() == 2

com.darren.test.overide.CustomString@1

A

可以了，证明需要重写equals方法和hashCode方法，来看原理：

java.lnag.Object中对hashCode的约定：

1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。

2. 如果两个对象根据equals(Object o)方法是相等的，则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。

3. 如果两个对象根据equals(Object o)方法是不相等的，则调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，则可能提高散列表的性能。

在HashSet中，基本的操作都是有HashMap底层实现的，因为HashSet底层是用HashMap存储数据的。当向HashSet中添加元素的时候，首先计算元素的hashcode值，然后用这个（元素的hashcode）%（HashMap集合的大小）+1计算出这个元素的存储位置，如果这个位置位空，就将元素添加进去；如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找一个空位添加。

如下是HashSet的部分源码：

    1. package java.util;
    2. public class HashSet<E> extends AbstractSet<E>
    3. implements Set<E>, Cloneable, java.io.Serializable
    4. {
    5. static final long serialVersionUID = -5024744406713321676L;
    6. // 底层使用HashMap来保存HashSet中所有元素。
    7. private transient HashMap<E,Object> map;
    8. // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
    9. private static final Object PRESENT = new Object();
    10. /**
    11. * 默认的无参构造器，构造一个空的HashSet。
    12. *
    13. * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
    14. */
    15. public HashSet() {
    16. map = new HashMap<E,Object>();
    17. }
    18. /**
    19. * 构造一个包含指定collection中的元素的新set。
    20. *
    21. * 实际底层使用默认的加载因子0.75和足以包含指定
    22. * collection中所有元素的初始容量来创建一个HashMap。
    23. * @param c 其中的元素将存放在此set中的collection。
    24. */
    25. public HashSet(Collection< extends E> c) {
    26. map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
    27. addAll(c);
    28. }
    29. /**
    30. * 以指定的initialCapacity和loadFactor构造一个空的HashSet。
    31. *
    32. * 实际底层以相应的参数构造一个空的HashMap。
    33. * @param initialCapacity 初始容量。
    34. * @param loadFactor 加载因子。
    35. */
    36. public HashSet(int initialCapacity, float loadFactor) {
    37. map = new HashMap<E,Object>(initialCapacity, loadFactor);
    38. }
    39. /**
    40. * 以指定的initialCapacity构造一个空的HashSet。
    41. *
    42. * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
    43. * @param initialCapacity 初始容量。
    44. */
    45. public HashSet(int initialCapacity) {
    46. map = new HashMap<E,Object>(initialCapacity);
    47. }
    48. /**
    49. * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
    50. * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。
    51. *
    52. * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
    53. * @param initialCapacity 初始容量。
    54. * @param loadFactor 加载因子。
    55. * @param dummy 标记。
    56. */
    57. HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    58. map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    59. }
    60. /**
    61. * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。
    62. *
    63. * 底层实际调用底层HashMap的keySet来返回所有的key。
    64. * 可见HashSet中的元素，只是存放在了底层HashMap的key上，
    65. * value使用一个static final的Object对象标识。
    66. * @return 对此set中元素进行迭代的Iterator。
    67. */
    68. @Override
    69. public Iterator<E> iterator() {
    70. return map.keySet().iterator();
    71. }
    72. /**
    73. * 返回此set中的元素的数量（set的容量）。
    74. *
    75. * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。
    76. * @return 此set中的元素的数量（set的容量）。
    77. */
    78. @Override
    79. public int size() {
    80. return map.size();
    81. }
    82. /**
    83. * 如果此set不包含任何元素，则返回true。
    84. *
    85. * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。
    86. * @return 如果此set不包含任何元素，则返回true。
    87. */
    88. @Override
    89. public boolean isEmpty() {
    90. return map.isEmpty();
    91. }
    92. /**
    93. * 如果此set包含指定元素，则返回true。
    94. * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))
    95. * 的e元素时，返回true。
    96. *
    97. * 底层实际调用HashMap的containsKey判断是否包含指定key。
    98. * @param o 在此set中的存在已得到测试的元素。
    99. * @return 如果此set包含指定元素，则返回true。
    100. */
    101. @Override
    102. public boolean contains(Object o) {
    103. return map.containsKey(o);
    104. }
    105. /**
    106. * 如果此set中尚未包含指定元素，则添加指定元素。
    107. * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))
    108. * 的元素e2，则向此set 添加指定的元素e。
    109. * 如果此set已包含该元素，则该调用不更改set并返回false。
    110. *
    111. * 底层实际将将该元素作为key放入HashMap。
    112. * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key
    113. * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true），
    114. * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变，
    115. * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，
    116. * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。
    117. * @param e 将添加到此set中的元素。
    118. * @return 如果此set尚未包含指定元素，则返回true。
    119. */
    120. @Override
    121. public boolean add(E e) {
    122. return map.put(e, PRESENT)==null;
    123. }
    124. /**
    125. * 如果指定元素存在于此set中，则将其移除。
    126. * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，
    127. * 则将其移除。如果此set已包含该元素，则返回true
    128. * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。
    129. *
    130. * 底层实际调用HashMap的remove方法删除指定Entry。
    131. * @param o 如果存在于此set中则需要将其移除的对象。
    132. * @return 如果set包含指定元素，则返回true。
    133. */
    134. @Override
    135. public boolean remove(Object o) {
    136. return map.remove(o)==PRESENT;
    137. }
    138. /**
    139. * 从此set中移除所有元素。此调用返回后，该set将为空。
    140. *
    141. * 底层实际调用HashMap的clear方法清空Entry中所有元素。
    142. */
    143. @Override
    144. public void clear() {
    145. map.clear();
    146. }
    147. }
												


																

最新文章
	

    
						
  1. Android应用开发基础之十二：版本控制
		
    2. 
						
  2. 根据html容器大小和显示文字多少调节字体大小
		
    3. 
						
  3. Debian上安装Apache＋Django全过程
		
    4. 
						
  4. 一点一滴之NHibernate
		
    5. 
						
  5. Beyond MySQL --Branching the popular database--转载
		
    6. 
						
  6. 实战RPM包制作
		
    7. 
						
  7. LINUX 内核代码  errno 错误代码提示 /include/asm/errno.h
		
    8. 
						
  8. mac ssd开启trim
		
    9. 
						
  9. iPhone/iPad全屏截图与区域截图的几种方法
		
    10. 
						
  10. JS给元素循环添加事件的问题
		
    11. 
						
  11. 基于Visual C++2013拆解世界五百强面试题--题12-进制转换
		
    12. 
						
  12. linux 内核的rt_mutex 锁操作实现的临界区
		
    13. 
						
  13. curl模拟请求常用参数
		
    14. 
						
  14. Linux网卡调优篇-禁用ipv6与优化socket缓冲区大小
		
    15. 
						
  15. Dockerfile详解（三）
		
    16. 
						
  16. 强势龙头股的 VOLM5/35/135 走势，可作为逃顶参考
		
    17. 
						
  17. python三大框架之一（flask介绍）
		
    18. 
						
  18. DXP 板层
		
    19. 
						
  19. Linux内核分析——第二章  从内核出发
		
    20. 
						
  20. poj2018（高精度二分+dp）
		
    21. 
		

	


热门文章
	

    
									
  1. 【Qt编程】QWT在QtCreator中的安装与使用
			
    2. 
						
  2. Xcode出现may cause a leak的解决
			
    3. 
						
  3. 如何使用VS2013本地C++单元测试框架
			
    4. 
						
  4. Leetcode_234_Palindrome Linked List
			
    5. 
						
  5. OpenCV——照亮边缘
			
    6. 
						
  6. android自定义view实现公章效果
			
    7. 
						
  7. Ubuntu安装java的最简单的命令行方式
			
    8. 
						
  8. Hibernate与Mybatis的比较
			
    9. 
						
  9. CF959F
			
    10. 
						
  10. Python 可视化TVTK CubeSource管线初使用
			
    11.