红黑树简介 红黑树一种自平衡的二叉树，先了解一下什么是二叉树把。 二叉树的性质 在二叉树的第I层上最多有2i-1(i>=1) 二叉树中如果深度为K，那么该二叉树最多有2k-1个节点（k>=1） n0 = n1+1 其中n0表示度数为0的节点数，n1表示度数为2的节点数 在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整 ...

布隆过滤器简介 布隆过滤器是一个位数组和哈希函数实现的一种数据结构，它相对于其他我们平常用的List，Set等更节省内存空间，不过它存在误判概率。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。 例如申请100万个元素位数组只用10^6/8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间，特别节省空间。...

PriorityBlockingQueue简介 PriorityBlockingQueue是一种优先级，无界堵塞，线程安全的队列，每次出队返回优先级高或低的元素，内部通过堆实现。 源码详解属性分析123456789101112131415161718192021//队列默认大小 private static final int DEFAULT_INITIAL_CA...

堆的定义 堆在逻辑上是一种完全二叉树，物理结构上是一维数组，按照根节点大小分为最大堆和最小堆，如下图。最小堆：所有节点的左右孩子节点都大于或者等于父节点最大堆：所有节点的左右孩子节点都小于或者等于父节点 补充：完全二叉树的性质如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（0<=i<=n）有（注意i的取值）1.如果i=0，则节点是二叉树的根，无双亲，如果...

ArrayBlockingQueue简介

ArrayBlockingQueue是一个有界，堵塞/非堵塞线程安全的队列。它是基于数组实现的，内部通过ReentrantLock独占锁来控制入队出队操作,通过两个条件变量控制队列为空为满的情况。

LinkedBlockingQueue简介 LinkedBlockingQueue类是堵塞/非堵塞（看你用啥方法），有边界线程安全队列。由下类图可以看到他的基本实现。它也是由单向链表实现，也是分别由两个Node指向head和tail，内部还有初始量为0的AtomicInteger的原子变量来计算队列数量。还有两个ReentrantLock独占锁来控制元素入队和出队的原子性。 源码详解成员...

ConcurrentLinkedQueue简介

ConcurrentLinkedQueue是一种无边界非堵塞线程安全的队列，底层通过单向链表实现，线程安全通过CAS操作实现。下图是它的类图关系，它继承了AbstractQueue类，实现Queue接口，具有Queue的基本特性。

该类内部通过两个volatile类型的Node节点来分别指向队列的首，尾节点。

java常用锁类型 常见的锁大致可以分为：乐观锁，悲观锁，排他锁，共享锁，分段锁，自选锁，公平锁，非公平锁等。。今天来学基于CAS非加锁实现的乐观锁 ReentrantLock锁 ReentrantLock类是一种可重入，公平/非公平，独占锁，它于synchronized具有相同的功能和语义，但是它更强大，它支持中断，超时等操作。Sync是ReentrantLock的内部类，他的两个子类分...

AQS简介 AbstractQueuedSynchronizer类简称为（AQS）,它是实现同步器的基本组件，内部使用int类型来表示同步状态，并提供CAS方法来操作这个同步状态。如常用的ReentrantLock/Semaphore/CountDownLatch等等就是基于AQS实现的，用法是通过继承AQS实现其模版方法，然后将子类作为同步组件的内部类。 上图是该类的属性，AQS是一...

JUC简介 在 Java 5.0 提供了 java.util.concurrent （简称JUC ）包，在此包中增加了在并发编程中很常用的实用工具类，用于定义类似于线程的自定义子系统，包括线程池、异步 IO 和轻量级任务框架。提供可调的、灵活的线程池。还提供了设计用于多线程上下文中的 Collection 实现等。 在JUC并发包中包含有AtomicInteger，AtomicLong,...