【攻克java集合系列（三）】java集合中的Set系列集合全面分析

转x33g5p2x  于2021-12-06 转载在 Java  
字(9.5k)|赞(0)|评价(0)|浏览(546)

之前我们已经对List和Queue集合进行了比较深入的分析，接下来轮到Set集合了，开干！

Set系列集合中的继承实现关系

建议大家先看完本文再回过头来思考这张图。

Set集合的无序性与不可重复性

Set与List和Queue一样都继承至Collection，位于java.util包中。

Set集合不允许包含相同的元素，并且不能记住元素的添加顺序，所以就不支持按索引访问的方式

public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();

        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(42);
        set.add(56);
        set.add(76);
        set.add(88);

        System.out.println("set:" + set);
        System.out.println("==============================================");
        boolean temp = set.add(1);
        System.out.println("第二次添加元素1:" + temp);
        System.out.println("set:" + set);

    }

打印结果

可以看到Set集合中元素的存储顺序与我们插入元素的顺序并不相同；并且在向集合中重复添加相同的元素时，并不能添加成功，添加相同元素后的Set集合与添加前的集合完全一致。这就是Set集合的无序性和不可重复性。

Set接口源码分析

Set是继承至Collection的一个接口，位于java.util包中。

Set中继承了Collection中的一些基本方法，如下

public interface Collection<E> extends Iterable<E> {
    // 返回此集合中的元素数。 如果超过Integer.MAX_VALUE个元素，则返回Integer.MAX_VALUE 。 
    int size();

    // 如果此集合不包含元素，则返回 true 。
    boolean isEmpty();

    // 如果此集合包含指定的元素，则返回true 。
    boolean contains(Object o);

    // 返回此集合中的元素的迭代器。
    Iterator<E> iterator();

    // 返回一个包含此集合中所有元素的数组。
    Object[] toArray();

    // 返回包含此集合中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。
    <T> T[] toArray(T[] a);

    // 如果此集合由于调用而更改，则返回true 。 （如果此集合不允许重复，并且已包含指定的元素，则返回false。 ）
    boolean add(E e);

    // 从该集合中删除指定元素的单个实例（如果存在）（可选操作）。如果此集合包含指定的元素（或等效地，如果此集合由于调用而更改），则返回true 。 
    boolean remove(Object o);

    // 如果此集合包含指定 集合中的所有元素，则返回true。 
    boolean containsAll(Collection<?> c);

    // 将指定集合中的所有元素添加到此集合
    boolean addAll(Collection<? extends E> c);

    // 删除指定集合中包含的所有此集合的元素。 此调用返回后，此集合将不包含与指定集合相同的元素。 
    boolean removeAll(Collection<?> c);

    // 仅保留此集合中包含在指定集合中的元素，即从该集合中删除所有不包含在指定集合中的元素。
    boolean retainAll(Collection<?> c);

    // 清空集合
    void clear();

    // 将指定的对象与此集合进行比较
    boolean equals(Object o);

    // 返回此集合的哈希码值。
    int hashCode();

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

HashSet、TreeSet

HashSet和TreeSet是最为最为常见Set接口的实现类。

HashSet

从源码分析HashSet集合
HashSet实现Set接口，由哈希表（实际为HashMap实例）支持。

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

HashSet继承至AbstractSet，并且实现了Set，Cloneable以及java.io.Serializable接口，所以它支持可复制以及序列化操作。

底层以哈希表为支持（HashMap为实例）。

private transient HashMap<E,Object> map;

构造函数
HashSet提供了四种HashSet的构造方式

