Java 中的集合框架之 Set 接口、HashSet 类、LinkedHashSet 类（1万字超全详解）

短命女 2023-09-28 15:30 35阅读 0赞

### 文章目录 ###

*  一、集合的框架体系
 *   *  1. 常用集合接口概述
     *  2. 常用 Collection 集合的实现子类
     *  3. 常用的 Map 图的实现子类
 *  二、Collection 接口
 *   *  1. Collection 接口常用方法
     *  2. 迭代器（Iterator）
     *  3. Collection 集合的遍历
 *  三、Set 接口
 *   *  Set 接口的遍历方式
 *  四、HashSet 类（散列表）
 *   *  1. HashSet 类基本概念
     *  2. HashSet 类的底层机制（重难点！！）
 *  五、LinkedHashSet 类（链式散列表）
 *   *  1. LinkedHashSet 类的基本概念
     *  2. LinkedHashSet 类的底层机制
 *  六、TreeSet 类
 *  总结

# 一、集合的框架体系 #

Java 集合框架提供了一套性能优良，使用方便的接口和类，其位于 java.util 包中， 所以当使用集合框架的时候需要进行导包。  
**Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合；另一种是图（Map），存储键/值对映射。**

*  **集合（Collection）体系如下：**  
    ![集合（Collection）体系图][Collection]
 *  **图（Map）体系如下：**  
    ![d61a2b447c5b47519cc9fcfdfcf4b87a.png][]

> **说明：**  
> **（1）Collection 接口有两个重要的子接口 List、 Set , 他们的实现子类都是单列集合。**  
> **（2）Map 接口的实现子类是双列集合，存放的 K-V（键值对）**

## 1. 常用集合接口概述 ##

**如下表：**

<table> 
 <thead> 
  <tr> 
   <th align="left">接口</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">Collection 接口</td> 
   <td align="left">Collection 是最基本的集合接口，一个 Collection 代表一组 Object（即 Collection 的元素）, Java不提供直接继承自 Collection的类，只提供继承自 Collection 接口的子接口(如 List和 set)。Collection 接口存储一组不唯一，无序的对象（不能通过索引来访问 Collection 集合中的对象）。</td> 
  </tr> 
  <tr> 
   <td align="left">List 接口</td> 
   <td align="left">List 接口继承自 Collection 接口 ，但 List 接口 是一个有序的集合，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(即元素在 List 中的位置，类似于数组的下标)来访问 List 集合中的元素，第一个元素的索引为 0。而且 List 集合中允许有相同的元素。可以说，List 接口的集合存储一组不唯一，有序（插入顺序）的对象。</td> 
  </tr> 
  <tr> 
   <td align="left">Set 接口</td> 
   <td align="left">Set 接口继承自 Collection 接口，具有与 Collection 完全一样的接口，只是方法上有部分不同，和 Collection 接口 相同，Set 接口存储一组唯一，无序的对象。</td> 
  </tr> 
  <tr> 
   <td align="left">Map 接口</td> 
   <td align="left">Map 接口与 Collection 接口同级（彼此没有继承关系），Map 图存储一组 键-值 对象，提供key（键）到value（值）的映射。</td> 
  </tr> 
 </tbody> 
</table>

**Set 和 List 接口的区别：**

> **（1）Set 接口集合存储的是无序的，不重复的数据。List 接口集合存储的是有序的，可以重复的元素。**

> **（2）Set 集合 底层使用的是 链表数据结构，其检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变 （实现子类有 HashSet , TreeSet 等）。**

> **（3）List 结合 底层和数组类似，但是它可以动态增长，根据实际存储的数据的长度自动增长 List 的长度。其检索元素效率高，插入和删除效率低，插入和删除会引起其他元素位置改变 （实现子类有 ArrayList, LinkedList , Vector 等）。**

## 2. 常用 Collection 集合的实现子类 ##

Java 提供了一套实现了 Collection 接口的标准集合类。其中一些是具体类，这些类可以直接拿来使用，而另外一些是抽象类，提供了接口的部分实现。

**如下表：**

