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接口，类定义如下：
  

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

复制代码

• HashSet实际上是HashMap，HashSet的无参构造函数如下：
  

1. public HashSet() {
2.     map = new HashMap<>();
3. }

复制代码

• 可以存放null值，但因为不能重复，所以只能存放一个null
  
• HashSet不保证元素是有序的，取决于hash之后，在确定索引的结果，也因此取出顺序是固定的
  
• 不能有重复元素/对象。
  

2.2 有关重复元素的经典问题

1. //定义一个类
2. class Dog{
3.     private String name;
4.     public Dog(String name){
5.         this.name = name;
6.     }
7. }
8. //定义一个HashSet
9. Set<Object> set = new HashSet<>();
10. set.add(new Dog("dog"));
11. set.add(new Dog("dog"));
12. System.out.println(set);

复制代码

两个dog都能添加成功！前面不是说不能有重复元素吗？事实上，HashSet判断元素是否重复依靠的是HashCode，而上面的代码并没有重写HashCode和equals方法，导致HashSet在判断两个Dog对象是否重复时，是以地址为依据判断的，而两个对象实例其在堆上的内存必然是不一样的，因此他们两个被认为是不同的实例。
相同的问题使用String再来验证一下：

1. set.add("john");
2. set.add("john");
3. System.out.println(set);

复制代码

毫无疑问地添加失败了，这是因为"john"被放在了常量池中，地址不变了吗？

1. set.add(new String("john"));
2. set.add(new String("john"));
3. 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()调用过程

1.     HashSet<Object> set = new HashSet<>();
2.     set.add("john");

复制代码

以上代码的调用过程如下图：
2.4 set.add()调用过程

1.     HashSet<Object> set = new HashSet<>();
2.     set.add("john");

复制代码

以上代码的调用过程如下图：

图中标注了调用顺序和返回顺序
其中，最关键的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下：

1.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
2.         //定义了一些辅助变量，table就是HashMap的一个数组，类型是Node[]
3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
4.         //if语句表示如果当前table是null，或者length==0，就第一次扩容到16
5.         if ((tab = table) == null || (n = tab.length) == 0)
6.             n = (tab = resize()).length;
7.         //(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置，并把这个位置的对象赋给p
8.         //(2) 判断p是否为null
9.         //(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突，就创建一个Node(key="java",value=PRESENT)，
10.         //      就放在该位置 tab[i] = new Node(hash,key,value,null);
11.         if ((p = tab[i = (n - 1) & hash]) == null)
12.             tab[i] = newNode(hash, key, value, null);
14.             //(2.2) 如果p不为null,表示该位置已经存放过元素，即发生了哈希碰撞，
15.         else {
16.             //定义了一些辅助变量。一个开发技巧的提示：在需要的局部变量(辅助变量)时再创建
17.             Node<K,V> e; K k;
18.             //(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且满足下面两个条件之一，就认为传入了重复元素，不能加入
19.             // 条件一： 准备加入的key和 p指向的Node节点的key是同一个对象
20.             // 条件二： 调用equals()方法比较二者，结果为ture，即认为他们内容相同，注意，这里的equals()方法是程序员定义的，不是单纯的比较内容
21.             if (p.hash == hash &&
22.                 ((k = p.key) == key || (key != null && key.equals(k))))
23.                 e = p;
24.             //再判断p是不是一棵红黑树，如果是一颗红黑树，就调用putTreeVal()来添加
25.             else if (p instanceof TreeNode)
26.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
28.             else {
29.                 //如果table对应索引位置已经是一个链表，就用for循环比较
30.                 for (int binCount = 0; ; ++binCount) {
31.                     //(1) 依次和链表的每一个元素比较后，都不相同，将该元素添加至该链表最后
32.                     if ((e = p.next) == null) {
33.                         p.next = newNode(hash, key, value, null);
34.                         //在把元素添加到链表后，立即判断该链表长度是否超过8个节点，如果是，就尝试将该链表转化为红黑树
35.                         //在进行树化时，还有一层判断：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
36.                         //如果if条件成立，就会先对table扩容；如果不成立，在转化成红黑树
37.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
38.                             treeifyBin(tab, hash);
39.                         break;
40.                     }
41.                     //(2) 如果比较过程中发现重复元素，退出返回
42.                     if (e.hash == hash &&
43.                         ((k = e.key) == key || (key != null && key.equals(k))))
44.                         break;
45.                     p = e;  //每次比较后，指针后移
46.                 }
47.             }
48.             if (e != null) { // existing mapping for key
49.                 V oldValue = e.value;
50.                 if (!onlyIfAbsent || oldValue == null)
51.                     e.value = value;
52.                 afterNodeAccess(e);
53.                 return oldValue;
54.             }
55.         }
56.         ++modCount;
57.         if (++size > threshold)
58.             resize();
59.         afterNodeInsertion(evict);//该方法是HashMap留给子类实现的方法，对于HashMap来说，是一个空方法
60.         return null;//返回null代表成功，否则会在前面的return语句中返回当前索引指向的对象
61.     }

