【容器源码篇】Set容器（HashSet，LinkedHashSet，TreeSet的特点）

文章目录

• ⭐容器继承关系
• • 🌹Set容器
  • • 🗒️HashSet源码解析
    • • 构造方法
      • • public HashSet()
        • public HashSet(Collection c)
        • public HashSet(int initialCapacity, float loadFactor)
        • HashSet(int initialCapacity, float loadFactor, boolean dummy)
        • public HashSet(int initialCapacity)
        • 常用方法
        • 🗒️LinkedHashSet源码解析
        • • 构造函数
          • 🗒️TreeSet源码解析
          • • 构造函数
            • add方法
            • addAll方法

              ⭐容器继承关系

              🌹Set容器

              Set用于存储不重复元素的集合。Set接口继承自Collection接口，不允许包含重复元素，并且没有指定顺序。常见的Set实现类有HashSet、LinkedHashSet和TreeSet。

              🗒️HashSet源码解析

              不允许重复元素：HashSet不允许存储重复的元素，如果试图向HashSet中添加一个已经存在的元素，那么添加操作将会失败。

              无序性：HashSet不保证集合中元素的顺序，即元素在集合中没有特定的顺序。具体的遍历顺序取决于元素的哈希码。

              基于哈希表：HashSet内部是通过HashMap来实现的。HashSet中的元素作为HashMap的key，而value则是一个固定的Object对象。

              添加、删除、包含操作的时间复杂度都是O(1)：由于HashSet基于哈希表实现，对于添加、删除和包含操作的时间复杂度都是常数级别的，因此具有很高的性能。

              构造方法

              public HashSet()

              创建一个空的HashMap，一个空HashMap的默认容量是16，装载因子是0.75

              public HashSet(Collection c)

              创建一个包含集合c中所有不重复元素的HashSet集合

              public HashSet(int initialCapacity, float loadFactor)

              创建一个具有指定容量和负载因子的HashMap

              HashSet(int initialCapacity, float loadFactor, boolean dummy)

              创建一个具有指定容量和负载因子的LinkedHashMap，这个包私有构造函数只被LinkedHashSet使用

              public HashSet(int initialCapacity)

              创建一个具有指定容量的HashMap

              常用方法

              // 返回集合中元素的个数
                  public int size() { return map.size();
                  }
              	// 返回集合是否为空
                  public boolean isEmpty() { return map.isEmpty();
                  }
              	
              	// 返回集合中是否包含指定元素o
                  public boolean contains(Object o) { return map.containsKey(o);
                  }
              	// 添加指定元素e
              	// 将e作为HashMap的key 常量PRESENT作为所有元素的value
                  public boolean add(E e) { return map.put(e, PRESENT)==null;
                  }
              	// 移出指定元素o
                  public boolean remove(Object o) { return map.remove(o)==PRESENT;
                  }
              	// 清空集合中所有元素
                  public void clear() { map.clear();
                  }
              

              🗒️LinkedHashSet源码解析

              LinkedHashSet是HashSet的子类，并且内部使用链表维护元素的插入顺序。下面是LinkedHashSet的一些特点和使用方法：

              保持插入顺序：与HashSet不同的是，LinkedHashSet会按照元素插入的顺序来维护集合中的元素。遍历LinkedHashSet时可以按照元素插入的顺序进行访问。

              基于哈希表和链表：LinkedHashSet内部既使用哈希表来存储元素，又使用链表来维护元素的插入顺序。

              性能表现：与HashSet相比，LinkedHashSet在添加、删除和包含操作的性能方面略低一些，因为需要同时维护哈希表和链表。

              构造函数

              🗒️TreeSet源码解析

              有序性：TreeSet会对元素进行排序，并且可以按照自然顺序或者自定义排序规则来进行排序。默认情况下，TreeSet会按照元素的自然顺序进行排序，或者在构造函数中传入Comparator对象以自定义排序规则。

              不允许null元素：TreeSet不允许添加null元素，因为它使用元素的比较规则来维护顺序，而null无法比较大小。

              性能表现：TreeSet的添加、删除和包含操作的时间复杂度为O(log n)，其中n为TreeSet中的元素个数。

              构造函数

              add方法

              addAll方法

              判断当前集合是否为空且指定集合不为空，并且指定集合为SortedSet类型，当前集合为TreeMap类型。

              如果满足以上条件，则将指定集合转换为SortedSet类型，将当前集合转换为TreeMap类型。

              比较指定集合的比较器和当前集合的比较器是否相等，如果相等，则使用线性时间版本的添加方式：map.addAllForTreeSet(set, PRESENT)。

              如果不满足以上条件，则调用父类的addAll方法进行添加操作。