ClawHub的技术分享

准备新写个文集《JAVA并发容器源码分析》，套路还是采用：先翻译源码，再分析技术实现。写几个常用到的并发容器：ConcurrentHashMap、CopyOnWriteArrayList、LinkedBlockingQueue。 并发容器：是专门针对多线程并发设计的，使用了锁分段技术，只对操作的位置进行同步操作，但是其他没有操作的位置其他线程仍然可以访问，提高了程序的吞吐量。采用了CAS算法、部分代码使用synchronized锁保证线程安全。 ConcurrentHashMapJDK6与JDK7中采用一种更加细粒度的加锁机制Segment“分段锁”，JDK8中采用CAS无锁算法。 CopyOnWriteArrayList对读操作不加锁，对写操作，先复制一份新的集合，在新的集合上面修改，然后将新集合赋值给旧的引用，并通过volatile 保证其可见性，写操作的锁采用：ReentrantLock。 LinkedBlockingQueue通过ReentrantLock实现线程安全，通过Condition实现阻塞和唤醒，基于链表实现的可阻塞的FIFO队列。

文章首发于：clawhub.club 这篇文章学习红黑树的删除操作，阅读分析了几篇关于红黑树删除的文章，好复杂。贴出红黑树的性质： 每个结点要么是红的，要么是黑的。 根结点是黑的。 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。 如果一个结点是红的，那么它的俩个儿子都是黑的。 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 红黑树的删除操作分为两步：一、按照普通的二叉查找树删除节点。 如果删除的节点下只有一个非空子节点，则直接删除这个节点，用它唯一的子节点顶替它的位置。 如果它是叶子节点，直接删除。 如果它有两个子节点且都不为空。则把它的中序遍历后的直接后继节点内容复制到它的位置，它的后继节点不可能有两个非空子节点，这样就转化成上面两种情况了，直接删除这个后继节点。 二、修正红黑树在删除节点之后，红黑树的性质可能遭到破坏，如果删除的是红色节点，对原树没有影响。如果删除的结点是黑色结点，原红黑树的性质可能会被改变，我们要对其做修正操作。 如果删除结点不是树唯一结点，那么删除结点的那一个支的到各叶结点的黑色结 ...

文章首发于：clawhub.club 红黑树插入操作与二叉查找树的插入方式是一样的，之不过插入后，会影响到树的平衡，所以要对树进行旋转和着色操作，使其符合红黑树的5条性质。继续贴上性质： 每个结点要么是红的，要么是黑的。 根结点是黑的。 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。 如果一个结点是红的，那么它的俩个儿子都是黑的。 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 新插入的节点是红色的（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。），插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。 为什么要插入修复？因为插入节点后，会影响到性质4与5。 不会造成性质破坏的插入1插入节点作为根节点直接插入后，将节点设置为黑色。 2插入节点作为根节点的子节点既然能作为根节点的字节点，即数中只有 ...

文章首发于：clawhub.club 数据结构红黑树本质上是一颗二叉查找树，所以基本结构和二叉查找树是一样的。 二叉查找树的数据结构：12345678910111213141516171819202122232425/** * 二叉查找树节点 */private class Node<T> { /** * 值 */ private T value; /** * 频率,如果value相同，则此值+1，去掉了重复的项 */ private int freq; /** * 父节点 */ private Node<T> parent; /** * 左节点 */ private Node<T> left; /** * 右节点 */ private Node<T> right;} 有根据红黑树的以下五条性质可知，它比二叉查找树多了一个颜色属性。 每个结点要么是红的，要么是黑的。 根 ...

文章首发于：clawhub.club 树旋转（英语：Tree rotation）是在二叉树中的一种子树调整操作, 每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合。 当对红黑树进行插入和删除等操作时，对树做了修改，红黑树的条件可能被破坏，需要通过调整使得查找树重新满足红黑树的条件，继续保持它的性质或平衡。调整可以分为两类： 颜色调整，即改变某个节点的颜色； 结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。 left-rotate（左旋）例子一：左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。 例子二：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。 图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。 right-rotate（右旋）例子一：右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。 ...

文章首发于：clawhub.club BST存在的问题：数在插入的时候会导致树的倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。如图： 所以出现了平衡树，其在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。 定义：红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。它的统计性能要好于平衡二叉树（AVL树） 红黑树的特性:（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 注意：(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。(02) ...

文章首发于：clawhub.club 定义SBT(Binary Sort Tree或者Binary Search Tree),二叉查找树，二叉排序树，是有一定性质的二叉树。在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。 性质： 若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； 左、右子树也分别为二叉查找树。 注意： 从特性中可以看出是支持重复值的。如果有重复的值，会影响到查询效率，所以一般在插入的时候，如果碰到重复的值，直接过滤处理。 当二叉查找树以中序遍历时，遍历的结果是一个从小到大排列的顺序。 节点定义Java代码实现： 1234567891011121314151617181920212223242526/** * 节点 */private class Node<V> { /** * 值 */ private V value; ...

文章首发于：clawhub.club 相关源码翻译Node内部类123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) * 基本哈希桶节点，用于大多数条目。(参见下面的TreeNode子类和LinkedHashMap中的Entry子类。) */static class Node<K, V> implements Entry<K, V> { // 哈希值 final int hash; // 键 final K key; // 值 V value; // 写一个Node节点的引用 Node ...

文章首发于：clawhub.club 为什么要有扩容： 随着HashMap中元素的数量增长，计算hash发生碰撞的概率也就越来越大，所产生的链表长度越来越长，这样也就影响到HashMap的性能。 为了保证HashMap的效率，要增加HashMap长度，以减少桶内节点太多。即在某个临界点进行扩容处理。进行扩容，会发生一次重新hash分配，而且会遍历hash表中所有的元素，这是是非常耗时的。在编写程序中，要尽量避免resize。 如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。 临界点选择：当 HashMap 中的 size >= threshold 时，HashMap 就要扩容。 size：HashMap表中包含的键值映射的数目。 threshold：要调整大小的下一个大小的阈值，等于(capacity * loadFactor)。 capacity：HashMap容量 loadFactor：哈希表的加载因子。 源码分析：12345678910111213141516171819202122232425 ...

文章首发于：clawhub.club hash算法的优略直接影响到HashMap的性能。 扰动函数源码：12345678910111213141516171819202122232425262728293031/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits ...