转载

深入浅出的分析 Set集合

01. 摘要

Set集合的特点主要有：元素不重复、存储无序的特点。

打开 Set 集合，主要实现类有 HashSet、LinkedHashSet 、TreeSet 、EnumSet（ RegularEnumSet、JumboEnumSet ）等等，总结 Set 接口实现类，图如下：

深入浅出的分析 Set集合

由图中的继承关系，可以知道，Set 接口主要实现类有 AbstractSet、HashSet、LinkedHashSet 、TreeSet 、EnumSet（ RegularEnumSet、JumboEnumSet ），其中 AbstractSet、EnumSet 属于抽象类，EnumSet 是在 jdk1.5 中新增的，不同的是 EnumSet 集合元素必须是枚举类型。

HashSet 是一个输入输出无序的集合，集合中的元素基于 HashMap 的 key 实现，元素不可重复；

LinkedHashSet 是一个输入输出有序的集合，集合中的元素基于 LinkedHashMap 的 key 实现，元素也不可重复；

TreeSet 是一个排序的集合，集合中的元素基于 TreeMap 的 key 实现，同样元素不可重复；

EnumSet 是一个与枚举类型一起使用的专用 Set 集合，其中 RegularEnumSet 和 JumboEnumSet 不能单独实例化，只能由 EnumSet 来生成，同样元素不可重复；

下面咱们来对各个主要实现类进行一一分析！

02. HashSet

HashSet 是一个输入输出无序的集合，底层基于 HashMap 来实现，HashSet 利用 HashMap 中的key元素来存放元素，这一点我们可以从源码上看出来，阅读源码如下：

public class HashSet<E>

extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable{

// HashMap 变量
private transient HashMap<E,Object> map;

/**HashSet 初始化*/
public HashSet() {
    //默认实例化一个 HashMap
    map = new HashMap<>();
}

}

add方法

打开HashSet的add()方法，源码如下：

public boolean add(E e) {

//向 HashMap 中添加元素
return map.put(e, PRESENT)==null;

}

其中变量PRESENT，是一个非空对象，源码部分如下：

private static final Object PRESENT = new Object();

可以分析出，当进行add()的时候，等价于

HashMap map = new HashMap<>();

map.put(e, new Object());//e 表示要添加的元素

在之前的集合文章中，咱们了解到 HashMap 在添加元素的时候 ，通过equals()和hashCode()方法来判断传入的key是否相同，如果相同，那么 HashMap 认为添加的是同一个元素，反之，则不是。

从源码分析上可以看出，HashSet 正是使用了 HashMap 的这一特性，实现存储元素下标无序、元素不会重复的特点。

remove方法

HashSet 的删除方法，同样如此，也是基于 HashMap 的底层实现，源码如下：

public boolean remove(Object o) {

//调用HashMap 的remove方法，移除元素
return map.remove(o)==PRESENT;

}

查询方法

HashSet 没有像 List、Map 那样提供 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：

public static void main(String[] args) {

Set<String> hashSet = new HashSet<String>();
System.out.println("HashSet初始容量大小："+hashSet.size());
hashSet.add("1");
hashSet.add("2");
hashSet.add("3");
hashSet.add("3");
hashSet.add("2");
hashSet.add(null);

//相同元素会自动覆盖
System.out.println("HashSet容量大小："+hashSet.size());
//迭代器遍历
Iterator<String> iterator = hashSet.iterator();
while (iterator.hasNext()){
    String str = iterator.next();
    System.out.print(str + ",");
}

System.out.println("/n===========");
//增强for循环
for (String str : hashSet) {
    System.out.print(str + ",");
}

}

输出结果：

HashSet初始容量大小：0

HashSet容量大小：4

null,1,2,3,

null,1,2,3,

需要注意的是，HashSet 允许添加为null的元素。

03. LinkedHashSet

LinkedHashSet 是一个输入输出有序的集合，继承自 HashSet，但是底层基于 LinkedHashMap 来实现。