<table> 
 <thead> 
  <tr> 
   <th align="left">类名</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">ArrayList 类</td> 
   <td align="left">该类实现了 List 接口，允许存储 null（空值）元素，且可存储重复元素。该类实现了可变大小的数组，随机访问和遍历元素时，提供了更好的性能。该类是非同步的, 在多线程的情况下不要使用。ArrayList 类在扩容时会扩容当前容量的1.5倍。</td> 
  </tr> 
  <tr> 
   <td align="left">Vector 类</td> 
   <td align="left">该类和 ArrayList 类非常相似，但该类是同步的，可以用在多线程的情况，该类允许设置默认的增长长度，默认扩容方式为原来的2倍。</td> 
  </tr> 
  <tr> 
   <td align="left">LinkedList 类</td> 
   <td align="left">该类实现了 List 接口，允许存储 null（空值）元素，且可存储重复元素，主要用于创建链表数据结构，该类没有同步方法，如果多个线程同时访问一个 LinkedList，则必须自己实现访问同步，解决方法就是在创建 LinkedList 类 时候再构造一个同步的 LinkedList 。</td> 
  </tr> 
  <tr> 
   <td align="left">HashSet 类</td> 
   <td align="left">该类实现了 Set 接口，不允许存储重复元素，并且不保证集合中元素的顺序，其允许存储 null （空值）元素，但最多只能存储一个。</td> 
  </tr> 
  <tr> 
   <td align="left">TreeSet 类</td> 
   <td align="left">该类实现了 Set 接口，不允许存储重复元素，并且不保证集合中元素的顺序，其允许存储 null （空值）元素，但最多只能存储一个。该类可以实现排序等功能。</td> 
  </tr> 
 </tbody> 
</table>

## 3. 常用的 Map 图的实现子类 ##

**如下表：**

<table> 
 <thead> 
  <tr> 
   <th align="left">类名</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">HashMap 类</td> 
   <td align="left">HashMap 类是一个散列表，它存储的内容是键-值对 (key-value) 映射。该类实现了 Map 接口，根据键的 HashCode 值存储y元素，具有很快的访问速度，但最多允许一条记录的键为 null （空值），它不支持线程同步。</td> 
  </tr> 
  <tr> 
   <td align="left">TreeMap 类</td> 
   <td align="left">TreeMap 类继承了AbstractMap ，实现了大部分 Map 接口，并且使用一颗树。</td> 
  </tr> 
  <tr> 
   <td align="left">Hashtable 类</td> 
   <td align="left">Hashtable 继承自 Dictionary(字典) 类，用来存储 键-值对。</td> 
  </tr> 
  <tr> 
   <td align="left">Properties 类</td> 
   <td align="left">Properties 继承自 Hashtable，表示一个持久的属性集，属性列表中每个键及其对应值都是一个字符串。</td> 
  </tr> 
 </tbody> 
</table>

**特此说明：由于集合框架的内容繁多，因此本文只介绍 Collection 集合下的 Set 接口及其重要实现子类的内容，其余集合框架的知识将会在下篇博文分享。**

# 二、Collection 接口 #

## 1. Collection 接口常用方法 ##

*  **说明：所有实现了 Collection 接口的子类集合都可以使用 Collection 接口中的方法。下面使用的是实现了 List 接口的 ArrayList 子类来举例，但实现了 Set 接口的子类都可以使用下列方法。**
 *  **代码实现：**

