Java基础-Collection子接口之Set接口
作者：尹正杰
版权声明：原创作品，谢绝转载！否则将追究法律责任。
学习Collection接口时，记得Collection中可以存放重复元素，也可以不存放重复元素，那么我们知道List中是可以存放重复元素的。那么不重复元素给哪里存放呢？那就是Set接口，它里面的集合，所存储的元素就是不重复的。
一.Set接口的特点
一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。正如其名称所暗示的，此接口模仿了数学上的 set 抽象。在所有构造方法以及 add、equals 和 hashCode 方法的协定上，Set 接口还加入了其他规定，这些规定超出了从 Collection 接口所继承的内容。出于方便考虑，它还包括了其他继承方法的声明（这些声明的规范已经专门针对 Set 接口进行了修改，但是没有包含任何其他的规定）。
Set集合有多个子类，这么我们介绍其中的HashSet，LinkedHashSet这两个集合。Set结合取出元素的方式可以采用迭代器和增强for。
二.HashSet集合介绍
此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 总结HashSet有以下结果特点：
1>.无序集合，也就是说存取元素和取出元素的顺序不一定是相同的；
2>.没有索引；
3>.不存储重复元素；
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
EMAIL:y1053419035@qq.com
*/ package cn.org.yinzhengjie.note; import java.util.HashSet;
import java.util.Iterator;
import java.util.Set; public class HashSetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
set.add("yinzhengjie");
set.add("尹正杰");
set.add("2018");
set.add("yinzhengjie"); //第二次添加同一个元素时，并不会放入HashSet集合中。
set.add("java");
set.add("Big Data"); //用迭代器进行遍历
System.out.println("第一种遍历方式");
Iterator<String> it = set.iterator();
while(it.hasNext()) {
System.out.println("\t"+it.next());
} System.out.println("第二种遍历方式");
for (String string : set) {
System.out.println("\t"+string);
}
}
} /*
以上代码执行结果如下：
第一种遍历方式
尹正杰
2018
java
Big Data
yinzhengjie
第二种遍历方式
尹正杰
2018
java
Big Data
yinzhengjie
*/
三.哈希表的数据结构
哈希表其实就是链表和数组的结合体。哈希表底层使用的也是数组机制，数组中也存放对象，而这些对象往数组中存放时的位置比较特殊，当需要把这些对象给数组中存放时，那么会根据这些对象的特有数据结合相应的算法，计算出这个对象在数组中的位置，然后把这个对象存放在数组中。而这样的数组就称为哈希数组，即就是哈希表。
当向哈希表中存放元素时，需要根据元素的特有数据结合相应的算法，这个算法其实就是Object类中的hashCode方法。由于任何对象都是Object类的子类，所以任何对象有拥有这个方法。即就是在给哈希表中存放对象时，会调用对象的hashCode方法，算出对象在表中的存放位置，这里需要注意，如果两个对象hashCode方法算出结果一样，这样现象称为哈希冲突，这时会调用对象的equals方法，比较这两个对象是不是同一个对象，如果equals方法返回的是true，那么就不会把第二个对象存放在哈希表中，如果返回的是false，就会把这个值存放在哈希表中。也就是说多个对象可能存放在同一块存储空间中，当第一个对象来到数组的存储空间时，这块空间存储的是第一个进入该区域的对象地址，当第二个对象再次进入这个空间时，这个对象的内存地址并不直接保存在数组中，而是保存在第一个存入的对象中。说道HashSet不得不说一下加载因子，所谓的加载因子就是一个触发数组扩容的指标。虚拟机默认是0.75，初始容量，数组长度默认是16。也就是说当数组的长度超过12时，就会扩容，而之前存在当前数组中的地址又会重新进行哈希。简图如下：
2>.字符串对象的哈希值
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
EMAIL:y1053419035@qq.com
*/ package cn.org.yinzhengjie.note; class Teacher {
/*
* 没有做重写父类，每次运行结果都是不同整数
* 如果子类重写父类的方法，哈希值，自定义的
* 存储到HashSet集合的依据
*
*/
@Override
public int hashCode() {
return 100;
}
} public class HashDemo {
public static void main(String[] args) {
Teacher t = new Teacher();
//调用自定义的类的hashCode方法
int hashId = t.hashCode();
System.out.println(hashId); String s1 = new String("abc");
String s2 = "abc";
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
}
} /*
以上代码执行结果如下：
100
96354
96354
*/
我们可以明显看出自己定义的类调用hashCode()默认返回值为100，最终打印结果和我们预期的一样，而我们在创建一个字符串的时候，发现两个值相等的字符串他们的地址竟然也是一样的！这是怎么回事呢？这个时候我们就不得不去看一下String重写的hashCode源码啦。
3>.哈希表的存储过程
四.哈希表的存储自定义对象
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
EMAIL:y1053419035@qq.com
*/ package cn.org.yinzhengjie.note2; public class Person {
private String name;
private int age;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
public Person() {
super();
}
@Override
public String toString() {
return this.name + "---" + this.age;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
Person.java 文件内容
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
EMAIL:y1053419035@qq.com
*/ package cn.org.yinzhengjie.note2; import java.util.HashSet; public class HashDemo {
public static void main(String[] args) {
HashSet<Person> set = new HashSet<>();
set.add(new Person("尹正杰",18));
set.add(new Person("尹正杰",28));
set.add(new Person("尹正杰",38));
set.add(new Person("尹正杰",48));
set.add(new Person("尹正杰",108));
set.add(new Person("桂 阳",20));
set.add(new Person("张 杰",19));
set.add(new Person("卜梦龙",20));
set.add(new Person("李 洋",18));
System.out.println(set);
}
} /*
以上代码执行结果如下:
[尹正杰---48, 张 杰---19, 尹正杰---18, 尹正杰---38, 卜梦龙---20, 李 洋---18, 桂 阳---20, 尹正杰---28, 尹正杰---108]
*/
五.LinkedHashSet集合
具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到 set 中的顺序（插入顺序）进行迭代。注意，插入顺序不 受在 set 中重新插入的 元素的影响。（如果在 s.contains(e) 返回 true 后立即调用 s.add(e)，则元素 e 会被重新插入到 set s 中。）此实现可以让客户免遭未指定的、由 HashSet 提供的通常杂乱无章的排序工作，而又不致引起与 TreeSet 关联的成本增加。
从后缀可以看出：其本质是HashSet只不过在内部维护了一个链表，可以记住元素放入的顺序，这样就保证了存取的顺序，但是由于多了个链表，所以他的效率低些。如果保证元素唯一呢？当然是基于hashCode和equals方法。那么如何保证顺序呢？当然是链表啦！
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
EMAIL:y1053419035@qq.com
*/
package cn.org.yinzhengjie.note2; import java.util.LinkedHashSet; public class LinkedHashSetDemo {
public static void main(String[] args) {
LinkedHashSet<Integer> link = new LinkedHashSet<>();
link.add(123);
link.add(98);
link.add(100);
link.add(314);
System.out.println(link);
}
} /*
以上代码执行结果如下：
[123, 98, 100, 314]
*/
六.TreeSet类
基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。此实现为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
注意，如果要正确实现 Set 接口，则 set 维护的顺序（无论是否提供了显式比较器）必须与 equals 一致。（关于与 equals 一致 的精确定义，请参阅 Comparable 或 Comparator。）这是因为 Set 接口是按照 equals 操作定义的，但 TreeSet 实例使用它的 compareTo（或 compare）方法对所有元素进行比较，因此从 set 的观点来看，此方法认为相等的两个元素就是相等的。即使 set 的顺序与 equals 不一致，其行为也是 定义良好的；它只是违背了 Set 接口的常规协定。
注意，此实现不是同步的。如果多个线程同时访问一个 TreeSet，而其中至少一个线程修改了该 set，那么它必须 外部同步。这一般是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSortedSet 方法来“包装”该 set。此操作最好在创建时进行，以防止对 set 的意外非同步访问：
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
此类的 iterator 方法返回的迭代器是快速失败 的：在创建迭代器之后，如果从结构上对 set 进行修改，除非通过迭代器自身的 remove 方法，否则在其他任何时间以任何方式进行修改都将导致迭代器抛出 ConcurrentModificationException。因此，对于并发的修改，迭代器很快就完全失败，而不会冒着在将来不确定的时间发生不确定行为的风险。
注意，迭代器的快速失败行为无法得到保证，一般来说，存在不同步的并发修改时，不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测 bug。
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
EMAIL:y1053419035@qq.com
*/
package cn.org.yinzhengjie.note2; import java.util.TreeSet; public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<String> set = new TreeSet();
set.add("d");
set.add("a");
set.add("c");
set.add("b");
for (String string : set) {
System.out.println(string); //自动进行排序
}
System.out.println(set);
}
} /*
以上代码执行结果如下：
a
b
c
d
[a, b, c, d]
*/
七.ArrayListm,HashSet判断对象是否重复的原因
1>.ArrayList的contains方法判断元素是否重复原理
ArrayList的contains方法会使用调用方法时，传入的元素的equals方法依次与集合中的旧元素所比较，从而根据返回的布尔值判断是否有重复元素。此时，当ArrayList存放自定义类型时，由于自定义类型在未重写equals方法前，判断是否重复的依据是地址值，所以如果想根据内容判断是否为重复元素，需要重写元素的equals方法。
2>.HashSet的add/contains等方法判断元素是否重复原理
Set集合不能存放重复元素，其添加方法在添加时会判断是否有重复元素，有重复不添加，没重复则添加。HashSet集合由于是无序的，其判断唯一的依据是元素类型的hashCode与equals方法的返回结果。规则如下：
先判断新元素与集合内已经有的旧元素的HashCode值。
a>.如果不同，说明是不同元素，添加到集合。
b>.如果相同，再判断equals比较结果。返回true则相同元素；返回false则不同元素，添加到集合。
所以，使用HashSet存储自定义类型，如果没有重写该类的hashCode与equals方法，则判断重复时，使用的是地址值，如果想通过内容比较元素是否相同，需要重写该元素类的hashcode与equals方法。
八.hashCode和equals方法的面试题
现有两个Person对象，p1和p2，那么存在两个问题：
1>.如果两个对象的哈希值相同（p1.hashCode()==p2.hashCode()），两个对象的equals一定返回true吗？p1.equals(p2) 一定是true吗？
正确答案：不一定！
2>.如果两个对象的equals方法返回true(p1.equals(p2) == true)，两个对象的哈希值一定相同吗？
正确答案：一定！