  • HashSet()
    构造一个新的空集合; HashMap实例具有默认初始容量（16）和负载因子（0.75）。
public HashSet() {
       map = new HashMap<>();
   }
  • HashSet(Collection<? extends E> c)
    构造一个包含指定集合中的元素的新集合。
public HashSet(Collection<? extends E> c) {
       map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
   }
  • HashSet(int initialCapacity, float loadFactor)
    构造一个新的空集合; HashMap实例具有指定的初始容量和默认负载因子（0.75）。
public HashSet(int initialCapacity, float loadFactor) {
       map = new HashMap<>(initialCapacity, loadFactor);
   }
  • HashSet(int initialCapacity)
    构造一个新的空集合; HashMap实例具有指定的初始容量和指定的负载因子。
public HashSet() {
   public HashSet(int initialCapacity) {
       map = new HashMap<>(initialCapacity);
   }

常用方法

  • Iterator iterator()
    返回此集合中元素的迭代器。 元素没有特定的顺序返回。
public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
  • int size()
    返回此集合中的元素数。
public int size() {
        return map.size();
    }
  • boolean isEmpty()
    如果此集合不包含元素，则返回 true 。
public boolean isEmpty() {
        return map.isEmpty();
    }
  • boolean contains(Object o)
    如果此集合包含指定的元素，则返回true 。
public boolean contains(Object o) {
        return map.containsKey(o);
    }
  • boolean add(E e)
    将指定的元素添加到此集合（如果尚未存在）。
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
  • boolean remove(Object o)
    如果存在，则从该集合中删除指定的元素。
public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
  • void clear()
    清空集合中的元素
public void clear() {
        map.clear();
    }
  • Object clone()
    返回此 HashSet实例的浅层副本：元素本身不被克隆。
public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

可以看到HashSet中的方法都是在HashMap的基础上就行操作的。

LinkedHashSet

LinkedHashSet是HashSet的一个子类，它使用一个双向链表维护集合，使得LinkedHashSet具有有序性（插入元素的顺序）。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet继承至HashSet，并且实现了Set, Cloneable, java.io.Serializable接口，具有Set集合不重复的特点和可复制、可序列化的性质。
构造方法
LinkedHashSet中提供了四种构造方法：

  • LinkedHashSet(int initialCapacity, float loadFactor)
    构造具有指定的初始容量和负载因子的新的，空的LinkedHashSet。
public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
  • LinkedHashSet(int initialCapacity)
    构造一个具有指定初始容量和默认负载因子（0.75）的新的，空的LinkedHashSet。
public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
  • LinkedHashSet()
    构造一个具有默认初始容量（16）和负载因子（0.75）的新的，空的LinkedHashSet。
public LinkedHashSet() {
        super(16, .75f, true);
    }
  • LinkedHashSet(Collection<? extends E> c)
    构造与指定集合相同的元素的新的LinkedHashSet。
public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

TreeSet

TreeSet也叫树集，是一个有序的集合，这里的有序不是指List中按照元素的加入顺序存储的有序性，而是指它能够对集合中的元素按照某种规则进行排序，并且保持集合中元素的唯一性。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet继承至AbstractSet，并且实现了NavigableSet，Cloneable以及java.io.Serializable接口，所以它也是支持可复制以及序列化操作。
由于实现了NavigableSet接口，它也具有了为给定搜索目标报告最接近匹配项的导航方法。
NavigableSet解析：从源码分析SortedSet与NavigableSet

TreeSet内部是基于TreeMap实现的，它提供两种排序方式（取决与构造方法）：

  • 自然排序
  • 根据创建TreeSet 时提供的 Comparator 进行排序

TreeSet的元素有序及唯一

public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();

        set.add(4);
        set.add(2);
        set.add(1);
        set.add(4);
        set.add(42);
        set.add(33);
        set.add(76);
        set.add(67);

        System.out.println("set:" + set);
        System.out.println("==============================================");
        boolean temp = set.add(1);
        System.out.println("第二次添加元素1:" + temp);
        System.out.println("set:" + set);

    }


可以看到TreeSet中的元素经过排序，递增的打印在控制台，并且向HashSet中重复添加相同的元素时，并不能添加成功。

构造方法
构造由指定的可导航地图支持的集。

/** * Constructs a set backed by the specified navigable map. */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

TreeSet 提供了四种TreeSet 的构造方式：