import java.util.ArrayList;
    import java.util.List;
    
    public class CollectionMethod {
        
        public static void main(String[] args) {
        
    		// 以实现了Collection 接口 的子类 ArrayList 来举例；
    		
            ArrayList list = new ArrayList();
    
    //      1.  add:添加单个元素
            list.add("jack");
            list.add(10);// 底层自动装箱：list.add(new Integer(10))
            list.add(true);// 同上
            System.out.println("list=" + list);// [jack, 10, true]
    
    //      2.  addAll:添加多个元素
            ArrayList list2 = new ArrayList();// 创建一个新的集合
            list2.add("红楼梦");
            list2.add("三国演义");
            list.addAll(list2);
            System.out.println("list=" + list);// [jack, 10, true, 红楼梦, 三国演义]
          
    //      3.  remove:删除指定元素，如果不指定则默认删除第一个元素
            list.remove(true);// 指定删除某个元素
            System.out.println("list=" + list);// [jack, 10, 红楼梦, 三国演义]
    
    //      4.  removeAll：删除多个元素
            list.add("聊斋");
            list.removeAll(list2);
            System.out.println("list=" + list);// [jack, 10, 聊斋]
          
    //      5.  contains:查找元素是否存在，返回 boolean 值
            System.out.println(list.contains("jack"));// T
    
    //      6.  containsAll:查找多个元素是否都存在，返回 boolean 值
            System.out.println(list.containsAll(list2));// T
          
    //      7.  size:获取元素个数
            System.out.println(list.size());// 3
    
    //      8.  isEmpty:判断是否为空
            System.out.println(list.isEmpty());// F
    
    //      9.  clear:清空
            list.clear();
            System.out.println("list=" + list);// []
        }
    }

## 2. 迭代器（Iterator） ##

*  **Iterator（迭代器）不是一个集合，它是一种用于访问 Collection 集合的接口，主要用于遍历 Collection 集合中的元素，所有实现了 Collection 接口的子类集合都可以使用迭代器。**
 *  **迭代器的执行原理：**

>  *  **迭代器就相当于一个游标，初始时指向集合中的第1个元素的的前一个位置；**
>  *  **首先使用 hasNext() 方法来判断迭代器的下一个位置是否还有元素，**
>  *  **若下一个位置有元素则使用 next() 方法返回下一个元素，并将迭代器的位置向后移一位。**
>  *  **若没有，则不调用 next() 方法，直接退出迭代器。**

![在这里插入图片描述][3c4811c9ab304019bc2941460c3ddd8a.png]

> **迭代器常用方法：**  
> **（1）调用 coll.next() 会返回迭代器的下一个元素，并且更新迭代器的状态（迭代器下移）。**  
> **（2）调用 list.hasNext() 判断集合中是否还有下一个元素。**  
> **（3）调用 list.remove() 将迭代器返回的元素删除。**

*  **注意：在使用 next() 方法前必须使用 hasNext() 方法判断集合中是否还有下一个元素，否则可能会出现异常。**
 *  **代码演示：**

import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Iterator;
    
    public class CollectionIterator {
        
        public static void main(String[] args) {
        
    
            List list = new ArrayList();// 创建一个新的集合，该集合实现了 Collection 接口
    
            list.add(1);
            list.add(2);
            list.add(3);
    
            // 1. 先得到 list集合 对应的 迭代器
            // 使用集合的 iterator() 方法来获得该集合的迭代器；
            // 所有实现了 Collection 接口的子类都拥有 iterator() 方法
            Iterator iterator = list.iterator();
    
            // 2. 使用 while 循环 + 迭代器 遍历集合
    
            while (iterator.hasNext()) {
         // 首先判断集合中（下一个位置）是否还有元素
    
                // 若有，则获取下一个位置的元素，迭代器位置向下移一位
                Object obj = iterator.next();
                // 输出该元素
                System.out.println("obj=" + obj);
    
            }
    
            // 3. 注意：当退出 while 循环后 , 这时 iterator 迭代器，指向的是集合中的最后一个元素；
            //  若再次 使用 iterator.next();  会产生 NoSuchElementException 异常，因为集合中下一个位置没有元素存在了； 
            
            // 4. 如果希望再次遍历集合，需要重置 迭代器的状态；
            
            iterator = list.iterator();// 重置迭代器
            System.out.println("===第二次遍历===");
            while (iterator.hasNext()) {
        
                Object obj = iterator.next();
                System.out.println("obj=" + obj);
            }
        }
    }

## 3. Collection 集合的遍历 ##

*  **说明：所有实现了 Collection 接口的子类集合都可以使用 下面的遍历方法。**

> **（1）使用迭代器遍历（所有集合中都可以使用 迭代器 来遍历）。**  
> **（2）使用普通 for 循环遍历（普通 for 循环 是通过元素的索引来获取元素，在无序的集合中不能此方式来获取元素。比如 实现了 Set 接口的子类集合）。**  
> **（3）使用增强 for 循环遍历（增强 for 循环的底层其实是实现了 迭代器，因此在 所有集合中都可以使用该方式遍历）。**

