Collection (二)：Set 解析

Posted on | In | Visitors:

写在前面

  • 由于个人水平有限，故部分内容可能会出现错误，还请包涵

Set 接口

Set 也是一种用于存储元素的集合，但 Set 内的元素是无序且不重复的

Set 中没有特有的方法，直接继承自 Collection

相等性

引用到堆上同一个对象的两个引用是相等的。如果对两个引用调用 hashCode 方法，会得到相同的结果

如果对象所属的类没有覆盖 Object 的 hashCode方法 的话，hashCode 会返回每个对象特有的序号（Java 是依据对象的内存地址计算出的此序号），所以两个不同的对象的 hashCode 值是不可能相等的

hashCode 和 equals 方法的区别和联系

hashCode 和 equals 方法均在 Object 类中定义

equals (Object obj) 方法用来判断两个对象是否“相同”，如果“相同”则返回 true，否则返回 false。hashCode() 方法返回一个 int 数，在 Object 类中的默认实现是“将该对象的内部地址转换成一个整数返回”

若重写了 equals(Object obj) 方法，则有必要重写 hashCode() 方法

  • 一般一个类的对象如果会存储在 HashTable，HashSet，HashMap 等散列存储结构中，那么重写 equals 后最好也重写 hashCode，否则会导致存储数据的不唯一性（存储了两个 equals 相等的数据）

若 equals 返回 true，则 hashCode 返回的 int 值相等。但若 hashCode 返回的 int 值相等，equals 返回不一定为 true

hashCode 是为了提高在散列结构存储中查找的效率，在线性表中没有作用

同一对象在执行期间若已经存储在集合中，则不能修改影响 hashCode 值的相关信息，否则会导致内存泄露问题

如果想要让类的两个不同对象视为相等，就必须重写 Object 中的 hashCode 方法和 equals 方法

HashSet 类

1
2
3
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

HashSet 类的底层数据结构是 HashMap，即 HashSet 类的所有方法实际上都是通过 HashMap 类的方法实现的，故在此不作深究，具体可参考 Java Map 解析

1
2
// 默认初始容量为 16，负载因子为 0.75
private transient HashMap<E,Object> map;

而因为 Map 存储的是键-值对的元素，故 HashSet 类内部包含了一个类实例 PRESENT ，即 map 中的所有 value 都是这个 PRESENT

1
private static final Object PRESENT = new Object();

HashSet 的 clone 方法同样是浅拷贝

LinkedHashSet 类

1
2
3
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet 类的底层数据结构是 LinkedHashMap，具体可参考 Java Map 解析

LinkedHashSet 的构造函数都是通过调用 HashSet 的一个具有包访问权限的构造函数实现的

LinkedHashSet 的好处在于可以保证访问元素的顺序和插入元素的顺序相同

具体使用

1
2
3
4
5
6
7
8
9
10
Set<String> set = new HashSet<>(Arrays.asList("Java", "Python", "C", "PHP"));
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
	System.out.println(iterator.next());
}
Set<String> set2 = new LinkedHashSet<>(Arrays.asList("Java", "Python", "C", "PHP"));
Iterator<String> iterator2 = set2.iterator();
while (iterator2.hasNext()) {
	System.out.println(iterator2.next());
}

输出结果为

1
2
3
4
5
6
7
8
Java
C
PHP
Python
Java
Python
C
PHP

TreeSet 类

1
2
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet 类的底层数据结构是 TreeMap，具体可参考 Java Map 解析

TreeSet 的有点在于可以确保集合元素处于排序状态（排序规则可以自定义）

总结

Set 源码阅读十分简单，因为 Set 实现类的底层数据结构都是相应的 Map 实现类，故重点全放在 Map 源码中

作为 key 的对象要正确重写 equals 和 hashCode 方法

Set 更像一个功能被限制了的 Map