死磕 java集合之ConcurrentSkipListSet源码分析——Set大汇总
问题
(1)ConcurrentSkipListSet的底层是ConcurrentSkipListMap吗?
(2)ConcurrentSkipListSet是线程安全的吗?
(3)ConcurrentSkipListSet是有序的吗?
(4)ConcurrentSkipListSet和之前讲的Set有何不同?
简介
ConcurrentSkipListSet底层是通过ConcurrentNavigableMap来实现的,它是一个有序的线程安全的集合。
源码分析
它的源码比较简单,跟通过Map实现的Set基本是一致,只是多了一些取最近的元素的方法。
为了保持专栏的完整性,我还是贴一下源码,最后会对Set的整个家族作一个对比,有兴趣的可以直接拉到最下面。
// 实现了NavigableSet接口,并没有所谓的ConcurrentNavigableSet接口 public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2479143111061671589L; // 存储使用的map private final ConcurrentNavigableMap<E,Object> m; // 初始化 public ConcurrentSkipListSet() { m = new ConcurrentSkipListMap<E,Object>(); } // 传入比较器 public ConcurrentSkipListSet(Comparator<? super E> comparator) { m = new ConcurrentSkipListMap<E,Object>(comparator); } // 使用ConcurrentSkipListMap初始化map // 并将集合c中所有元素放入到map中 public ConcurrentSkipListSet(Collection<? extends E> c) { m = new ConcurrentSkipListMap<E,Object>(); addAll(c); } // 使用ConcurrentSkipListMap初始化map // 并将有序Set中所有元素放入到map中 public ConcurrentSkipListSet(SortedSet<E> s) { m = new ConcurrentSkipListMap<E,Object>(s.comparator()); addAll(s); } // ConcurrentSkipListSet类内部返回子set时使用的 ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) { this.m = m; } // 克隆方法 public ConcurrentSkipListSet<E> clone() { try { @SuppressWarnings("unchecked") ConcurrentSkipListSet<E> clone = (ConcurrentSkipListSet<E>) super.clone(); clone.setMap(new ConcurrentSkipListMap<E,Object>(m)); return clone; } catch (CloneNotSupportedException e) { throw new InternalError(); } } /* ---------------- Set operations -------------- */ // 返回元素个数 public int size() { return m.size(); } // 检查是否为空 public boolean isEmpty() { return m.isEmpty(); } // 检查是否包含某个元素 public boolean contains(Object o) { return m.containsKey(o); } // 添加一个元素 // 调用map的putIfAbsent()方法 public boolean add(E e) { return m.putIfAbsent(e, Boolean.TRUE) == null; } // 移除一个元素 public boolean remove(Object o) { return m.remove(o, Boolean.TRUE); } // 清空所有元素 public void clear() { m.clear(); } // 迭代器 public Iterator<E> iterator() { return m.navigableKeySet().iterator(); } // 降序迭代器 public Iterator<E> descendingIterator() { return m.descendingKeySet().iterator(); } /* ---------------- AbstractSet Overrides -------------- */ // 比较相等方法 public boolean equals(Object o) { // Override AbstractSet version to avoid calling size() if (o == this) return true; if (!(o instanceof Set)) return false; Collection<?> c = (Collection<?>) o; try { // 这里是通过两次两层for循环来比较 // 这里是有很大优化空间的,参考上篇文章CopyOnWriteArraySet中的彩蛋 return containsAll(c) && c.containsAll(this); } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } } // 移除集合c中所有元素 public boolean removeAll(Collection<?> c) { // Override AbstractSet version to avoid unnecessary call to size() boolean modified = false; for (Object e : c) if (remove(e)) modified = true; return modified; } /* ---------------- Relational operations -------------- */ // 小于e的最大元素 public E lower(E e) { return m.lowerKey(e); } // 小于等于e的最大元素 public E floor(E e) { return m.floorKey(e); } // 大于等于e的最小元素 public E ceiling(E e) { return m.ceilingKey(e); } // 大于e的最小元素 public E higher(E e) { return m.higherKey(e); } // 弹出最小的元素 public E pollFirst() { Map.Entry<E,Object> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } // 弹出最大的元素 public E pollLast() { Map.Entry<E,Object> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); } /* ---------------- SortedSet operations -------------- */ // 取比较器 public Comparator<? super E> comparator() { return m.comparator(); } // 最小的元素 public E first() { return m.firstKey(); } // 最大的元素 public E last() { return m.lastKey(); } // 取两个元素之间的子set public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new ConcurrentSkipListSet<E> (m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } // 取头子set public NavigableSet<E> headSet(E toElement, boolean inclusive) { return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); } // 取尾子set public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); } // 取子set,包含from,不包含to public NavigableSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } // 取头子set,不包含to public NavigableSet<E> headSet(E toElement) { return headSet(toElement, false); } // 取尾子set,包含from public NavigableSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); } // 降序set public NavigableSet<E> descendingSet() { return new ConcurrentSkipListSet<E>(m.descendingMap()); } // 可分割的迭代器 @SuppressWarnings("unchecked") public Spliterator<E> spliterator() { if (m instanceof ConcurrentSkipListMap) return ((ConcurrentSkipListMap<E,?>)m).keySpliterator(); else return (Spliterator<E>)((ConcurrentSkipListMap.SubMap<E,?>)m).keyIterator(); } // 原子更新map,给clone方法使用 private void setMap(ConcurrentNavigableMap<E,Object> map) { UNSAFE.putObjectVolatile(this, mapOffset, map); } // 原子操作相关内容 private static final sun.misc.Unsafe UNSAFE; private static final long mapOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<?> k = ConcurrentSkipListSet.class; mapOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("m")); } catch (Exception e) { throw new Error(e); } } }
可以看到,ConcurrentSkipListSet基本上都是使用ConcurrentSkipListMap实现的,虽然取子set部分是使用ConcurrentSkipListMap中的内部类,但是这些内部类其实也是和ConcurrentSkipListMap相关的,它们返回ConcurrentSkipListMap的一部分数据。
另外,这里的equals()方法实现的相当敷衍,有很大的优化空间,作者这样实现,应该也是知道几乎没有人来调用equals()方法吧。
总结
(1)ConcurrentSkipListSet底层是使用ConcurrentNavigableMap实现的;
(2)ConcurrentSkipListSet有序的,基于元素的自然排序或者通过比较器确定的顺序;
(3)ConcurrentSkipListSet是线程安全的;
彩蛋
Set大汇总:
Set | 有序性 | 线程安全 | 底层实现 | 关键接口 | 特点 |
---|---|---|---|---|---|
HashSet | 无 | 否 | HashMap | 无 | 简单 |
LinkedHashSet | 有 | 否 | LinkedHashMap | 无 | 插入顺序 |
TreeSet | 有 | 否 | NavigableMap | NavigableSet | 自然顺序 |
CopyOnWriteArraySet | 有 | 是 | CopyOnWriteArrayList | 无 | 插入顺序,读写分离 |
ConcurrentSkipListSet | 有 | 是 | ConcurrentNavigableMap | NavigableSet | 自然顺序 |
从中我们可以发现一些规律:
(1)除了HashSet其它Set都是有序的;
(2)实现了NavigableSet或者SortedSet接口的都是自然顺序的;
(3)使用并发安全的集合实现的Set也是并发安全的;
(4)TreeSet虽然不是全部都是使用的TreeMap实现的,但其实都是跟TreeMap相关的(TreeMap的子Map中组合了TreeMap);
(5)ConcurrentSkipListSet虽然不是全部都是使用的ConcurrentSkipListMap实现的,但其实都是跟ConcurrentSkipListMap相关的(ConcurrentSkipListeMap的子Map中组合了ConcurrentSkipListMap);
欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java并发编程之CountDownLatch源码解析
一、导语 最近在学习并发编程原理,所以准备整理一下自己学到的知识,先写一篇CountDownLatch的源码分析,之后希望可以慢慢写完整个并发编程。 二、什么是CountDownLatch CountDownLatch是java的JUC并发包里的一个工具类,可以理解为一个倒计时器,主要是用来控制多个线程之间的通信。 比如有一个主线程A,它要等待其他4个子线程执行完毕之后才能执行,此时就可以利用CountDownLatch来实现这种功能了。 三、简单使用 public static void main(String[] args){ System.out.println("主线程和他的两个小兄弟约好去吃火锅"); System.out.println("主线程进入了饭店"); System.out.println("主线程想要开始动筷子吃饭"); //new一个计数器,初始值为2,当计数器为0时,主线程开始执行 CountDownLatch latch = new CountDownLatch(2); new Thread(){ public void run() { try { Sys...
- 下一篇
使用ConcurrentHashMap一定线程安全?
前言 老王为何半夜惨叫?几行代码为何导致服务器爆炸?说好的线程安全为何还是出问题?让我们一起收看今天的《走进IT》 正文 CurrentHashMap出现背景 说到ConcurrentHashMap的出现背景,还得从HashMap说起。 老王是某公司的苦逼Java开发,在互联网行业中,业务总是迭代得非常快。体现在代码中的话,就是v1.0的模块是单线程执行的,这时候使用HashMap是一个不错的选择。然而到了v1.5的版本,为了性能考虑,老王觉得把这段代码改成多线程会更有效率,那么说改就改,然后就愉快的发布上线了。 直到某天晚上,突然收到线上警报,服务器CPU占用100%。这时候惊醒起来一顿排查(百度,谷歌),结果发现原来是HashMap 在并发的环境下进行rehash的时候会造成链表的闭环,因此在进行get()操作的时候导致了CPU占用100%。喔,原来HashMap不是线程安全的类,在当前的业务场景中会有问题。那么你这时候又想到了Hashtable,没错,这是个线程安全的类,那我先用这个类替换不就行了,一顿commit,push,部署上去了,观察了一段时间,完美~再也没出现过类似的问...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,CentOS8安装Elasticsearch6.8.6
- 2048小游戏-低调大师作品
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7安装Docker,走上虚拟化容器引擎之路
- SpringBoot2全家桶,快速入门学习开发网站教程