写点什么

Java 集合篇之 set,面试官:请说一说 HashSet、LinkedHashSet、TreeSet 的区别?

作者:EquatorCoco
  • 2024-02-20
    福建
  • 本文字数:2485 字

    阅读完需:约 8 分钟

写在开头


Java 的集合世界中主要由 List,Set,Queue,Map 构成,我们在之前的博文中已经学习了 List,接下来我们继续学习 Set 集合。Set 特点:存取无序,不可以存放重复的元素,不可以用下标对元素进行操作



HashSet


作为 Set 容器的代表子类,HashSet 经常被用到,我们通过源码去分析它


【源码查看】


public class HashSet<E>    extends AbstractSet<E>    implements Set<E>, Cloneable, java.io.Serializable{    private transient HashMap<E,Object> map;     // Dummy value to associate with an Object in the backing Map    private static final Object PRESENT = new Object();     public HashSet() {        map = new HashMap<>();    }     public boolean add(E e) {        return map.put(e, PRESENT)==null;    }     public boolean remove(Object o) {        return map.remove(o)==PRESENT;    }}
复制代码


虽然 HashSet 实现了 Set 接口,但通过源码我们能够看到,它的底层逻辑实现其实依据的是 HashMap,通过操作 map 的 key 值来实现元素的增删改查,下面通过一个小测试类去用下 HashSet。


【代码示例 1】


public class Test {    public static void main(String[] args) throws FileNotFoundException {        // 创建一个新的HashSet        HashSet<Integer> set = new HashSet<>();        // 添加元素        set.add(3);        set.add(4);        set.add(0);        set.add(1);        set.add(4);         // 输出HashSet的元素个数        System.out.println("HashSet size: " + set.size());         // 判断元素是否存在于HashSet中        boolean containsWanger = set.contains(2);        System.out.println(containsWanger);         // 删除元素        boolean removeWanger = set.remove(1);        System.out.println(set);         // 修改元素,需要先删除后添加        boolean removeChenmo = set.remove(3);        boolean addBuChenmo = set.add(4);        System.out.println(removeChenmo && addBuChenmo);         // 输出修改后的HashSet        System.out.println(set);    }}
复制代码


输出:


HashSet size: 4false[0, 3, 4]false[0, 4]
复制代码


由代码结果进一步证明了我们的结论:1、存储数据不重复,但 add 重复数据并不报错,原因是第一个数据会被第二次重复数据覆盖掉;2,无序,很多人发现输出了一个有序的数字集合,这个其实与我们所说的有序是有区别的,在 Set 中的有序无序是指输入的顺序与输出的顺序是否一致 当然,想要实现有序可以通过 LinkedHashSet,底层通过链表记录元素插入顺序。


面试考点这里面其实包含着一个小小的 Java 面试考点,曾经有面试官问过这样的一个问题:


集合中的无序性和不可能重复性的什么意思?


  • 无序性:所谓无序性不等于随机性,也不等于输出无序,就如同上面我们看到的向 HashSet 中随机添加数字,输出是从大到小,看似有序,实际此序非彼序!真正的无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ,而是根据数据的哈希值进行判断。


  • 不可重复性:指添加的元素按照 equals() 判断时 ,返回 false,因此,实现不可重复性,必须要同时重写 equals() 方法和 hashCode() 方法。


LinkedHashSet


那么有的小伙伴会问了:“我就想存一个不重复的数据集合,同时又想要他们有序怎么办呢?”,Java 的开发人员已经早就为你想到了,这个办法就是用 LinkedHashSet!LinkedHashSet 是基于 LinkedHashMap 实现的,并且使用链表维护了元素的插入顺序,具有快速查找、插入和删除操作的优点,又可以维护元素的插入顺序!源码就不带大家看了,咱们直接上测试案例。


【代码示例 2】


LinkedHashSet<String> set = new LinkedHashSet<>();// 添加元素set.add("Hello");set.add("Java");set.add("Build");set.add("Java");System.out.println(set);// 删除元素set.remove("Hello"); // 修改元素set.remove("Java");set.add("java"); // 查找元素boolean bool = set.contains("Build");System.out.println("Build哥:" + bool); //输出System.out.println(set);
复制代码


输出:


[Hello, Java, Build]Build哥:true[Build, java]
复制代码


通过输出结果我们可以得出结论:LinkedHashSet 中的元素不可重复,有序。


TreeSet


通过上面两个集合类我们大概能够猜到,几乎所有的 Set 集合的底层都是通过 Map 去实现,TreeSet 同样是基于 TreeMap 实现,TreeMap 基于红黑树实现,所以 TreeSet 也就自带了排序功能。


 public TreeSet() {        this(new TreeMap<E,Object>());    }
复制代码


【代码示例 3】


public class Test {    public static void main(String[] args) {        // 创建一个 TreeSet 对象        TreeSet<Integer> set = new TreeSet<>();        set.add(3);        set.add(6);        set.add(2);        set.add(1);        set.add(0);        set.add(9);        System.out.println(set);    }}
复制代码


输出:


[0, 1, 2, 3, 6, 9]
复制代码


总结


  1. HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类,都能保证元素唯一,并且都不是线程安全的。

  2. HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表(基于 HashMap 实现)。LinkedHashSet 的底层数据结构是链表和哈希表,元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树,元素是有序的,排序的方式有自然排序和定制排序。

  3. 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景,LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景,TreeSet 用于支持对元素自定义排序规则的场景。

  4. 此外,HashSet、LinkedHashSet 允许有 null 值,TreeSet 不允许有 null 值,当向 TreeSet 插入 null 元素时,TreeSet 使用 compareTo 方法与 null 元素进行比较,报错:java.lang.NullPointerException。


文章转载自:JavaBuild

原文链接:https://www.cnblogs.com/JavaBuild/p/18022332

体验地址:http://www.jnpfsoft.com/?from=001

用户头像

EquatorCoco

关注

还未添加个人签名 2023-06-19 加入

还未添加个人简介

评论

发布
暂无评论
Java集合篇之set,面试官:请说一说HashSet、LinkedHashSet、TreeSet的区别?_Java_EquatorCoco_InfoQ写作社区