*  **代码实现：**

import java.util.*;
    
    public class ListFor {
        
        public static void main(String[] args) {
        
    
            ArrayList list = new ArrayList();// 创建一个有序的集合
    
            list.add("jack");
            list.add("tom");
            list.add("鱼香肉丝");
            list.add("北京烤鸭子");
    
            //遍历方式：
            //1. 迭代器
            Iterator iterator = list.iterator();
            while (iterator.hasNext()) {
        
                Object obj =  iterator.next();
                System.out.println(obj);
    
            }
    
            System.out.println("=====增强for=====");
            //2. 增强 for 循环
            for (Object o : list) {
        
                System.out.println("o=" + o);
            }
    
            System.out.println("=====普通for====");
            //3. 普通 for 循环
            for (int i = 0; i < list.size(); i++) {
        
                System.out.println("对象=" + list.get(i));
            }
        }
    }

# 三、Set 接口 #

*  **Set 接口是Collection 的子接口，Set 集合存储一组唯一，无序的元素（无序即 Set 接口的元素添加和取出的顺序不一致，且元素没有索引）。**
 *  Set 接口 Collection 的子接口，因此，其常用方法和 Collection 接口一样。
 *  **代码实现：**

public class SetMethod {
        
        public static void main(String[] args) {
        
    
            // 1. 以Set 接口的实现类 HashSet 来讲解Set 接口的方法
            // 2. set 接口的实现类的对象(Set接口对象), 不能存放重复的元素, 可以添加一个null
            // 3. set 接口对象存放元素是唯一和无序的(即添加的顺序和取出的顺序不一致)
            // 4. 注意：取出的顺序的顺序虽然不是添加的顺序，但是只要取出一次，它之后取出的顺序就一样了。
            Set set = new HashSet();
            set.add("john");
            set.add("lucy");
            set.add("john");// 元素重复，存入失败
            set.add("jack");
            set.add("hsp");
            set.add(null);// 可以添加 null
            set.add(null);// 再次添加null 会失败
            System.out.println(set);// 添加元素的顺序和打印出来的顺序不同
            System.out.println(set);// 但多次打印出来的顺序相同。
    
        }
    }

## Set 接口的遍历方式 ##

*  同 Collection接口 的遍历方式一样，Set 接口的比遍历方法可以使用：

> **（1）使用迭代器遍历**  
> **（2）使用增强 for 循环**  
> **注意，不能使用 普通 for 循环遍历获取元素（因为 Set 中的对象不能通过索引来获取）。**

*  **代码实现：**

public class SetMethod {
        
        public static void main(String[] args) {
        
    
            Set set = new HashSet();
            set.add("john");
            set.add("lucy");
            set.add("jack");
            set.add("hsp");
            set.add(null);
            
            // 遍历
            // 方式1： 使用迭代器
            
            Iterator iterator = set.iterator();
            while (iterator.hasNext()) {
        
                Object obj =  iterator.next();
                System.out.println("obj=" + obj);
    
            }
    
            // 方式2: 增强for
            System.out.println("=====增强for====");
    
            for (Object o : set) {
        
                System.out.println("o=" + o);
            }
    
            // set 接口集合，不能通过索引来获取元素，因此不能使用普通 for 循环来获取元素。 
            // 下面代码会报错！！
            for(int i = 0; i < set.size(); i++) {
        
                System.out.println(set.get(i));// 注意，根本没有get 方法
            }
        }
    }

# 四、HashSet 类（散列表） #

## 1. HashSet 类基本概念 ##

*  **HashSet 类实现了 Set 接口，不允许存储重复元素，并且不保证集合中元素的顺序，其允许存储 null （空值）元素，但最多只能存储一个。**
 *  HashSet 类不是线程安全的， 如果多个线程尝试同时修改 HashSet，则最终结果是不确定的。 必须在多线程访问时显式同步对 HashSet 的并发访问。
 *  查看HashSet 类的构造器源码，可以发现，HashSet 类的底层其实是基于 HashMap 类来实现的。
 *  HashSet 类实现了Set 接口，因此 HashSet 类中的常用方法和 Collection 接口中的一致，且 HashSet 集合的遍历方式和 Set 接口的一致。
 *  **代码演示：**

