Talk is cheap , show me your code!
欢迎来到付振南Java博客,让我们一起学习Java吧!

Java集合之Set详解 HashSet底层原理以及如何检查重复?

Java集合之Set详解

前面我们说了Java集合里面的list,现在我们再来说说set。我们知道list是可以重复的,而set是不能重复的。set和list都是继承自Collection接口,set有很多实现类,比如我们常用的HashSet,TreeSet,LinkedHashSet,CopyOnArraySet和ConcurrentSkipListSet跳表等。

HashSet

基本概念

HashSet是线程不安全的,其实本质上是用的HashMap来实现的,无论我们是有参还是无参构造,底层new的都是一个HashMap,下面请看代码!
无参构造:

    /**
     * Constructs a new, empty set; the backing {@code HashMap} instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

有参构造:

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

所以说掌握了HashMap,HashSet理解起来就非常 容易了。

HashSet add元素的实现方式

前面我们说了,HashSet底层是通过HashMap来实现的,但是HashMap往里面添加元素的时候是通过put key,value键值对方式实现的,而不论是list和set添加元素的时候都是添加的对象,那么HashSet的add方法是如何实现的呢?我们先来看源码:

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

从这个add方法中我们可以看到,HashSet的add方法调用的还是HashMap的put方法,key是要add的元素,但是这个value是一个叫做PERSENT的东西,那么这到底是个什么东西呢?
private static final Object PRESENT = new Object();
其实value就是一个Object类型的常量值。
所以HashSet的add方法是调用HashMap的put方法来实现的,只不过key是要add的元素,value是一个object常量值。

HashSet是如何检查重复元素的呢?

前面我们说到,set这个集合的最大特点就是元素不能重复,那么在HashSet中add的时候,是怎么去检查重复元素的呢?

计算HashCode值找到对象索引位置

首先,当add元素的时候,通过HashCode方法来计算key的哈希码,找到要存放该对象的索引位置。

判断HashCode是否存在

计算key的HashCode值之后会和已经存在set集合中的元素的HashCode值作比较,如果没有重复的,HashSet就会假设这个元素没有重复,就会add进来。

调用equals方法判断对象是否相等

如果很不幸HashCode值已经存在了,那么就会调用equals方法来判断HashCode值相等的两个对象是否真的相同,如果一样说明已经存在了,就不会add进来,如果不一样就会add进来。

多线程环境下使用HashSet

由于HashSet是非线程安全的,在多线程环境下使用肯定会出现错误的。
java.util.ConcurrentModificationException
那么如何在多线程环境下使用它呢?
其实跟ArrayList多线程解决方案是差不多的。第一种就是通过Collections工具类里面的SynchronizedSet方法,第二种就是使用juc里面的CopyOnWriteArraySet

阅读CopyOnWriteArraySet的源码你会发现,其实CopyOnWriteArraySet本质上用的还是CopyOnWriteArrayList。

    /**
     * Creates an empty set.
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

LinkedHashSet

既然我们知道了HashSet是通过HashMap来实现的,那么我们可以大胆猜测LinkedHashSet是通过LinkedHashMap来实现的,事实上也正是这样的。

LinkedHashSet是继承了HashSet,HashSet是通过HashMap来实现的,大致就可以理解为LinkedHashSet内部是通过LinkedHashMap来实现的。

TreeSet

TreeSet是有序的集合,继承了SortedSet,底层是通过红黑树来实现的,红黑树就是一棵自平衡二叉树,因为本身我不常用,这里就不多讲了。

赞(3) 打赏
未经允许不得转载:付振南Java博客 » Java集合之Set详解

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