源码阅读(26)：Java中主要的Set结构——HashSet

柔情只为你懂 2023-07-08 09:17 43阅读 0赞

# 1、概述 #

在全面理解了HashMap结构后，理解HashSet数据结构也就足够简单了——HashSet内部就是对HashMap数据结构的依赖。HashMap结构的Key就是HashSet存储的数据，HashMap结构的Value则是一个固定对象记为“PRESENT”：

// ...
    private static final Object PRESENT = new Object();
    // ...

下图为HashSet的主要继承体系：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70]  
从上图可以看出HashSet继承了AbstractSet，后者包括了相当一部分关于Set集合通用的方法逻辑。这些方法包括了equals(Object o)、hashCode()、isEmpty()、contains(Object o)等方法。

> This class provides a skeletal implementation of the Setinterface to minimize the effort required to implement thisinterface.

在上一篇文章中《[源码阅读(25)：Java中主要的Set结构——概述][25_Java_Set]》我们已经介绍过HashSet结构的使用效果，简单来说其使用效果可以概要为以下几个要点：

*  HashSet中不允许存储“相同”的元素。

如何确认“相同”元素呢？就是使用当前存储到HashSet集合中的对象定义的hashCode()方法的返回结果作为确认依据（关于对象定义中的equals(Object anObject)方法和hashCode()方法如何作用于对象“相等”的判定属于最基础知识，读者可参考其它资料）。例如当前HashSet中存储了java.lang.String类型的对象，那么将使用“boolean String.hashCode()”这个方法判定对象是否“相同”。实际上这个原理也是HashMap集合的工作原理。

*  由于内部存储原理依赖于HashMap的原因，HashSet集合中存储的元素并不是有序的。最显著的效果是：同样的元素集合，使用不同的添加顺序添加到集合中，这些元素在集合中存储的位置可能是不同的。这段代码已经在前文中给出：

//......
    // 创建一个HashSet集合，并添加字符串对象
    HashSet<String> set = new HashSet<>();
    set.add("a");
    set.add("b");
    set.add("c");
    set.add("1");
    set.add("2");
    set.add("3");
    Iterator<String> itr = set.iterator();
    while(itr.hasNext()) {
        
      String item = itr.next();
      System.out.println(String.format("item = %s" , item));
    }
    
    // 以下代码改变了元素对象的添加顺序，就会造成集合中元素的存储顺序完全不一样
    System.out.println("//=======================");
    set = new HashSet<>();
    set.add("1");
    set.add("2");
    set.add("3");
    set.add("a");
    set.add("b");
    set.add("c");
    itr = set.iterator();
    while(itr.hasNext()) {
        
      String item = itr.next();
      System.out.println(String.format("item = %s" , item));
    }
    //......

输出结果如下所示：

item = a
    item = 1
    item = b
    item = 2
    item = c
    item = 3
    //=======================
    item = 1
    item = a
    item = 2
    item = b
    item = 3
    item = c

# 2、结构特点 #

## 2.1、HashSet的主要结构 ##

上文已经多次强调，HashSet集合内部依赖于HashMap集合，下面我们给出HashSet源代码中关键属性的定义代码，进行分析：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
        
      // ......
      // 这是一个不参与序列化过程的HashMap集合，作为HashSet中一个重要属性存在。
      private transient HashMap<E,Object> map;
    
      // Dummy value to associate with an Object in the backing Map
      // 在HashSet基于HashMap添加元素时，后者每一个K-V键值对结点的Value值，都采用这个常量进行描述
      private static final Object PRESENT = new Object();
      
      // ......
    }

## 2.2、HashSet中的构造函数 ##

HashSet中的构造函数也很简单，主要就是对其内部的HashMap属性进行实例化，代码片段如下所示：

/**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     * 完成一个默认的HashMap对象的实例化
     */
     public HashSet() {
        
       map = new HashMap<>();
     }
    
     /**
      * 参考一个指定集合中的元素进行内部HashMap集合的初始化
      * 注意，HashMap的初始化大小基于当前两个数值较大的一个：源集合大小的175%和固定值16
      *
      * @param c the collection whose elements are to be placed into this set
      * @throws NullPointerException if the specified collection is null
      */
     public HashSet(Collection<? extends E> c) {
        
       map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
     }
    
     /**
      * 该构造函数可以为内部使用的HashMap指定两个关键参数，一个是HashMap的初始化大小，另一个是HashMap的负载因子
      * @param      initialCapacity   he initial capacity of the hash map
      * @param      loadFactor        the load factor of the hash map
      * @throws     IllegalArgumentException if the initial capacity is less
      *             than zero, or if the load factor is nonpositive
      */
     public HashSet(int initialCapacity, float loadFactor) {
        
       map = new HashMap<>(initialCapacity, loadFactor);
     }
    
     /**
      * 该构造函数可以为内部使用的HashMap指定一个关键参数，是HashMap的初始化大小；负载因子将设定为默认的0.75
      * @param      initialCapacity   the initial capacity of the hash table
      * @throws     IllegalArgumentException if the initial capacity is less
      *             than zero
      */
     public HashSet(int initialCapacity) {
        
       map = new HashMap<>(initialCapacity);
     }
    
     /**
      * 这个构造函数很有趣，这是一个访问控制级别为“包内访问”的构造函数，事实上，它是专门给
      * HashSet的子类LinkedHashSet进行实例化使用的构造函数。我们将在后续内容中介绍LinkedHashSet容器。
      * 那么问题来了，为什么不在LinkedHashSet类中定义这个构造函数呢？
      */
     HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
       map = new LinkedHashMap<>(initialCapacity, loadFactor);
     }