如果你之前了解过 LinkedHashMap，那么你一定知道，它也继承自 HashMap，唯一有区别的是，LinkedHashMap 底层数据结构基于循环链表实现，并且数组指定了头部和尾部，虽然数组的下标存储无序，但是却可以通过数组的头部和尾部，加上循环链表，依次可以查询到元素存储的过程，从而做到输入输出有序的特点。

如果还不了解 LinkedHashMap 的实现过程，可以参阅集合系列中关于 LinkedHashMap 的实现过程文章。

阅读 LinkedHashSet 的源码，类定义如下：

public class LinkedHashSet<E>

extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {

public LinkedHashSet() {
    //调用 HashSet 的方法
    super(16, .75f, true);
}

}

查询源码，super调用的方法，源码如下：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {

//初始化一个 LinkedHashMap
map = new LinkedHashMap<>(initialCapacity, loadFactor);

}

add方法

LinkedHshSet没有重写add方法，而是直接调用HashSet的add()方法，因为map的实现类是LinkedHashMap，所以此处是向LinkedHashMap中添加元素，当进行add()的时候，等价于

HashMap map = new LinkedHashMap<>();

map.put(e, new Object());//e 表示要添加的元素

remove方法

LinkedHashSet也没有重写remove方法，而是直接调用HashSet的删除方法，因为LinkedHashMap没有重写remove方法，所以调用的也是HashMap的remove方法，源码如下：

public boolean remove(Object o) {

//调用HashMap 的remove方法，移除元素
return map.remove(o)==PRESENT;

}

查询方法

同样的，LinkedHashSet 没有提供 get 方法，使用迭代器或者 for 循环来遍历元素，方法如下：

public static void main(String[] args) {

Set<String> linkedHashSet = new LinkedHashSet<String>();
System.out.println("linkedHashSet初始容量大小："+linkedHashSet.size());
linkedHashSet.add("1");
linkedHashSet.add("2");
linkedHashSet.add("3");
linkedHashSet.add("3");
linkedHashSet.add("2");
linkedHashSet.add(null);
linkedHashSet.add(null);

System.out.println("linkedHashSet容量大小："+linkedHashSet.size());
//迭代器遍历
Iterator<String> iterator = linkedHashSet.iterator();
while (iterator.hasNext()){
    String str = iterator.next();
    System.out.print(str + ",");
}

System.out.println("/n===========");
//增强for循环
for (String str : linkedHashSet) {
    System.out.print(str + ",");
}

}

输出结果：

linkedHashSet初始容量大小：0

linkedHashSet容量大小：4

1,2,3,null,

1,2,3,null,

可见，LinkedHashSet 与 HashSet 相比，LinkedHashSet 输入输出有序。

04. TreeSet

TreeSet 是一个排序的集合，实现了NavigableSet、SortedSet、Set接口，底层基于 TreeMap 来实现。TreeSet 利用 TreeMap 中的key元素来存放元素，这一点我们也可以从源码上看出来，阅读源码，类定义如下：

public class TreeSet<E> extends AbstractSet<E>

implements NavigableSet<E>, Cloneable, java.io.Serializable {

//TreeSet 使用NavigableMap接口作为变量
private transient NavigableMap<E,Object> m;

/**对象初始化*/
public TreeSet() {
    //默认实例化一个 TreeMap 对象
    this(new TreeMap<E,Object>());
}

//对象初始化调用的方法
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

}

new TreeSet<>()对象实例化的时候，表达的意思，可以简化为如下：

NavigableMap<E,Object> m = new TreeMap<E,Object>();

因为TreeMap实现了NavigableMap接口，所以没啥问题。

public class TreeMap<K,V>

extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
......

}

add方法

打开TreeSet的add()方法，源码如下：

public boolean add(E e) {

//向 TreeMap 中添加元素
return m.put(e, PRESENT)==null;

}

其中变量PRESENT，也是是一个非空对象，源码部分如下：

private static final Object PRESENT = new Object();

可以分析出，当进行add()的时候，等价于

TreeMap map = new TreeMap<>();

map.put(e, new Object());//e 表示要添加的元素

TreeMap 类主要功能在于，给添加的集合元素，按照一个的规则进行了排序，默认以自然顺序进行排序，当然也可以自定义排序，比如测试方法如下：

