写点什么

精解四大集合框架:Set 核心知识总结

用户头像
田维常
关注
发布于: 2020 年 11 月 02 日

关注Java 后端技术全栈”**


回复“面试”获取全套面试资料


Set 继承于 Collection 接口,是一个不允许出现重复元素,并且无序的集合,主要有 HashSet 和 TreeSet 两大实现类,另外 LinkedHashSet 也有一定的使用频率。


在判断重复元素的时候,Set 集合会调用 hashCode()和 equal()方法来实现。


类图 UML



Set 常用方法


与 List 一样都是接口,Set 接口也提供了集合操作的基本方法。Java 四大集合之一,但与 List 不同的是,Set 还提供了 equals(Object o)和 hashCode(),供其子类重写,以实现对集合中插入重复元素的处理;


 1public interface Set<E> extends Collection<E> { 2    //添加 3    boolean add(E e); 4    boolean addAll(Collection<? extends E> c); 5 6    //删除 7    boolean remove(Object o); 8    boolean removeAll(Collection<?> c); 9    void clear();1011    //长度12    int size();13    //是否为空14    boolean isEmpty();1516    //是否包含17    boolean contains(Object o);18    boolean containsAll(Collection<?> c);19    boolean retainAll(Collection<?> c); 2021    //获取Set集合的迭代器:22    Iterator<E> iterator();2324    //把集合转换成数组25    Object[] toArray();26    <T> T[] toArray(T[] a);2728    //判断元素是否重复,为子类提高重写方法29    boolean equals(Object o);30    int hashCode();31}
复制代码


接口里知识定义了方法,具体的实现请看下面两个常用实现类。


HashSet


HashSet 是用来存储没有重复元素的集合类并且是无序的。实现了 Set 接口。底层其实主要是使用 HashMap 机制实现,所以也是线程不安全


部分源码:


1public class HashSet<E>  extends AbstractSet<E>  implements Set<E>, Cloneable, java.io.Serializable{2    private transient HashMap<E,Object> map;3    //这里这个PRESENT就是作为HashMap中的key4    private static final Object PRESENT = new Object();5    public HashSet() {6        map = new HashMap<>();7    }
复制代码


特征:


  1. 不可重复

  2. 无序

  3. 线程不安全,若多个线程同时操作 HashSet,必须通过代码实现同步;

  4. 集合元素可以是 null,但只能放入一个 null


使用场景:去重、不要求顺序


原理:HashSet 底层由 HashMap 实现,插入的元素被当做是 HashMap 的 key,根据 hashCode 值来确定集合中的位置,由于 Set 集合中并没有角标的概念,所以并没有像 List 一样提供 get()方法。当获取 HashSet 中某个元素时,只能通过遍历集合的方式进行 equals()比较来实现;


常用方法


 1    //添加 2    public boolean add(E e) { 3        return map.put(e, PRESENT)==null; 4    } 5    //移除 6    public boolean remove(Object o) { 7        return map.remove(o)==PRESENT; 8    } 9    //清空10    public void clear() {11        map.clear();12    }13    //获取迭代器14    public Iterator<E> iterator() {15        return map.keySet().iterator();16    }17    //判断是否为空18    public boolean isEmpty() {19        return map.isEmpty();20    }21    //求集合大小22    public int size() {23        return map.size();24    }
复制代码


正如上面所说,底层使用 HashMap 的 key 不能重复机制来实现没有重复的 HashSet。


TreeSet


TreeSet 实现了 SortedSet 接口,意味着可以排序,它是一个有序并且没有重复的集合类,底层是通过 TreeMap 实现。TreeSet 并不是根据插入的顺序来排序,而是字典自然排序。线程不安全。从名字上可以看出,此集合的实现和树结构有关。与 HashSet 集合类似,TreeSet 也是基于 Map 来实现,具体实现 TreeMap(后面讲解),其底层结构为红黑树(特殊的二叉查找树)。


TreeSet 支持两种排序方式:自然升序排序自定义排序


部分源码


 1public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{ 2 3    private transient NavigableMap<E,Object> m; 4 5    private static final Object PRESENT = new Object(); 6 7    TreeSet(NavigableMap<E,Object> m) { 8        this.m = m; 9    }1011    public TreeSet() {12        this(new TreeMap<E,Object>());13    }
复制代码


常用方法



 `1 //求集合大小 2 public int size() { 3     return m.size(); 4 } 5 //判断是否为空 6 public boolean isEmpty() { 7     return m.isEmpty(); 8 } 9 //判断是否包含10 public boolean contains(Object o) {11     return m.containsKey(o);12`

复制代码


特征:


  1. 不可重复

  2. 有序,默认自然升序排序

  3. 线程不安全,若多个线程同时操作 HashSet,必须通过代码实现同步;

  4. 集合元素不可以为 null

  5. 对插入的元素进行排序,是一个有序的集合(主要与 HashSet 的区别);

  6. 底层使用红黑树结构,而不是哈希表结构;


原理:


TreeSet 底层是基于 treeMap(红黑树结构)实现的,可以自定义比较器对元素进行排序,或是使用元素的自然顺序。


使用场景:去重、要求排序


LinkedHashSet


LinkedHashSet 是使用 HashSet 机制实现,它是一个可以保证插入顺序或是访问顺序,并且没有重复的集合类。线程不安全


数据结构:数组 + 双向链表,Entry 结构:before|hash|key|value|next|after,before 和 after 用于维护整个双向链表。


部分源码


 1public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { 2 3    public LinkedHashSet(int initialCapacity, float loadFactor) { 4        super(initialCapacity, loadFactor, true); 5    } 6 7    public LinkedHashSet(int initialCapacity) { 8        super(initialCapacity, .75f, true); 9    }1011    public LinkedHashSet() {12        super(16, .75f, true);13    }
复制代码


常用方法



从这里可以看出,这家伙基本上都是使用 HashSet 来实现的,所以常用方法和 HashSet 相同。


特征:


  1. 集合元素不可以为 null;

  2. 线程不安全。


原理:


LinkedHashSet 底层使用了 LinkedHashMap 机制(比如 before 和 after),加上又继承了 HashSet,所以可以实现既可以保证迭代顺序,又可以达到不出现重复元素。


使用场景:去重、需要保证插入或者访问顺序


HashSet、TreeSet、LinkedHashSet 的区别


  • HashSet 只去重

  • TreeSet 去重并排序

  • LinkedHashSet 去重并保证迭代顺序。


发布于: 2020 年 11 月 02 日阅读数: 54
用户头像

田维常

关注

关注公众号:Java后端技术全栈,领500G资料 2020.10.24 加入

关注公众号:Java后端技术全栈,领500G资料

评论

发布
暂无评论
精解四大集合框架:Set核心知识总结