**由以上分析可以看出，基本上所有我们直接使用进行HashSet集合对象初始化的构造函数，其内部都是对HashMap对象的初始化。**

# 3、HashSet的主要方法 #

> **HashSet的主要方法都是对内部HashMap集合主要方法的封装**

请看HashSet集合的主要方法代码：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
        
      // ......
      /**
       * 集合的添加操作亦是调用了HashMap的添加操作，请注意写入的value对象，是一个常量
       * @param e element to be added to this set
       * @return <tt>true</tt> if this set did not already contain the specified
       * element
       */
      public boolean add(E e) {
        
        return map.put(e, PRESENT)==null;
      }
      
      /**
       * 集合的移除操作亦是调用HashMap的移除操作。
       *
       * @param o object to be removed from this set, if present
       * @return <tt>true</tt> if the set contained the specified element
       */
      public boolean remove(Object o) {
        
          return map.remove(o)==PRESENT;
      }
    
      /**
       * 集合的元素清除操作，亦是调用HashMap集合的清除操作
       */
      public void clear() {
        
        map.clear();
      }
    
      // 这里不再列举
      // ......
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030119502427.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ==,size_16,color_FFFFFF,t_70
[25_Java_Set]: https://blog.csdn.net/yinwenjie/article/details/103846008

发表评论取消回复

表情：

评论列表（有 0 条评论，43人围观）

还没有评论，来说两句吧...

相关阅读

相关源码阅读(27)：Java中主要的Set结构——LinkedHashSet、TreeSet等结构

（接上文《[源码阅读(26)：Java中主要的Set结构——HashSet][26_Java_Set_HashSet]》） 1、概述和HashSet类似，Java中另

傷城~/ 2023年07月10日 12:58/ 0 赞/ 29 阅读

相关源码阅读(26)：Java中主要的Set结构——HashSet

1、概述在全面理解了HashMap结构后，理解HashSet数据结构也就足够简单了——HashSet内部就是对HashMap数据结构的依赖。HashMap结构的Key就

柔情只为你懂/ 2023年07月08日 09:17/ 0 赞/ 44 阅读

相关 Java8 HashSet 源码阅读

1. 概述 HashSet 保证元素不重复的集合，查询元素、新增元素、删除元素的时间复杂度均为 O(1)。 HashSet 底层的数据结构为 HashMap，map 中

分手后的思念是犯贱/ 2023年07月03日 06:22/ 0 赞/ 55 阅读

相关源码阅读(25)：Java中主要的Set结构——概述

1、概述从本专题的第15篇文章开始一直到本专题的第24篇文章截止，我们花了大量的篇幅介绍Java中的Map接口以及实现该接口的多个重要容器，其中又以介绍HashMap容

╰+攻爆jí腚メ/ 2023年06月27日 08:48/ 0 赞/ 39 阅读

相关源码阅读(24)：Java中其它主要的Map结构——LinkedHashMap容器（下）

（接上文《[源码阅读(23)：Java中其它主要的Map结构——LinkedHashMap容器（上）][23_Java_Map_LinkedHashMap]》） 2、Lin

落日映苍穹つ/ 2023年06月23日 14:29/ 0 赞/ 42 阅读

相关源码阅读(23)：Java中其它主要的Map结构——LinkedHashMap容器（上）

1、概述 LinkedHashMap容器是Java容器框架中从很早的版本就开始提供的（JDK 1.4+），该容器又被这样认为：“LinkedHashMap = HashM

谁借莪１个温暖的怀抱￠/ 2023年06月21日 07:16/ 0 赞/ 88 阅读

相关源码阅读(22)：Java中其它主要的Map结构——TreeMap容器（2）

（接上文《[源码阅读(21)：Java中其它主要的Map结构——TreeMap容器（1）][21_Java_Map_TreeMap_1]》）（注：笔者翻阅了一下网络上的相

男娘i/ 2023年06月18日 06:57/ 0 赞/ 19 阅读

相关源码阅读(21)：Java中其它主要的Map结构——TreeMap容器（1）

(接上文《[源码阅读(20)：Java中主要的Map结构——HashMap容器（下2）][20_Java_Map_HashMap_2]》) 我们通过解读Java自带的各种Ma

小鱼儿/ 2023年06月16日 07:28/ 0 赞/ 37 阅读

相关源码阅读(20)：Java中主要的Map结构——HashMap容器（下2）

（接上文《[源码阅读(19)：Java中主要的Map结构——HashMap容器（下1）][19_Java_Map_HashMap_1]》） 3.4.6、HashMap扩容操

淩亂°似流年/ 2023年06月12日 09:10/ 0 赞/ 34 阅读

相关 Set源码分析（HashSet,TreeSet）

Set不允许重复的，HashSet无序，TreeSet有序的 HashSet 变量 private transient HashMap<E,Object> m

Dear 丶/ 2022年03月10日 04:58/ 0 赞/ 319 阅读