public static void main(String[] args) {

Map initMap = new TreeMap();
initMap.put("4", "d");
initMap.put("3", "c");
initMap.put("1", "a");
initMap.put("2", "b");
//默认自然排序，key为升序
System.out.println("默认 排序结果:" + initMap.toString());
//自定义排序，在TreeMap初始化阶段传入Comparator 内部对象
Map comparatorMap = new TreeMap<String, String>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2){
        //根据key比较大小，采用倒叙，以大到小排序
        return o2.compareTo(o1);
    }
});
comparatorMap.put("4", "d");
comparatorMap.put("3", "c");
comparatorMap.put("1", "a");
comparatorMap.put("2", "b");
System.out.println("自定义 排序结果:" + comparatorMap.toString());

}

输出结果：

默认 排序结果:{1=a, 2=b, 3=c, 4=d}

自定义 排序结果:{4=d, 3=c, 2=b, 1=a}

相信使用过TreeMap的朋友，一定知道TreeMap会自动将key按照一定规则进行排序，TreeSet正是使用了TreeMap这种特性，来实现添加的元素集合，在输出的时候，其结果是已经排序好的。

如果您没看过源码TreeMap的实现过程，可以参阅集合系列文章中TreeMap的实现过程介绍，或者阅读 jdk 源码。

remove方法

TreeSet 的删除方法，同样如此，也是基于 TreeMap 的底层实现，源码如下：

public boolean remove(Object o) {

//调用TreeMap 的remove方法，移除元素
    return m.remove(o)==PRESENT;

}

查询方法

TreeSet 没有重写 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：

public static void main(String[] args) {

Set<String> treeSet = new TreeSet<>();
System.out.println("treeSet初始容量大小："+treeSet.size());
treeSet.add("1");
treeSet.add("4");
treeSet.add("3");
treeSet.add("8");
treeSet.add("5");

System.out.println("treeSet容量大小："+treeSet.size());
//迭代器遍历
Iterator<String> iterator = treeSet.iterator();
while (iterator.hasNext()){
    String str = iterator.next();
    System.out.print(str + ",");
}

System.out.println("/n===========");
//增强for循环
for (String str : treeSet) {
    System.out.print(str + ",");
}

}

输出结果：

treeSet初始容量大小：0

treeSet容量大小：5

1,3,4,5,8,

1,3,4,5,8,

自定义排序

使用自定义排序，有 2 种方法，第一种在需要添加的元素类，实现Comparable接口，重写compareTo方法来实现对元素进行比较，实现自定义排序。

方法一

/**

  • 创建实体类Person实现Comparable接口

*/

public class Person implements Comparable<Person>{

private int age;
private String name;
public Person(String name, int age){
    this.name = name;
    this.age = age;
}
@Override
public int compareTo(Person o){
    //重写 compareTo 方法，自定义排序算法
    return this.age-o.age;
}
@Override
public String toString(){
    return name+":"+age;
}

}

创建一个Person实体类，实现Comparable接口，重写compareTo方法，通过变量age实现自定义排序 测试方法如下：

public static void main(String[] args) {

Set<Person> treeSet = new TreeSet<>();
System.out.println("treeSet初始容量大小："+treeSet.size());
treeSet.add(new Person("李一",18));
treeSet.add(new Person("李二",17));
treeSet.add(new Person("李三",19));
treeSet.add(new Person("李四",21));
treeSet.add(new Person("李五",20));

System.out.println("treeSet容量大小："+treeSet.size());
System.out.println("按照年龄从小到大，自定义排序结果：");
//迭代器遍历
Iterator<Person> iterator = treeSet.iterator();
while (iterator.hasNext()){
    Person person = iterator.next();
    System.out.print(person.toString() + ",");
}

}

输出结果：

treeSet初始容量大小：0

treeSet容量大小：5

按照年龄从小到大，自定义排序结果：

李二:17,李一:18,李三:19,李五:20,李四:21,

方法二

