一、各种树简介#

红黑树#

它可以在 O(logn) 时间内完成查找，插入和删除，这里的n是树中元素的数目.

常考五个性质

自编顺口溜：有红有黑，头黑尾黑，红后黑，任尾同黑

1. 结点是红色或黑色
2. 根结点始终是黑色
3. 叶子结点（NIL 结点）都是黑色
4. 红色结点的两个直接孩子结点都是黑色（即从叶子到根的所有路径上不存在两个连续的红色结点）
5. 从任一结点到每个叶子的所有简单路径都包含相同数目的黑色结点

保证了红黑树在满足平衡二叉树特征的前提下，还可以做到 从根到叶子的最长路径最多不会超过最短路径的两倍。

AVL树#

AVL树定义:
二叉排序树，其中每一个结点的左子树和右子树的高度差不超过1（小于等于1）。

二叉树的平衡因子 （Balance Factor） 等于该结点的左子树深度减去右子树深度的值称为平衡因子。平衡因子只可能是－1，0，1。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

红黑树和AVL树都是从树的平衡性出发，找到合适的平衡方式，一个通过颜色标识限定，一个通过树高差限定，使树都处于平衡状态。

AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

B树#

B树相对于红黑树的区别

在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。

B树的数据结构就是为内外存的数据交互准备的。
外存（如硬盘）是将 所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面 。如果要处理的硬盘数据量很大，无法一次全部装入内存中，就要对B树进行调整，是的B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配。比如一棵B树的阶为1001（1个结点可以包含1000个元素），高度为2，它可以存储超过10亿（1000X1000X1000）个关键字，我们只要让根结点持久的保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取。通过这种方式，在有限内存的情况下，每一次磁盘的访问都可以获得最大数量的数据。

二、各树操作代价#

整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。

RBT 的操作代价分析#