复制代码

其中，最关键的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下：

1.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
2.         //定义了一些辅助变量，table就是HashMap的一个数组，类型是Node[]
3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
4.         //if语句表示如果当前table是null，或者length==0，就第一次扩容到16
5.         if ((tab = table) == null || (n = tab.length) == 0)
6.             n = (tab = resize()).length;
7.         //(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置，并把这个位置的对象赋给p
8.         //(2) 判断p是否为null
9.         //(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突，就创建一个Node(key="java",value=PRESENT)，
10.         //      就放在该位置 tab[i] = new Node(hash,key,value,null);
11.         if ((p = tab[i = (n - 1) & hash]) == null)
12.             tab[i] = newNode(hash, key, value, null);
14.             //(2.2) 如果p不为null,表示该位置已经存放过元素，即发生了哈希碰撞，
15.         else {
16.             //定义了一些辅助变量。一个开发技巧的提示：在需要的局部变量(辅助变量)时再创建
17.             Node<K,V> e; K k;
19.             //(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
20.             // 并且满足下面两个条件之一，就认为传入了重复元素，不能加入
21.             // 条件一： 准备加入的key和 p指向的Node节点的key是同一个对象
22.             // 条件二： 调用equals()方法比较二者，结果为ture，即认为他们内容相同，注意，这里的equals()方法是程序员定义的，不是单纯的比较内容
23.             if (p.hash == hash &&
24.                 ((k = p.key) == key || (key != null && key.equals(k))))
25.                 e = p;
26.             //再判断p是不是一棵红黑树，如果是一颗红黑树，就调用putTreeVal()来添加
27.             else if (p instanceof TreeNode)
28.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
30.             else {
31.                 //如果table对应索引位置已经是一个链表，就用for循环比较
32.                 for (int binCount = 0; ; ++binCount) {
33.                     //(1) 依次和链表的每一个元素比较后，都不相同，将该元素添加至该链表最后
34.                     if ((e = p.next) == null) {
35.                         p.next = newNode(hash, key, value, null);
36.                         //在把元素添加到链表后，立即判断该链表长度是否超过8个节点，如果是，就尝试将该链表转化为红黑树
37.                         //在进行树化时，还有一层判断：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
38.                         //如果if条件成立，就会先对table扩容，知道64；如果不成立，在转化成红黑树
39.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
40.                             treeifyBin(tab, hash);
41.                         break;
42.                     }
43.                     //(2) 如果比较过程中发现重复元素，退出返回
44.                     if (e.hash == hash &&
45.                         ((k = e.key) == key || (key != null && key.equals(k))))
46.                         break;
47.                     p = e;  //每次比较后，指针后移
48.                 }
49.             }
50.             if (e != null) { // existing mapping for key
51.                 V oldValue = e.value;
52.                 if (!onlyIfAbsent || oldValue == null)
53.                     e.value = value;
54.                 afterNodeAccess(e);
55.                 return oldValue;
56.             }
57.         }
58.         ++modCount;
59.         if (++size > threshold)
60.             resize();
61.         afterNodeInsertion(evict);//该方法是HashMap留给子类实现的方法，对于HashMap来说，是一个空方法
62.         return null;//返回null代表成功
63.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！