public class HashSet_ {
        
        public static void main(String[] args) {
        
            /*
            1. HashSet 类构造器的源码：
            
                public HashSet() {
                    map = new HashMap<>();// HashSet 类基于 HashMap 类来创建
                }
    
            2. HashSet 可以存放null ,但是只能有一个null,即元素不能重复
             */
            
            Set hashSet = new HashSet();
            hashSet.add(null);
            hashSet.add(null);// 添加失败
            System.out.println("hashSet=" + hashSet);
    
        }
    }

## 2. HashSet 类的底层机制（重难点！！） ##

HashSet 类的底层是 HashMap 类，其添加的元素是无序且唯一的；HashSet 类的底层维护了一个数组+单向链表（邻接表）的数据结构。

*  简单说明数组+单向链表的数据结构：就是存在一个数组，数组中的每个元素都指向了一条单向链表。如下图：  
    ![在这里插入图片描述][524d6dd436c5409a92eb86dd85b2fd92.png]
 *  **这里我们只分析 HashSet 集合添加元素的底层实现机制和 HashSet 集合的底层扩容机制。先说明结论，再详细分析。**
 *  **结论如下：**

> **一、HashSet 类对象调用 add() 方法添加元素的底层实现机制**  
> **（1）在添加一个新元素时，首先根据这个元素的 hashcode 值得到 一个对应的 hash 值，然后将该 hash 值转成一个对应的 索引值。**  
> **（2）其次在 HashSet 类对象的领接表中检索，先检索的索引值对应的数组位置，看下该位置是否已经存储了元素。**  
> **（3）若数组的该位置未存储元素，则直接将新元素存放进该数组位置。**

> **（4）若数组的该位置已经存储有元素（下面统称为旧元素），则需调用 equals() 方法再进行判断新、旧元素是否相同。**

> **（4.1）若新元素 与 旧元素相同，则不存储新元素，退出 add() 方法。**

> **（4.2）若新元素 与 旧元素不同，则进入数组该位置指向的单向链表，又要再次判断该链表是普通的单项链表，还是一个升级的红黑树。**  
> **（4.2.1）若已经是红黑树，则使用红黑树中的方法进行比较，由于红黑树太复杂，就不在此分析其底层。**  
> **（4.2.2）若是普通的单向链表，则依次遍历该链表的每个结点；若遍历链表结束，发现所有结点存储的旧元素和新元素都不同，便将新元素加入链表的尾部（将新元素存放进 HashSet 集合中），检查是否要将链表树化，再退出 add 方法；若在遍历过程中，发现存在一个旧元素与新元素相同，则不存储新元素，退出add 方法。**

*  **源码演示：**

public class HashSetSource {
        
        public static void main(String[] args) {
        
    
            HashSet hashSet = new HashSet();
            hashSet.add("java");// 到此位置，第1 次add分析完毕，
            hashSet.add("php");// 到此位置，第2 次add分析完毕，前两个元素添加在数组的不同位置。
            hashSet.add("java");// 在此位置，添加了已存在的元素，它和之前的元素重复了，所以它们 hash 值相同
            System.out.println("set=" + hashSet);
          
    对HashSet 的源码解读：
    
    1. 执行 HashSet() 方法:
    
        public HashSet() {
        
            map = new HashMap<>();// 底层是 HashMap 构造器；
        }
        
    2. 执行 add() 方法:
    
       public boolean add(E e) {
        // e = "java"
            return map.put(e, PRESENT)==null;// (static) PRESENT = new Object(); 这个值始终是固定的值，没意义，作用是占位
       // 注意：底层 HashMap 的 put()方法需要传入键、值对（两个值），但实际 HashSet 是单列集合，不需要值，所以便将值这个位置的参数设置为静态变量，相当于没有作用。
       }
       
    3.执行 put() , 该方法首先会执行 hash(key) 得到key 对应的 hash值，使用 算法 h = key.hashCode()) ^ (h >>> 16)
     