  • TreeSet()
    构造一个新的，空的树集，根据其元素的自然排序进行排序。
public TreeSet() {
        this(new TreeMap<E,Object>());
    }
  • TreeSet(Comparator<? super E> comparator)
    构造一个新的，空的树集，根据指定的比较器进行排序。
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
  • TreeSet(Collection<? extends E> c)
    构造一个包含指定集合中的元素的新树集，根据其元素的自然排序进行排序。
public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
  • TreeSet(SortedSet s)
    构造一个包含相同元素的新树，并使用与指定排序集相同的顺序。
public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

常用方法

  • Iterator iterator()
    以升序返回该集合中的元素的迭代器。
public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }
  • Iterator descendingIterator()
    以降序返回该集合中的元素的迭代器。
public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }
  • int size()
    返回此集合中的元素数。
public int size() {
        return m.size();
    }
  • boolean isEmpty()
    如果此集合不包含元素，则返回 true 。
public boolean isEmpty() {
        return m.isEmpty();
    }
  • boolean contains(Object o)
    如果此集合包含指定的元素，则返回true 。
public boolean contains(Object o) {
        return m.containsKey(o);
    }
  • boolean add(E e)
    将指定的元素添加到此集合（如果尚未存在）。
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
  • boolean remove(Object o)
    如果存在，则从该集合中删除指定的元素。
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
  • void clear()
    清空集合中的元素
public void clear() {
        m.clear();
    }
  • boolean addAll(Collection<? extends E> c)
    将指定集合中的所有元素添加到此集合中。
public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }
  • NavigableSet subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive)
    该集合的部分的视图，其元素的范围从 fromElement （包括）到 toElement。
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }
  • NavigableSet headSet(E toElement, boolean inclusive)
    该集合的全部的视图。
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }
  • NavigableSet headSet(E toElement, boolean inclusive)
    返回此集合的部分的视图，其元素小于（或等于，如果inclusive为真）toElement。
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }
  • NavigableSet tailSet(E fromElement, boolean inclusive)
    返回此集合的部分的视图，其元素小于（或等于，如果inclusive为真）toElement。
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }
  • Comparator<? super E> comparator()
    返回用于对该集合中的元素进行排序的比较器
public Comparator<? super E> comparator() {
        return m.comparator();
    }
  • E first()
    返回此集合中当前的第一个（最低）元素。
public E first() {
        return m.firstKey();
    }
  • E last()
    返回此集合中当前的最后（最高）元素。
public E last() {
        return m.lastKey();
    }
  • E lower(E e)
    返回这个集合中最大的元素严格小于给定的元素，如果没有这样的元素，则返回 null 。
public E lower(E e) {
        return m.lowerKey(e);
    }
  • E floor(E e)
    返回该集合中最大的元素小于或等于给定的元素，如果没有这样的元素，则返回 null 。
public E floor(E e) {
        return m.floorKey(e);
    }
  • E ceiling(E e)
    返回此集合中最小元素大于或等于给定元素，如果没有此元素则返回 null 。
public E ceiling(E e) {
        return m.ceilingKey(e);
    }
  • E higher(E e)
    返回此集中的最小元素严格大于给定元素，如果没有此元素，则返回 null 。
public E higher(E e) {
        return m.higherKey(e);
    }
  • E pollFirst()
    检索并删除第一个（最低）元素，如果此集合为空，则返回 null 。
public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
  • E pollLast()
    检索并删除最后一个（最高）元素，如果此集合为空，则返回 null 。
public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }
  • Object clone()
    返回此TreeSet实例的浅拷贝。 （元素本身不被克隆。）
public Object clone() {
        TreeSet<E> clone;
        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }

        clone.m = new TreeMap<>(m);
        return clone;
    }

HashSet、TreeSet、LinkedHashSet之间的比较

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_43598687/article/details/121617875

内容来源于网络，如有侵权，请联系作者删除！

JavaSet集合源码java集合java源码

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com