Java笔记(16) Collection集合-->Set集合-->HashSet
1. Set接口基本介绍
- Set是无序集合（添加和取出的顺序不一致，但取出的顺序是固定的），没有索引
- 不允许重复元素，所以最多包含一个null
- JDK API中Set接口的实现类有：
Abstract, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet
1.1 Set接口的常用方法
Set接口和List接口一样，都是Collection的子接口，因此常用方法和Collection接口一样
1.2 Set接口的遍历方法
同Collection的遍历方式一样，因为Set接口是Collection接口的子接口。
- 可以使用迭代器
- 增强for循环
- 不能使用索引的方式来获取
2 HashSet
2.1 HashSet的全面说明
- HashSet实现了Set接口，类定义如下：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
- HashSet实际上是HashMap，HashSet的无参构造函数如下：
public HashSet() {
map = new HashMap<>();
}
- 可以存放null值，但因为不能重复，所以只能存放一个null
- HashSet不保证元素是有序的，取决于hash之后，在确定索引的结果，也因此取出顺序是固定的
- 不能有重复元素/对象。
2.2 有关重复元素的经典问题
//定义一个类
class Dog{
private String name;
public Dog(String name){
this.name = name;
}
}
//定义一个HashSet
Set<Object> set = new HashSet<>();
set.add(new Dog("dog"));
set.add(new Dog("dog"));
System.out.println(set);
两个dog都能添加成功！前面不是说不能有重复元素吗？事实上，HashSet判断元素是否重复依靠的是HashCode，而上面的代码并没有重写HashCode和equals方法，导致HashSet在判断两个Dog对象是否重复时，是以地址为依据判断的，而两个对象实例其在堆上的内存必然是不一样的，因此他们两个被认为是不同的实例。
相同的问题使用String再来验证一下：
set.add("john");
set.add("john");
System.out.println(set);
毫无疑问地添加失败了，这是因为"john"被放在了常量池中，地址不变了吗？
set.add(new String("john"));
set.add(new String("john"));
System.out.println(set);
结果仍然添加失败，这两个String对象的内存地址不同，却仍被准确识别为重复元素，是因为String类重写了HashCode和equals方法，HashSet在判断过程中比较的是二者的内容是否一致，而不再是地址了
2.3 HashSet底层机制说明
HashSet底层是HashMap，HashMap底层是(数组+链表+红黑树)
HashSet添加元素的操作(hash()+equals()):
- HashSet底层是HashMap
- 添加一个元素是，先得到hash值，会转成索引值
- 找到存储数据表table，看这个索引位置是否已经存放的有元素
- 如果没有，直接加入
- 如果有，调用equals比较内容，如果相同，就放弃添加，如果不相同，则添加到最后，形成链表
- 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),并且table的大小 >= MIN_TRESHOLD_CAPACITY(默认是64)，就会进行树化(红黑树)
- HashSet底层的HashMap，第一次添加时，table数组扩容到16，临界值(threshold)是16*0.75(加载因子, loadFactor) = 12;
- 如果table数组使用到了临界值12，或者某条单链长度超过8，就会扩容到16*2 = 32，新的临界值就是32*0.75 = 24。以此类推
- 在Java8中，如果一条链表的元素个数达到TREE_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制
- 临界值比较的是table中的所有节点个数，不论这个节点是直接存储在table中，还是附加在某一条链表后
- 如果table没有达到64，而单链长度超过8，会立即触发扩容，并且每次检测到超长都会触发一次扩容，即使没有达到threshold，直到table长度达到64后，触发树化
2.4 set.add()调用过程
HashSet<Object> set = new HashSet<>();
set.add("john");
以上代码的调用过程如下图：
2.4 set.add()调用过程
HashSet<Object> set = new HashSet<>();
set.add("john");
以上代码的调用过程如下图：
图中标注了调用顺序和返回顺序
其中，最关键的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//定义了一些辅助变量，table就是HashMap的一个数组，类型是Node[]
Node<K,V>[] tab; Node<K,V> p; int n, i;
//if语句表示如果当前table是null，或者length==0，就第一次扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置，并把这个位置的对象赋给p
//(2) 判断p是否为null
//(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突，就创建一个Node(key="java",value=PRESENT)，
// 就放在该位置 tab[i] = new Node(hash,key,value,null);
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//(2.2) 如果p不为null,表示该位置已经存放过元素，即发生了哈希碰撞，
else {
//定义了一些辅助变量。一个开发技巧的提示：在需要的局部变量(辅助变量)时再创建
Node<K,V> e; K k;
//(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且满足下面两个条件之一，就认为传入了重复元素，不能加入
// 条件一： 准备加入的key和 p指向的Node节点的key是同一个对象
// 条件二： 调用equals()方法比较二者，结果为ture，即认为他们内容相同，注意，这里的equals()方法是程序员定义的，不是单纯的比较内容
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判断p是不是一棵红黑树，如果是一颗红黑树，就调用putTreeVal()来添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果table对应索引位置已经是一个链表，就用for循环比较
for (int binCount = 0; ; ++binCount) {
//(1) 依次和链表的每一个元素比较后，都不相同，将该元素添加至该链表最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//在把元素添加到链表后，立即判断该链表长度是否超过8个节点，如果是，就尝试将该链表转化为红黑树
//在进行树化时，还有一层判断：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
//如果if条件成立，就会先对table扩容；如果不成立，在转化成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//(2) 如果比较过程中发现重复元素，退出返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //每次比较后，指针后移
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);//该方法是HashMap留给子类实现的方法，对于HashMap来说，是一个空方法
return null;//返回null代表成功，否则会在前面的return语句中返回当前索引指向的对象
}
其中，最关键的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//定义了一些辅助变量，table就是HashMap的一个数组，类型是Node[]
Node<K,V>[] tab; Node<K,V> p; int n, i;
//if语句表示如果当前table是null，或者length==0，就第一次扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置，并把这个位置的对象赋给p
//(2) 判断p是否为null
//(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突，就创建一个Node(key="java",value=PRESENT)，
// 就放在该位置 tab[i] = new Node(hash,key,value,null);
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//(2.2) 如果p不为null,表示该位置已经存放过元素，即发生了哈希碰撞，
else {
//定义了一些辅助变量。一个开发技巧的提示：在需要的局部变量(辅助变量)时再创建
Node<K,V> e; K k;
//(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
// 并且满足下面两个条件之一，就认为传入了重复元素，不能加入
// 条件一： 准备加入的key和 p指向的Node节点的key是同一个对象
// 条件二： 调用equals()方法比较二者，结果为ture，即认为他们内容相同，注意，这里的equals()方法是程序员定义的，不是单纯的比较内容
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判断p是不是一棵红黑树，如果是一颗红黑树，就调用putTreeVal()来添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果table对应索引位置已经是一个链表，就用for循环比较
for (int binCount = 0; ; ++binCount) {
//(1) 依次和链表的每一个元素比较后，都不相同，将该元素添加至该链表最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//在把元素添加到链表后，立即判断该链表长度是否超过8个节点，如果是，就尝试将该链表转化为红黑树
//在进行树化时，还有一层判断：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
//如果if条件成立，就会先对table扩容，知道64；如果不成立，在转化成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//(2) 如果比较过程中发现重复元素，退出返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //每次比较后，指针后移
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);//该方法是HashMap留给子类实现的方法，对于HashMap来说，是一个空方法
return null;//返回null代表成功
}