        public V put(K key, V value) {
         // key == "java"， value == PRESENT 静态变量是共享的，在 HashSet 中没有作用。
            return putVal(hash(key), key, value, false, true);// hash值不等于 hashcode()，而是做了避免碰撞的处理
        }
        
     4.执行 putVal()方法:
     
     	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量
    
            // table 就是 HashMap 的一个属性，类型是 Node[]数组
            // if 语句表示如果当前 table 是 null, 或者 大小=0 ；就调用 resize()，进行第一次扩容，到 16个空间.（该方法里面有个缓存算法），然后回到 putVal 方法；
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
    		// 开始添加元素
    
            // 若添加的索引位置未存放元素，看这个分支
            if ((p = tab[i = (n - 1) & hash]) == null) // i 是根据hash 值算出的索引
            /*
             (1) 根据 key与得到的 hash， 去计算该 key 应该存放到 table表的哪个索引位置，并把这个位置的先前存在的对象，赋给 p
             (2) 再判断 p （位置的对象）是否为null
                 	(2.1) 如果p 为 null, 表示该位置还没有存放元素, 就创建一个Node (key="java", value = PRESENT)
                 	(2.2) 然后放在该索引位置 tab[i] = newNode(hash, key, value, null)
             */    	
                tab[i] = newNode(hash, key, value, null); // 最后一个实参 null 就是 next值
    
    
            // 添加索引位置存在元素 ，看这个分支
            else {
        
                // 一个开发技巧提示： 在需要局部变量(辅助变量)时候，再创建
                Node<K,V> e; K k; // 辅助变量：辅助结点 e
    
                // 第一种情况，索引位置已存在的元素与新元素 “相同”
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且满足 下面两个条件之一:
                        // (1) 准备加入的key 和 p 指向的Node 结点的 已存在key 是同一个对象
                        // (2) p 指向的Node 结点的 已存在key 的 equals() 和准备加入的 key比较后相同
                    // 否则不能进入
                    e = p; // 辅助结点 e 指向已存在的对象；
    
                // 第二种情况，索引位置已存在的元素与新元素 “不相同”,但 索引指向了一个红黑树
                else if (p instanceof TreeNode)
                     判断 p 是不是一颗红黑树,如果是一颗红黑树，就调用 putTreeVal , 来进行添加，
                     否则不能进入
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    
                // 第三种情况，索引位置已存在的元素与新元素 “不相同”,但 索引指向一个链表
                else {
        
                      // 如果table 对应索引位置，已经是一个链表, 就使用for 循环比较；
                     /*  (1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后；
                          注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
                          , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)；
                          注意，在转成红黑树时，要进行判断, 判断条件:
                      */    
                          if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
                                  resize();
                        //  如果上面条件成立，先 进行table扩容.
                        //  只有上面条件不成立时，才进行转成红黑树
                        
                      // (2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break
                    for (int binCount = 0; ; ++binCount) {
         // 死循环
                    
                   //     （1）依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                    //    （2）依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
    
                        p = e;// 将 p 指针往下移动，可以实现依次比较链表中的每个元素
                    }
                }
    
                //最后判断 e 是否指向空值，如果指向空值，说明该链表中没有元素与新元素相同，跳过下面代码；
                //否则,说明 已存在重复元素，进入下面代码，不返回空值
    
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue; // 退出putVal 方法，不返回空值
                }
            }
            ++modCount;
            
            // size： 每加入一个结点Node(k,v,h,next), size都会增加一次，不管是在数组或是索引位置。
            if (++size > threshold) // threshold 属性在resize() 中是一个缓冲值，当超过该值时就需要重新调用 resize 方法扩容
                resize();// 再次扩容
            afterNodeInsertion(evict);// 对于hashmap 来说，该方法是个空方法，是它留给它的子类去实现的
            return null;// 返回 null给 putVal方法，再返回null 给put 方法，代表成功了；如果不为null ，则失败了
    	}