(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。

(2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。

(3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。

RBT 效率总结 :

查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。
插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。

AVL 的操作代价分析#

(1) 查找代价： AVL是严格平衡的BST（平衡因子不超过1）。那么查找过程与BST一样，只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好，最坏情况都是O(logN)数量级的。

(2) 插入代价： AVL必须要保证严格平衡(|bf|<=1)，那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上，AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。

(3) 删除代价：AVL删除结点的算法可以参见BST的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)

AVL 效率总结

查找的时间复杂度维持在O(logN)，不会出现最差情况
AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。

AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。

B树的操作代价分析#

(1) 查找代价： B-Tree作为一个平衡多路查找树(m-叉)。B树的查找分成两种：一种是从一个结点查找另一结点的地址的时候，需要定位磁盘地址(查找地址)，查找代价极高。另一种是将结点中的有序关键字序列放入内存，进行优化查找(可以用折半)，相比查找代价极低。而B树的高度很小，因此在这一背景下，B树比任何二叉结构查找树的效率都要高很多。而且B+树作为B树的变种，其查找效率更高。

(2)插入代价： B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时，磁盘访问的次数为h(读取搜索路径上的节点)＋2s(回写两个分裂出的新节点)＋1（回写新的根节点或插入后没有导致分裂的节点）。因此，所需要的磁盘访问次数是h+2s+1，最多可达到3h+1。因此插入的代价是很大的。

(3)删除代价：B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h＝（找到包含被删除元素需要h次读访问）+（获取第2至h层的最相邻兄弟需要h-1次读访问）+（在第3至h层的合并需要h-2次写访问）+（对修改过的根节点和第2层的两个节点进行3次写访问）

B-Tree效率总结： 由于考虑磁盘储存结构，B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。

三、AVL与红黑树的对比#

AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势，其应用上也有不同。

结构对比： AVL的结构高度平衡，RBT的结构基本平衡。平衡度AVL > RBT.

查找对比： AVL 查找时间复杂度最好，最坏情况都是O(logN)。

RBT 查找时间复杂度最好为O(logN)，最坏情况下比AVL略差。

插入删除对比： 1. AVL的插入和删除结点很容易造成树结构的不平衡，而RBT的平衡度要求较低。因此在大量数据插入的情况下，RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。

如果需要平衡处理时，RBT比AVL多一种变色操作，而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单，所以在实践中这种变色仍然是非常快速的。

当插入一个结点都引起了树的不平衡，AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后，AVL最多需要logN 次旋转操作，而RBT最多只需要3次。因此两者插入一个结点的代价差不多，但删除一个结点的代价RBT要低一些。

AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。

总体评价：大量数据实践证明，RBT的总体统计性能要好于平衡二叉树。

谈谈你对AQS的理解#

AQS是JUC(java.util.concurrent)中很多同步组件的构建基础，简单来讲，它内部实现主要是状态变量state和一个FIFO队列来完成，同步队列的头结点是当前获取到同步状态的结点，获取同步状态state失败的线程，会被构造成一个结点（或共享式或独占式）加入到同步队列尾部（采用自旋CAS来保证此操作的线程安全），随后线程会阻塞；释放时唤醒头结点的后继结点，使其加入对同步状态的争夺中。

AQS的内部实现#

• state 资源状态
• exclusiveOwnerThread 持有资源的线程
• CLH 同步等待队列。

AQS维护一个共享资源state，内置的同步队列由一个一个的Node结点组成，每个Node结点维护一个prev引用和next引用，分别指向自己的前驱和后继结点。

AQS维护两个指针，分别指向队列头部head和尾部tail

继承自AQS的常见类#

CountDownLatch、ReentrantLock、Semaphore等

AQS的两种实现方式#

独占式&共享式, 这样方便使用者实现不同类型的同步组件，独占式如ReentrantLock，共享式如Semaphore，CountDownLatch，组合式的如ReentrantReadWriteLock。

AQS定义的以下可重写的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

独占式获取同步状态，试着获取，成功返回true，反之为false
protected boolean tryAcquire(int arg) 

独占式释放同步状态，等待中的其他线程此时将有机会获取到同步状态
protected boolean tryRelease(int arg) 
  
共享式获取同步状态，返回值大于等于0，代表获取成功；反之获取失败
protected int tryAcquireShared(int arg) 

共享式释放同步状态，成功为true，失败为false
protected boolean tryReleaseShared(int arg) 

是否在独占模式下被线程占用
protected boolean isHeldExclusively()

独占式

1.tryAcquire方法尝试获取锁，如果成功就返回，如果不成功，走到2.

2.把当前线程和等待状态信息构造成一个Node节点，并将结点放入同步队列的尾部

3.该Node结点在队列中尝试获取同步状态，若获取不到，则阻塞结点线程，直到被前驱结点唤醒或者被中断.

以ReentrantLock为例，state初始化为0，表示未锁定状态。A线程lock()时，会调用tryAcquire()独占该锁并将state+1。此后，其他线程再tryAcquire()时就会失败，直到A线程unlock()到state=0（即释放锁）为止，其它线程才有机会获取该锁。当然，释放锁之前，A线程自己是可以重复获取此锁的（state会累加），这就是可重入的概念。但要注意，获取多少次就要释放多么次，这样才能保证state是能回到零态的

自我实现独占锁示例，待重写方法提供更新state等操作.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import java.util.concurrent.locks.AbstractQueuedSynchronizer;

public class MyLock {


    private final Sync sync = new Sync();

    public void lock() {
        sync.acquire(1);
    }

    public void unlock() {
        sync.release(1);
    }

    public boolean isLocked() {
        return sync.isHeldExclusively();
    }


    private static class Sync extends AbstractQueuedSynchronizer {
        @Override
        protected boolean tryAcquire(int arg) {

            //首先判断状态是否等于=0,如果状态==0，就将status设置为1
            if (compareAndSetState(0,1)) {
                //将当前线程赋值给独占模式的onwer
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }

            return false;

        }

        @Override
        protected boolean tryRelease(int arg) {
            if (getState() == 0) {
                throw new IllegalMonitorStateException();
            }
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }

        @Override
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }
    }
}

共享式

CountDownLatch:
任务分为N个子线程去执行，state也初始化为N（注意N要与线程个数一致）。这N个子线程是并行执行的，每个子线程执行完后countDown()一次，state会CAS减1。等到所有子线程都执行完后(即state=0)，会unpark()主调用线程，然后主调用线程就会从await()函数返回，继续后余动作。

Semaphore:
AQS通过state值来控制对共享资源访问的线程数，有线程请求同步状态成功state值减1，若超过共享资源数量获取同步状态失败，则将线程封装共享模式的Node结点加入到同步队列等待。有线程执行完任务释放同步状态后，state值会增加1，同步队列中的线程才有机会获得执行权。公平锁与非公平锁不同在于公平锁申请获取同步状态前都会先判断同步队列中释放存在Node，若有则将当前线程封装成Node结点入队，从而保证按FIFO的方式获取同步状态，而非公平锁则可以直接通过竞争获取线程执行权。

一般来说，自定义同步器要么是独占方法，要么是共享方式，他们也只需实现tryAcquire-tryRelease、tryAcquireShared-tryReleaseShared中的一种即可。但AQS也支持自定义同步器同时实现独占和共享两种方式，如ReentrantReadWriteLock。

总结

volatile关键字具有许多特性，其中最重要的特性就是保证了用volatile修饰的变量对所有线程的可见性。利用内存屏障使得读写、读读、写写 都不能同时发生, 且不能指令重排。

可见性

当一个线程修改了变量的值，新的值会立刻同步到主内存当中。而其他线程读取这个变量的时候，也会从主内存中拉取最新的变量值。

得益于java语言的先行发生原则（happens-before）
对于一个volatile变量的写操作先行发生于后面对这个变量的读操作。

内存屏障

内存屏障（Memory Barrier）是一种CPU指令。禁止重排序，控制执行顺序，刷新缓存与获取最新主存数据。

hashtable&concurrenthashmap1.7&1.8 总结

HashMap：

它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

HashMap最多只允许一条记录的键为null，允许多条记录的值为null。

HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

结构: 数组 + 链表, 链表长度达到8转化成红黑树

扩容: hashMap的容量达到threshold会触发扩容。扩容前后，哈希桶的长度一定会是2的次方, 这样在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效。

get

查找过程和删除基本差不多， 找到返回节点，否则返回null

源码解析-put函数

系列目录

1. 总览&目录
2. 链表节点NODE
3. 构造函数
4. 扩容函数
5. put
6. remove
7. get
8. 遍历
9. &hashtable

遍历

1.Node implements Map.Entry

2.EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>>

3.迭代器HashIterator实现 expectedModCount = modCount 支持fastfail

remove

1.找到待删除节点，也是分第一个节点就是，红黑树中找该节点，普通链表中找该节点

2.删除节点，分红黑树删除，头节点删除，中间节点删除(包括尾)

3.++modCount, –size

HashMap是非线程安全的，HashTable是线程安全的。