ConcurrentSkipListMap介绍
ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。
ConcurrentSkipListMap和TreeMap,它们虽然都是有序的哈希表。但是,第一,它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。第二,ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。
关于跳表(Skip List),它是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。
ConcurrentSkipListMap原理和数据结构
ConcurrentSkipListMap的数据结构,如下图所示:
说明:
先以数据“7,14,21,32,37,71,85”序列为例,来对跳表进行简单说明。
跳表分为许多层(level),每一层都可以看作是数据的索引,这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的,上一层数据是下一层数据的子集,并且第一层(level 1)包含了全部的数据;层次越高,跳跃性越大,包含的数据越少。
跳表包含一个表头,它查找数据时,是从上往下,从左往右进行查找。现在“需要找出值为32的节点”为例,来对比说明跳表和普遍的链表。
情况1:链表中查找“32”节点
路径如下图1-02所示:
需要4步(红色部分表示路径)。
情况2:跳表中查找“32”节点
路径如下图1-03所示:
忽略索引垂直线路上路径的情况下,只需要2步(红色部分表示路径)。
下面说说Java中ConcurrentSkipListMap的数据结构。
(01) ConcurrentSkipListMap继承于AbstractMap类,也就意味着它是一个哈希表。
(02) Index是ConcurrentSkipListMap的内部类,它与“跳表中的索引相对应”。HeadIndex继承于Index,ConcurrentSkipListMap中含有一个HeadIndex的对象head,head是“跳表的表头”。
(03) Index是跳表中的索引,它包含“右索引的指针(right)”,“下索引的指针(down)”和“哈希表节点node”。node是Node的对象,Node也是ConcurrentSkipListMap中的内部类。
ConcurrentSkipListMap函数列表
// 构造一个新的空映射,该映射按照键的自然顺序进行排序。ConcurrentSkipListMap()// 构造一个新的空映射,该映射按照指定的比较器进行排序。ConcurrentSkipListMap(Comparator<? super K> comparator)// 构造一个新映射,该映射所包含的映射关系与给定映射包含的映射关系相同,并按照键的自然顺序进行排序。ConcurrentSkipListMap(Map<? extends K,? extends V> m)// 构造一个新映射,该映射所包含的映射关系与指定的有序映射包含的映射关系相同,使用的顺序也相同。ConcurrentSkipListMap(SortedMap<K,? extends V> m)// 返回与大于等于给定键的最小键关联的键-值映射关系;如果不存在这样的条目,则返回 null。Map.Entry<K,V> ceilingEntry(K key)// 返回大于等于给定键的最小键;如果不存在这样的键,则返回 null。K ceilingKey(K key)// 从此映射中移除所有映射关系。void clear()// 返回此 ConcurrentSkipListMap 实例的浅表副本。ConcurrentSkipListMap<K,V> clone()// 返回对此映射中的键进行排序的比较器;如果此映射使用键的自然顺序,则返回 null。Comparator<? super K> comparator()// 如果此映射包含指定键的映射关系,则返回 true。boolean containsKey(Object key)// 如果此映射为指定值映射一个或多个键,则返回 true。boolean containsValue(Object value)// 返回此映射中所包含键的逆序 NavigableSet 视图。NavigableSet<K> descendingKeySet()// 返回此映射中所包含映射关系的逆序视图。ConcurrentNavigableMap<K,V> descendingMap()// 返回此映射中所包含的映射关系的 Set 视图。Set<Map.Entry<K,V>> entrySet()// 比较指定对象与此映射的相等性。boolean equals(Object o)// 返回与此映射中的最小键关联的键-值映射关系;如果该映射为空,则返回 null。Map.Entry<K,V> firstEntry()// 返回此映射中当前第一个(最低)键。K firstKey()// 返回与小于等于给定键的最大键关联的键-值映射关系;如果不存在这样的键,则返回 null。Map.Entry<K,V> floorEntry(K key)// 返回小于等于给定键的最大键;如果不存在这样的键,则返回 null。K floorKey(K key)// 返回指定键所映射到的值;如果此映射不包含该键的映射关系,则返回 null。V get(Object key)// 返回此映射的部分视图,其键值严格小于 toKey。ConcurrentNavigableMap<K,V> headMap(K toKey)// 返回此映射的部分视图,其键小于(或等于,如果 inclusive 为 true)toKey。ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive)// 返回与严格大于给定键的最小键关联的键-值映射关系;如果不存在这样的键,则返回 null。Map.Entry<K,V> higherEntry(K key)// 返回严格大于给定键的最小键;如果不存在这样的键,则返回 null。K higherKey(K key)// 如果此映射未包含键-值映射关系,则返回 true。boolean isEmpty()// 返回此映射中所包含键的 NavigableSet 视图。NavigableSet<K> keySet()// 返回与此映射中的最大键关联的键-值映射关系;如果该映射为空,则返回 null。Map.Entry<K,V> lastEntry()// 返回映射中当前最后一个(最高)键。K lastKey()// 返回与严格小于给定键的最大键关联的键-值映射关系;如果不存在这样的键,则返回 null。Map.Entry<K,V> lowerEntry(K key)// 返回严格小于给定键的最大键;如果不存在这样的键,则返回 null。K lowerKey(K key)// 返回此映射中所包含键的 NavigableSet 视图。NavigableSet<K> navigableKeySet()// 移除并返回与此映射中的最小键关联的键-值映射关系;如果该映射为空,则返回 null。Map.Entry<K,V> pollFirstEntry()// 移除并返回与此映射中的最大键关联的键-值映射关系;如果该映射为空,则返回 null。Map.Entry<K,V> pollLastEntry()// 将指定值与此映射中的指定键关联。V put(K key, V value)// 如果指定键已经不再与某个值相关联,则将它与给定值关联。V putIfAbsent(K key, V value)// 从此映射中移除指定键的映射关系(如果存在)。V remove(Object key)// 只有目前将键的条目映射到给定值时,才移除该键的条目。boolean remove(Object key, Object value)// 只有目前将键的条目映射到某一值时,才替换该键的条目。V replace(K key, V value)// 只有目前将键的条目映射到给定值时,才替换该键的条目。boolean replace(K key, V oldValue, V newValue)// 返回此映射中的键-值映射关系数。int size()// 返回此映射的部分视图,其键的范围从 fromKey 到 toKey。ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)// 返回此映射的部分视图,其键值的范围从 fromKey(包括)到 toKey(不包括)。ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey)// 返回此映射的部分视图,其键大于等于 fromKey。ConcurrentNavigableMap<K,V> tailMap(K fromKey)// 返回此映射的部分视图,其键大于(或等于,如果 inclusive 为 true)fromKey。ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive)// 返回此映射中所包含值的 Collection 视图。Collection<V> values()
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
- 历年真题答案解析
- 备考技巧名师总结
- 高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
相关文章
发现更多好内容- 如何在 Java 中实现对正方形的缩放操作?(如何在Java中对正方形进行缩放操作)
- 如何正确使用 Java 的 join 方法?(java join方法怎么使用)
- Java 中 DecimalFormat 在哪些场景下使用较为合适?(Java DecimalFormat在哪里使用合适)
- 如何确保Redis客户端的安全性:实用技巧与最佳实践
- 在 JavaScript 中如何使用 parentNode?(javascript中的parentNode怎么用)
- 如何高效编码 Java Supplier 接口?(java supplier接口的高效编码技巧)
- 如何进行 Java NoSQL 查询优化?(java nosql查询优化怎样进行)
- Java 中 `equals()` 的核心究竟是什么?(java eques的核心是什么)
- Java代理模式的优缺点分别有哪些?(Java代理模式有哪些优缺点)
- Java 内存泄露具体有哪些表现呢?(java内存泄露的表现有哪些)