> **二、HashSet 集合的底层扩容与链表红黑树化机制**  
> **（1）HashSet 的底层是 HashMap，在使用 add 方法添加元素时，会调用 resize() 方法进行数组的扩容。**  
> **（2）当第一次往 HashSet 集合中添加元素时，resize（）方法会将数组的大小 （size 变量）扩容到16；在方法中设置了一个数组临界值 threshold ，是数组大小的 0.75 倍，当数组中存储的元素到达该临界值的时候，就会再次调用 resize（）方法对数组进行扩容，默认是 扩容到之前数组大小的2倍，然后更新临界值 threshold。**  
> **（3）当 HashSet 集合中的某个数组位置中的链表的元素个数到达一个固定值时（默认为8个），集合就会将普通的单向链表进行红黑树化，但前提是数组的大小已到达64；否则要先对数组扩容（直到数组大小到达64），再进行树化。**

*  **代码举例：**

public class HashSetIncrement {
        
        public static void main(String[] args) {
        
            /*
            HashSet 底层是HashMap, 第一次添加时，table 数组扩容到 16，
            临界值(threshold)是 16*加载因子(loadFactor)是0.75 = 12
            如果table 数组使用到了临界值 12,就会扩容到 16 * 2 = 32,
            新的临界值就是 32*0.75 = 24, 依次类推
             */
            HashSet hashSet = new HashSet();
    
            // 往集合中添加元素，下列的每个元素都是添加到集合的数组中，不会添加到链表中
            // 所以集合将会一直进行数组的扩容。
            for(int i = 1; i <= 100; i++) {
        
                hashSet.add(i); // 1,2,3,4,5...100
            }
    
            /*
            在Java8中, 如果一条链表的元素个数 >= TREEIFY_THRESHOLD(默认是 8 )，
            并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树),
            否则仍然采用数组扩容机制，意思是说到第11个元素时就会扩容到64了
             */
            hashSet = new HashSet(); // 创建一个新的空集合
    
            // 往集合中添加元素，但与上面不同，这次添加的元素会添加到数组的同一个索引位置，
            // 因此数组的大小不会改变，依旧是默认的16。
            // 由于每个元素都不同，所以这些元素会加入到数组的单向链表中，
            // 当链表中的元素增加到8个时，集合就要将普通链表进行树化；
            // 但此时数组的大小为16，不满足树化要求的数组大小为64，所以要先进行数据的扩容；
            // 则新加入的第9、10个元素依然是添加到单向链表的后面，此时数组大小扩容到64；
            // 在添加第11 个元素时，数组大小和链表长度都满足了树化的条件，因此集合将链表进行树化。
            // 注意，本例中的每个元素都是不同的，但他们的hash 值相同，因此加入的数组的索引位置相同。
            for(int i = 1; i <= 12; i++) {
        
                hashSet.add(new A(i));
            }
    
    
            /*
                当我们向hashset增加一个元素，-> Node -> 加入table , 就算是增加了一个size
                在 table中 size > threshold ，就会扩容
             */
    
            hashSet = new HashSet(); // 再次创建一个新的空集合
    
            // 在 集合的某一条链表上添加了 7个 A对象
            for(int i = 1; i <= 7; i++) {
        
                hashSet.add(new A(i));
            }
            
            // 在另一条链表上添加到第4 个 B对象的时候，size = 12，到达临界值，数组会进行 resize（）扩容
            // 但是由于为满足某条链表的元素个数 = 8，所以不会进行树化。 
            for(int i = 1; i <= 7; i++) {
        
                hashSet.add(new B(i));
            }
        }
    }
    
    class B {
        
        private int n;
    
        public B(int n) {
        
            this.n = n;
        }
        @Override
        public int hashCode() {
        
            return 200;
        }
    }
    
    class A {
        
        private int n;
    
        public A(int n) {
        
            this.n = n;
        }
        @Override
        public int hashCode() {
        
            return 100;
        }
    }

*  上面的解释过程，需要小伙伴们自己动手去 debug ，才能真正理解。

# 五、LinkedHashSet 类（链式散列表） #

## 1. LinkedHashSet 类的基本概念 ##

