并发编程 之 TreeMap ConcurrentSkipListMap set queue源码分析
并发编程 之 TreeMap ConcurrentSkipListMap set queue源码分析
TreeMap ConcurrentSkipListMap
TreeMap
整体结构
treeMap是：数组+红黑树
代码
/*** 红黑树根节点*/
private transient Entry<K,V> root;// 红黑力学
private static final boolean RED = false;
private static final boolean BLACK = true;/*** 树中的节点。Doubles 用作将键值对传递回用户的方法(请参阅Map.Entry)。* @param <K>* @param <V>*/
static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK;}
图示
put方法
/*** 将指定值与此映射中的指定键进行关联。如果该映射以前包含此键的映射关系，那么将替换旧值。* 覆写：类 AbstractMap<K,V> 中的 put* @param key 要与指定值关联的键* @param value 要与指定键关联的值 * @return 与 key 关联的先前值；如果没有针对 key 的映射关系，则返回 null。* （返回 null 还可能表示该映射以前将 null 与 key 关联。） */
public V put(K key, V value) {Entry<K,V> t = root;if (t == null) { // 根节点为空，直接设置为根节点compare(key, key); // 类型(可能为空)检查root = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator; // 获取比较器if (cpr != null) { // 使用指定的比较器do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0) // 左子节点t = t.left;else if (cmp > 0) // 右子节点t = t.right;elsereturn t.setValue(value);} while (t != null);}else { // 使用自然顺序比较器if (key == null) // 如果指定键为 null 并且此映射使用自然顺序，或者其比较器不允许使用 null 键throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0) // 左子节点t = t.left;else if (cmp > 0) // 右节点t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e); // 插入节点esize++;modCount++;return null;
}
ConcurrentSkipListMap
跳表是一个特殊的链表，相比一般的链表，有更高的查找效率，可比拟二叉查找树。
平均期望的查找、插入、删除时间复杂度都是O(log n)，许多优秀软件的数据结构都采用了跳表结构。
Redis的zset；LevelDB、RocksDB、Hbase中的Memtable；Lucene的TerDictionary、Posting List。
整体结构
代码
// 头部索引，整个索引的引用入口
private transient volatile HeadIndex<K,V> head;static final class HeadIndex<K,V> extends Index<K,V> {final int level;//表示索引的层级HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {super(node, down, right);this.level = level;}}static class Index<K,V> {final Node<K,V> node;// 节点数据包含：key/value键值对，next单向链表引用final Index<K,V> down;// 向下的索引volatile Index<K,V> right;// 向右的索引}static final class Node<K,V> {final K key;volatile Object value;volatile Node<K,V> next;}
图示
CAS ABA问题
list set queue
List源码解读
ArrayList解读
ArrayList代码非常好读，其实内部维护了一个动态的数组，是一个非线程安全的类。
数据结构：数组
transient Object[] elementData; // non-private to simplify nested class access
CopyOnWriteArrayList解读
数据结构：数组
/** The lock protecting all mutators 内部有一把锁*/
final transient ReentrantLock lock = new ReentrantLock();private transient volatile Object[] array;//添加时，使用所
public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;//将原数组复制一份，并将数组长度加一Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}
}
//获取时，没有锁
public E get(int index) {return get(getArray(), index);
}
相比较ArrayList除了多了一把lock锁，还有一个写时复制的特性。
-
读取的时候不需要加锁，直接读取即可
-
修改的时候，先获取锁，复制一份数组，然后进行修改，避免读线程和写线程争抢同一个内存地址的资源。
为什么要这样设计？
读写分离：如果只采用一把独占锁控制读写操作，写线程获取到锁，其他线程包括读线程阻塞，反之亦然。改时复制，修
改时不是直接往容器中进行修改，而是先复制一份进行修改，改完后再将原容器的引用指向新的容器，这样写操作则不会
影响到正在读取的线程。
注意的问题：虽然不会产生读的并发安全问题，但会产生数据不一致的问题，写线程没来得及写回内存，读线程就会读到脏数据。
适用场景：适合读多写少的场景，相反写多读少的场合就不合适
Set源码解读
HashSet
通过HashMap来实现的，add方法进来的值，作为HashMap的Key，HashMap的Vlaue用一个Object对象常量进行存放。
CopyOnWriteArraySet
通过CopyOnWriteArrayList.addIfAbsent来实现不能重复的功能
ConcurrentSkipListSet
通过ConcurrentSkipListMap来实现，方式跟HashSet类似，通过ConcurrentSkipListMap的Key保证一致性
Queue源码解读
ArrayBlockingQueue内部维护成员
Object[] item；数组，意味着连续的地址空间，可以重复使用。
takeIndex;putIndex; 下标来进行控制插入、删除访问。
Lock lock; 插入、删除操作都使用的是同一把锁
线程等待条件通知队列：condition
LinkedBlockingQueue内部维护成员
链表：tail/head
两把锁：takeLock、putLock
Condition 分别通过两个锁来获得的。
PriorityBlockingQueue内部维护成员
Object[] queue；数组。
Comparator comparator; 比较器。
Lock lock; 插入、删除操作都使用的是同一把锁。
Condition notEmpty；条件队列
DelayQueue内部维护成员
PriorityQueue q；通过优先队列实现
ReentrantLock lock；一把锁。
Condition available；条件队列。
ConcurrentLinkedQueue内部维护成员
链表：tail/head
无锁：casNext、casTail
无阻塞等待队列
参考资料
算法复杂度：https://blog.csdn.net/user11223344abc/article/details/81485842
红黑树扩展：
https://www.pianshen.com/article/3004315412/
https://blog.csdn.net/yang_yulei/article/details/26066409?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
.pianshen.com/article/3004315412/
https://blog.csdn.net/yang_yulei/article/details/26066409?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
红黑树动画演示地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html