第二种方法是在TreeSet初始化阶段，Person不用实现Comparable接口，将Comparator接口以内部类的形式作为参数，初始化进去，方法如下：

public static void main(String[] args) {

//自定义排序
Set<Person> treeSet = new TreeSet<>(new Comparator<Person>(){
    @Override
    public int compare(Person o1, Person o2) {
        if(o1 == null || o2 == null){
            //不用比较
            return 0;
        }
        //从小到大进行排序
        return o1.getAge() - o2.getAge();
    }
});
System.out.println("treeSet初始容量大小："+treeSet.size());
treeSet.add(new Person("李一",18));
treeSet.add(new Person("李二",17));
treeSet.add(new Person("李三",19));
treeSet.add(new Person("李四",21));
treeSet.add(new Person("李五",20));

System.out.println("treeSet容量大小："+treeSet.size());
System.out.println("按照年龄从小到大，自定义排序结果：");
//迭代器遍历
Iterator<Person> iterator = treeSet.iterator();
while (iterator.hasNext()){
    Person person = iterator.next();
    System.out.print(person.toString() + ",");
}

}

输出结果：

treeSet初始容量大小：0

treeSet容量大小：5

按照年龄从小到大，自定义排序结果：

李二:17,李一:18,李三:19,李五:20,李四:21,

需要注意的是，TreeSet不能添加为空的元素，否则会报空指针错误！

05. EnumSet

EnumSet 是一个与枚举类型一起使用的专用 Set 集合，继承自AbstractSet抽象类。与 HashSet、LinkedHashSet 、TreeSet 不同的是，EnumSet 元素必须是Enum的类型，并且所有元素都必须来自同一个枚举类型，EnumSet 定义源码如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>

implements Cloneable, java.io.Serializable {
......

}

EnumSet是一个虚类，不能直接通过实例化来获取对象，只能通过它提供的静态方法来返回EnumSet实现类的实例。

EnumSet的实现类有两个，分别是RegularEnumSet、JumboEnumSet两个类，两个实现类都继承自EnumSet。

EnumSet会根据枚举类型中元素的个数，来决定是返回哪一个实现类，当 EnumSet元素中的元素个数小于或者等于64，就会返回RegularEnumSet实例；当EnumSet元素个数大于64，就会返回JumboEnumSet实例。

这一点，我们可以从源码中看出，源码如下：

public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {

Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
    throw new ClassCastException(elementType + " not an enum");
//当元素个数小于或者等于 64 的时候，返回 RegularEnumSet
if (universe.length <= 64)
    return new RegularEnumSet<>(elementType, universe);
else
    //大于64，返回 JumboEnumSet
    return new JumboEnumSet<>(elementType, universe);

}

noneOf是EnumSet中一个静态方法，用于判断是返回哪一个实现类。

我们来看看当元素个数小于等于64的时候，使用RegularEnumSet的类，源码如下：

class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {

/**元素为long型*/
private long elements = 0L;

/**添加元素*/
public boolean add(E e) {
    typeCheck(e);

    long oldElements = elements;
    //二进制运算，获取元素
    elements |= (1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

}

RegularEnumSet 通过二进制运算得到结果，直接使用long来存放元素。

我们再来看看当元素个数大于64的时候，使用JumboEnumSet的类，源码如下：

class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {

/**元素为long型*/
private long elements = 0L;

/**添加元素*/
public boolean add(E e) {
    typeCheck(e);

    int eOrdinal = e.ordinal();
    int eWordNum = eOrdinal >>> 6;

    long oldElements = elements[eWordNum];
    //二进制运算
    elements[eWordNum] |= (1L << eOrdinal);
    //使用数组来操作元素
    boolean result = (elements[eWordNum] != oldElements);
    if (result)
        size++;
    return result;
}

}

JumboEnumSet 也是通过二进制运算得到结果，使用long来存放元素，但是它是使用数组来存放元素。

二者相比，RegularEnumSet 效率比 JumboEnumSet 高些，因为操作步骤少，大多数情况下返回的是 RegularEnumSet，只有当枚举元素个数超过 64 的时候，会使用 JumboEnumSet。

添加元素：

//新建一个EnumEntity的枚举类型，定义2个参数

public enum EnumEntity {

WOMAN,MAN;

}

创建一个空的 EnumSet：

//创建一个 EnumSet，内容为空

EnumSet<EnumEntity> noneSet = EnumSet.noneOf(EnumEntity.class);

System.out.println(noneSet);

输出结果：

[]

创建一个 EnumSet，并将枚举类型的元素全部添加进去：

//创建一个 EnumSet，将EnumEntity 元素内容添加到EnumSet中

EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class);

System.out.println(allSet);

输出结果：

[WOMAN, MAN]

创建一个 EnumSet，添加指定的枚举元素：

//创建一个 EnumSet，添加 WOMAN 到 EnumSet 中

EnumSet<EnumEntity> customSet = EnumSet.of(EnumEntity.WOMAN);

System.out.println(customSet);

查询元素

EnumSet与HashSet、LinkedHashSet、TreeSet一样，通过迭代器或者 for 循环来遍历元素，方法如下：

EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class);