> **(1）LinkedHashSet 类是 HashSet 类的子类，可以使用 HashSet 类中的所有常用方法和遍历方法。**  
> **(2）LinkedHashSet 类底层是一个 LinkedHashMap ，底层维护了一个数组+双向链表的数据结构。**  
> (3）LinkedHashSet 类根据元素的 hashCode 值来决定元素在数组中的存储位置（和 HashSet 一样），同时使用双向链表维护了元素的次序，这使得元素看起来是以插入顺序保存的（即元素的添加顺序和输出顺序是相同的）,即对 HashSet 进行了扩展。  
> **(4）LinkedHashSet 类不允许添重复元素，允许有null 值，不能使用 索引来获取元素。**

## 2. LinkedHashSet 类的底层机制 ##

*  **示意图如下：**

![在这里插入图片描述][afa474b5859d42c28d04380917486fe9.png]

*  **说明：LinkedHashSet 集合的底层机制其实和 HashSet 集合的差不多，只是将 单向链表换成了 双向链表，所以元素的添加和取出看上去是有序的，但本质上 LinkedHashSet 集合中元素的存放仍是无序的，不能使用索引来获取该集合中的元素。**

# 六、TreeSet 类 #

*  **源码分析**

public class TreeSet_ {
        
        public static void main(String[] args) {
        
        
            // 1. 当我们使用无参构造器，创建 TreeSet 时，仍然是无序的
            // 2. 老师希望添加的元素，按照字符串大小来排序
            // 3. 使用TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)，并指定排序规则
    
    //      TreeSet treeSet = new TreeSet();// 普通构造器
    
            //  带参构造器
            TreeSet treeSet = new TreeSet(new Comparator() {
        
                @Override
                public int compare(Object o1, Object o2) {
        
    
                 // return ((String) o2).compareTo((String) o1); 按照字符串大小排序
                  
                    return ((String) o1).length() - ((String) o2).length();// 按照长度大小排序
                }
            });
    
            // 添加数据
            treeSet.add("jack");
            treeSet.add("tom");// 3
            treeSet.add("sp");
            treeSet.add("a");
            treeSet.add("abc");// abc 长度和 tom 相同，加入失败
    
    
            System.out.println("treeSet=" + treeSet);
     
    源码分析：
    
    1. 构造器把传入的比较器对象，赋给了 TreeSet的底层的 TreeMap的属性this.comparator
    
        public TreeMap(Comparator<? super K> comparator) {
        
            this.comparator = comparator;
        }
    
    2. 在 调用 treeSet.add("tom"), 在底层会执行到
    
        if (cpr != null) {
        //cpr 就是我们的匿名内部类(对象)
            do {
        
                parent = t;
                //动态绑定到我们的匿名内部类(对象)compare
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else //如果相等，即返回0,这个Key就没有加入
                    return t.setValue(value);
            } while (t != null);
        }   
    
        }
    }

# 总结 #

*  本文是小白博主在学习B站韩顺平老师的Java网课时整理总结的学习笔记，在这里感谢韩顺平老师的网课，如有有兴趣的小伙伴也可以去看看。
 *  本文详细介绍了 集合框架 的基本概念，并深入讲解了 Collection 集合中常用的 Set 接口、HashSet 类、LinkedHashSet 类 使用的注意事项和常用方法，并介绍了迭代器的使用；还分析了各个子类实现的源码，举了很多很多例子，希望小伙伴们看后能有所收获！
 *  最后，如果本文有什么错漏的地方，欢迎大家批评指正！一起加油！！我们下一篇博文见吧！

[Collection]: https://img-blog.csdnimg.cn/436a04070ca94faa81a4784d5d97179f.png
[d61a2b447c5b47519cc9fcfdfcf4b87a.png]: https://img-blog.csdnimg.cn/d61a2b447c5b47519cc9fcfdfcf4b87a.png
[3c4811c9ab304019bc2941460c3ddd8a.png]: https://img-blog.csdnimg.cn/3c4811c9ab304019bc2941460c3ddd8a.png
[524d6dd436c5409a92eb86dd85b2fd92.png]: https://img-blog.csdnimg.cn/524d6dd436c5409a92eb86dd85b2fd92.png
[afa474b5859d42c28d04380917486fe9.png]: https://img-blog.csdnimg.cn/afa474b5859d42c28d04380917486fe9.png