首页 > 其他分享 >HashSet和CopyOnWriteArraySet

HashSet和CopyOnWriteArraySet

时间:2022-11-11 16:35:07浏览次数:70  
标签:map HashSet CopyOnWriteArrayList boolean CopyOnWriteArraySet public

参考 https://www.jianshu.com/p/f55bf8a8520e

前言

这篇文章的目的如下:

  • HashSet是如何保证元素的不重复和无序
  • HashSet的增删(改查?)原理
  • CopyOnWriteArraySet支持并发的原理
  • CopyOnWriteArraySet的增删(改查?)原理

如果不想看分析过程,可直接拉到文章末尾看结论

先来看看 Set接口

public interface Set<E> extends Collection<E> {
 
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    boolean equals(Object o);
    int hashCode();
} 

我们从以上接口发现Set并没有get和set方法,也就是没有查和改,为什么呢?原因如下:

  • 因为Set是无序的,没有通过index来进行查询
  • 同样是因为Set是无序的,也就是没有办法通过Index来进行修改

1 HashSet如何保证元素不重复?

要弄清楚HashSet如何保证里面的元素不重复,得从以下两个方面入手:

  • 它底层的存储结构是什么?
  • 插入时是如何判断元素是否存在?

当我们弄清楚上面两个问题之后我们也可以明白HashSet为什么是无序的了。

1)HashSet的底层存储逻辑

且看源码:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

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

我们可以看出来HashSet的底层存储结构是一个HashMap,并且HashSet的元素作为该Map的Key进行存储,HashMap的Key的存储是无序并且不可重复,这就解释了HashSet中如何保证元素不重复

2)插入逻辑

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

直接put到map当中

3)总结

由以上内容我们可以知道HashSet的底层存储结构是HashMap,并且插入到HashSet中元素作为map的key进行存储,这就保证HashSet的一下特点:

  • HashSet中的元素不重复的
  • HashSet中的元素是无序的

2 HashSet增删(改查?)原理

我们从上一小节了解到HashSet的底层存储结构是HashMap,那么它的增删也就是map的put和remove

1)增

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

直接put到map当中

2)删

public boolean remove(Object o) {return map.remove(o)==PRESENT;} 

直接在map中移除即可,非常简单

3 CopyOnWriteArraySet为什么能支持并发?

在搞清楚_CopyOnWriteArraySet为什么能支持并发_ 这个问题之前,我们先来想想以下几个问题:

  • HashSet对应的并发类为什么叫CopyOnWriteArraySet,而不是叫CopyOnWriteHashSet呢?
  • CopyOnWriteArraySet和CopyOnWriteArrayList有没有关系?

我想一旦我们弄清楚上面两个问题我们就是知道 CopyOnWriteArraySet为什么能支持并发?

先来看看CopyOnWriteArraySet的部分源码:

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;

    private final CopyOnWriteArrayList<E> al;

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

从源码中神奇地发现CopyOnWriteArraySet的底层存储结构竟然是CopyOnWriteArrayList,那么我们就可以知道它的名字的由来了,并且知道它支持并发的原理跟CopyOnWriteArrayList是一样的。

附:CopyOnWriteArrayList原理解析

4 CopyOnWriteArraySet的增删(改查?)原理

1)增

public boolean add(E e) {
    return al.addIfAbsent(e);
} 

看方法名我们就是如果CopyOnWriteArrayList中不存在某元素才会添加成功

2)删

public boolean remove(Object o) {
    return al.remove(o);
} 

直接从CopyOnWriteArrayList中移除

5 总结

  • HashSet是如何保证元素的不重复和无序

答:因为HashSet的底层存储结构是HashMap,并且HashSet中的元素是作为Map的Key存储到Map中,所以HashMap中Key是不重复且无序,所以HashSet中的元素也就是不重复和无序的

  • HashSet的增删(改查?)原理

HashSet的增删原理很简单,就是map的put和remove,为什么没有改查呢?那是因为HashSet中的元素是无序的,没办法根据索引进行查询和修改

  • CopyOnWriteArraySet支持并发的原理

CopyOnWriteArraySet之所以叫CopyOnWriteArraySet,是因为它的底层存储结构是CopyOnWriteArrayList,同时也就是保证了它的并发安全性

  • CopyOnWriteArraySet的增删(改查?)原理

CopyOnWriteArraySet继承了AbstractSet,跟HashSet一样只有增删,没有改查,增删原理也就是调用CopyOnWriteArrayList的增删方法,只不过增的时候需要判断一下List中是否存储该元素

标签:map,HashSet,CopyOnWriteArrayList,boolean,CopyOnWriteArraySet,public
From: https://www.cnblogs.com/kuangke/p/16880900.html

相关文章

  • C# Hashtable、HashSet和Dictionary的区别
    原文网址:https://blog.csdn.net/yyyyz999/article/details/1248512251.Hashtable哈希表(HashTable)表示键/值对的集合。在.NETFramework中,Hashtable是System.Collect......
  • 数组还是HashSet?
    我记得大约在半年前,有个朋友问我一个问题,现在有一个选型:一个性能敏感场景,有一个集合,需要确定某一个元素在不在这个集合中,我是用数组直接Contains还是使用HashSet<T>.Cont......
  • Java的HashSet和HashMap性能选项
    Java的HashSet和HashMap性能选项1.*HashSet和HashMap的性能选项对于HashSet及其子类而言,它们采用hash算法来决定集合中元素的存储位置,并通过hash算法来控制集合的大小;对......
  • HashSet实现类的使用
    【1】放入Integer类型数据packagecom.msb.test06;importjava.util.HashSet;/***@author:liu*日期:10:36:57*描述:IntelliJIDEA*版本:1.0*/publi......
  • C# HashSet不要遍历或者使用泛型扩展方法
    C#的接口IEnumerable定义了GetEnumerator方法,它的拓展方法是都是基于这个迭代器实现的。当我们使用比如,First、Where等泛型方法时,会实例化一个迭代器Enumerator包含......
  • JAVA___HashSet底层原理
    HashCode和equalsHashSet通过hashCode确定元素存储的位置,如果该位置没有元素就直接放入,有元素的话需要利用equals方法比较两个元素是否相同,如果不相同利用链表将两个元素......
  • HashSet集合 Array sort方法 学习 剑指offer 练习1
    HashSet集合是基于HashMap来实现的,不允许有重复的元素        允许有NULL值 无序,不会记录插入的顺序HashSet实例化对象  HashSet<Strin......
  • CopyOnWriteArrayList与CopyOnWriteArraySet详解
    什么是CopyOnWrite容器【1】CopyOnWrite容器是基于并发模式Copy-on-Write模式(最简单的并发解决方案)实现的用于避免共享的数据集合。【2】CopyOnWrite容器又被成......
  • java基础HashSet 集合TreeSet集合
           ......
  • HashSet存储重复元素流程图和LinkedHashSet集合
    代码:publicstaticvoidmain(String[]args){HashSet<String>set=newHashSet<>();Strings1=newString("abc");Strings2=newString("abc");se......