for (EnumEntity enumEntity : allSet) {

System.out.print(enumEntity + ",");

}

输出结果：

WOMAN,MAN,

06. 总结

HashSet 是一个输入输出无序的 Set 集合，元素不重复，底层基于 HashMap 的 key 来实现，元素可以为空，如果添加的元素为对象，对象需要重写 equals() 和 hashCode() 方法来约束是否为相同的元素。

LinkedHashSet 是一个输入输出有序的 Set 集合，继承自 HashSet，元素不重复，底层基于 LinkedHashMap 的 key来实现，元素也可以为空，LinkedHashMap 使用循环链表结构来保证输入输出有序。

TreeSet 是一个排序的 Set 集合，元素不可重复，底层基于 TreeMap 的 key来实现，元素不可以为空，默认按照自然排序来存放元素，也可以使用 Comparable 和 Comparator 接口来比较大小，实现自定义排序。

EnumSet 是一个与枚举类型搭配使用的专用 Set 集合，在 jdk1.5 中加入。EnumSet 是一个虚类，有2个实现类 RegularEnumSet、JumboEnumSet，不能显式的实例化改类，EnumSet 会动态决定使用哪一个实现类，当元素个数小于等于64的时候，使用 RegularEnumSet；大于 64的时候，使用JumboEnumSet类，EnumSet 其内部使用位向量实现，拥有极高的时间和空间性能，如果元素是枚举类型，推荐使用 EnumSet。

07. 参考

1、JDK1.7&JDK1.8 源码

2、程序园 - java集合－EnumMap与EnumSet

3、 Java极客技术 - https://blog.csdn.net/javagee...

原文  https://segmentfault.com/a/1190000021099376
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
Java入门教程 bootstrap3 CSS Apache基础教程 springboot-demo php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 Struts2教程 MongoDB教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 SpringCloud ANTLR教程 Hive教程 java实例教程 Ant教程 Hazelcast教程 Elastic-Job-Lite XStream教程 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 WebService CXF学习 Hadoop教程 solr教程 JPA教程 ActiveMQ中文指南 Java内存模型 dubbo教程 Linux入门视频教程
近期评论
  1. 1 Spring Boot集成zipkin快速入门Demo
  2. 2 能用365块大洋去解决的事，千万不要用时间
  3. 3 Spring Boot集成atomikos快速入门Demo
  4. 4 Spring Boot集成fastdfs快速入门Demo
  5. 5 Spring Boot集成Https快速入门Demo
  6. 6 Spring Boot集成easypoi快速入门Demo
  7. 7 Spring Boot集成webflux快速入门Demo
  8. 8 Spring Boot集成Graphql快速入门Demo
  9. 9 Spring Boot API 多版本快速入门Demo
  10. 10 Spring Boot内容协商快速入门Demo
网站信息
  • 文章总数：155,459 篇
  • 文件总数：468,740 个
  • 标签总数：2,264 个
  • 分类总数：90 个
  • 留言数量：2,540 条
  • 在线人数：698 人
  • 运行天数：4,193天
  • 最后更新：2024年04月20日08点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG