Java容器深入浅出之HashSet、TreeSet和EnumSet-阿里云开发者社区

开发者社区> 开发与运维> 正文

Java容器深入浅出之HashSet、TreeSet和EnumSet

简介: Java集合中的Set接口,定义的是一类无顺序的、不可重复的对象集合。如果尝试添加相同的元素,add()方法会返回false,同时添加失败。Set接口包括3个主要的实现类:HashSet、TreeSet和EnumSet。

Java集合中的Set接口,定义的是一类无顺序的、不可重复的对象集合。如果尝试添加相同的元素,add()方法会返回false,同时添加失败。Set接口包括3个主要的实现类:HashSet、TreeSet和EnumSet。

通过查看Java源码,事实上Java是先实现了Map,然后通过包装一个所有value都为null的集合,形成Set。

HashSet

HashSet基于Hash算法实现,因此存取和查找的性能较好。HashSet的主要特点如下:

1. 无顺序的。与添加顺序不同,并且可变。

2. 线程不安全。

3. 集合元素可以是null

4. HashSet是通过元素的HashCode返回值,来确定元素存储位置。

5. 不可重复。HashSet判断元素是否重复的标准是:该元素对象的HashCode()返回值相等,并且equals()方法相等。换句话说,如果两个元素的equals方法相同,但HashCode返回值不相同,HashSet依然可以添加成功。因此,需要注意:

5.1 用Set类保存的元素,尽量保证其equals相等的同时,HashCode返回的值也相等。 

5.2 当保存引用类型对象的时候,尽量不要修改其实例变量,否则可能会导致Set集合操作失灵。

 1 /*
 2  * 测试HashSet的对象添加规则
 3  */
 4 class A{
 5     //重写类A的equals方法,恒返回true
 6     public boolean equals(Object obj) {
 7         return true;
 8     }
 9 }
10 class B{
11     //重写类B的HashCode方法,恒返回1
12     public int hashCode() {
13         return 1;
14     }
15 }
16 class C{
17     //重写类C的HashCode方法,恒返回2
18     public int hashCode() {
19         return 2;
20     }
21     //重写类C的equals方法,恒返回true
22     public boolean equals(Object obj) {
23         return true;
24     }
25 }
26 public class TestHashSet {
27 
28     public static void main(String[] args) {
29         
30         Set<Object> set = new HashSet<>();
31         //equals相同,HashCode不相同:
32         //两个对象添加到hash表的不同位置
33         set.add(new A());
34         set.add(new A());
35         //HashCode相同, equals不同
36         //此时Hash表会在该HashCode位置,使用链式结构保存这些对象,导致性能下降.
37         set.add(new B());
38         set.add(new B());
39         //C类对象只被添加了一次.
40         set.add(new C());
41         set.add(new C());
42         
43         System.out.println(set);
44 
45     }
46 
47 }

LinkedHashSet

LinkedHashSet是HashSet的子类。虽然同样按照元素的HashCode来确定存储位置,但该类同时使用链表来维护添加顺序,也因此,其性能稍低,但是迭代访问元素时优势较大。

TreeSet

TreeSet底层采用的是红黑树的数据结构,并且是有序的集合。因此,TreeSet增加了访问第一个、前一个、后一个和最后一个的方法,并且提供了3个截取子树的方法。

TreeSet包括两种排序方法:自然排序和定制排序,默认使用自然排序。

 1 public class TestTreeSet {
 2 
 3     public static void main(String[] args) {
 4         TreeSet<Integer> nums = new TreeSet<>();
 5         nums.add(5);
 6         nums.add(2);
 7         nums.add(10);
 8         nums.add(-9);
 9         //输出,此时已按自然排序
10         System.out.println(nums);
11         System.out.println(nums.first());
12         System.out.println(nums.last());
13         //返回<4的子序列
14         System.out.println(nums.headSet(4));
15         //返回>=5的子序列
16         System.out.println(nums.tailSet(5));
17         //返回[-3, 4)的子序列
18         System.out.println(nums.subSet(-3, 4));
19     }
20 
21 }

TreeSet的自然排序

指的是TreeSet会调用元素的compareTo(Object o)方法来比较元素之间的大小关系,然后将集合按升序排列。

当把一个对象加入TreeSet集合中时,会调用compareTo方法与集合中其它对象比较大小,然后根据红黑树结构定位存储位置。如比较相等,则无法添加。

自然排序中判断两个对象是否相等的唯一标准:两个对象通过compareTo方法返回是否为0

因此,当重写两个对象的equals方法时,应当重写其compareTo方法,确保有一致的结果。与HashSet类似,当保存引用类型对象的时候,尽量不要修改其实例变量,否则可能会导致操作失效。

TreeSet的定制排序

创建TreeSet集合的对象时,提供一个Comparator对象与该TreeSet集合关联,由该Comparator对象负责元素集合的排序逻辑。

定制排序中判断两个对象是否相等的标准:Comparator对象中比较两个元素是否返回0

class M{
    int age;

    public M(int age) {
        super();
        this.age = age;
    }

    @Override
    public String toString() {
        return "M [age=" + age + "]";
    }
    
}

public class TestTreeSetComparator {

    public static void main(String[] args) {
        TreeSet<M> ts = new TreeSet<>((o1, o2) -> {
            M m1 = (M)o1;
            M m2 = (M)o2;
            //自定义排序:M对象的age属性越大,对比结果反而越小
            return m1.age > m2.age ? -1 : m1.age < m2.age ? 1 : 0;
        });
        ts.add(new M(5));
        ts.add(new M(-3));
        ts.add(new M(9));
        System.out.println(ts);
    }

}

EnumSet

EnumSet专为枚举类设计,其元素必须是指定枚举类的枚举值,并且不能为null。

EnumSet为有序集合,顺序由枚举值在枚举类中的定义顺序决定。其常用方法如下:

 1 enum Season{
 2     SPRING, SUMMER, FALL, WINTER
 3 }
 4 
 5 public class TestEnumSet {
 6 
 7     public static void main(String[] args) {
 8         //创建一个指定枚举类Season的枚举集合
 9         EnumSet<Season> es1 = EnumSet.allOf(Season.class);
10         System.out.println(es1);
11         //创建一个指定枚举类Season的空集合
12         EnumSet<Season> es2 = EnumSet.noneOf(Season.class);
13         System.out.println(es2);
14         //手动添加枚举值
15         es2.add(Season.WINTER);
16         es2.add(Season.SUMMER);
17         System.out.println(es2);
18         //创建一个指定枚举值的枚举集合
19         EnumSet<Season> es3 = EnumSet.of(Season.SPRING, Season.FALL);
20         System.out.println(es3);
21         //创建一个指定枚举值及顺序的枚举集合
22         EnumSet<Season> es4 = EnumSet.range(Season.SUMMER, Season.WINTER);
23         System.out.println(es4);
24         //创建一个es4集合的其余集合es5, 其中es4+es5=es1
25         EnumSet<Season> es5 = EnumSet.complementOf(es4);
26         System.out.println(es5);        
27     }
28 }

关于HashSet和TreeSet的选择

作为两个Set接口的典型实现,一般的选择考虑点是:

1. 优先选择HashSet,快速满足日常添加、查询的操作。

2. 有迭代需求时,可以考虑LinkedHashSet

3. 当需要一个排序的Set的时候,再考虑TreeSet

4. 操作枚举类时,优先考虑EnumSet

当需要在多线程环境下使用集合,应该使用Collections工具类在创建集合时就封装为线程安全。

SortedSet set = Collections.synchronizedSortedSet(new TreeSet());

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章