前言
前面我们对Java集合框架有了一个基本的认识, 这里我们从几大接口入手, 逐步讲解其实现类; 下面要讲解的是
Set的实现类, 即常用的HashSet,TreeSet和LinkedHashSet
文章源码基于JDK8
Java集合框架系列博客:
正文
一. 概述
需要注意的是, 本文要讲的Set的几个实现类内部都是基于Map实现的, 比如: HashSet基于HashMap, TreeSet基于TreeMap, LinkedHashSet基于LinkedHashMap, Set的value实际上就是Map中的key, 依赖于Map键值的唯一性实现Set中元素的不可重复; 所以在学习Set部分的时候, 只需要了解对应Map的特点和实现就可以了; 因此, 本文也不会详细讲解各Set实现类的代码细节, 而只是对每个实现类的特点进行一个总结
二. HashSet
HashSet内部是基于HashMap实现的, 所以在讲解HashSet之前, 需要先看一下HashMap的实现, 可以参照Java集合框架之HashMap, 该篇文章中详细介绍了HashMap的实现原理和特点, 推荐对HashMap有了一个大致的了解之后再开始往下读 ~
总体而言, HashSet的代码比较简单, 其实现Set元素不重复性其实是利用HashMap键值的唯一性; 当我们存放一个Value的时候, 其实是将该Value当做HashMap中的键值的, 而实现的各种常规操作, 比如: add(), remove(), contains()等, 其实都是间接调用了HashMap中的相应操作
所以, 这里不会去细讲HashSet代码, 了解HashMap之后, 其实是很简单的
这里只是贴一下HashSet的特点:
-
没有重复元素, 允许
null -
不保证
Set的遍历顺序, 不保证元素的存储数据(具体原因可以见上面博客对HashMap的分析) -
对
add(),remove(),contains(),size()方法提供常量时间 -
非同步, 可以使用
Collections.synchronizedSet(new HashSet(...)); -
Iterator遍历的时候, 多线程抛出异常ConcurrentModificationException(遍历过程中修改数据, 但是可以使用Iterator自己提供的remove()方法, 该方法不会造成异常)(原因参见Java集合框架之List中分析)
三. TreeSet
简要总结特点如下:
-
基于
TreeMap实现 -
TreeSet是一个有序的集合类, 默认为自然顺序, 也可根据提供的Comparator排序 -
add(),remove()和contains()需要logN时间(是因为TreeMap是基于红黑树实现的) -
非同步, 可以使用
Collections.synchronizedSortedSet(new TreeSet(...)); -
Iterator抛异常:ConcurrentModificationException
四. LinkedHashSet
LinkedHashSet基于LinkedHashMap, 建议参照LinkedHashMap的源码分析: Java集合框架之LinkedHashMap
总结特点如下:
-
访问有序(
LinkedHashMap特点), 按照元素插入顺序访问(注意, 虽然LinkedHashSet基于LinkedHashMap实现, 而前面的文章分析了LinkedHashMap有两种访问顺序, 但是LinkedHashSet在构造LinkedHashMap的时候使用的默认访问顺序, 即插入顺序(accessOrder = false), 所以LinkedHashSet的访问顺序只有一种, 即元素的插入顺序, 而且需要注意的是, 重复插入元素时是不会改变访问顺序的) -
非同步: 可以使用
Collections.synchronizedSet(new LinkedHashSet(...)); -
对
add(),contains()和remove()提供常量时间(具体可以参见Java集合框架之HashMap中对HashMap的分析)
