1，AQS

全称AbstractQueuedSynchronizer，抽象队列同步器。

当然我看了文章【https://www.cnblogs.com/waterystone/p/4920797.html】，写的真好。

架构图，我们借用下网上的图：

我们这里从使用到源码的方式入手来解析AQS。每个方法的作用及其实现原理。

1.1 独占锁

这里用ReentrantLock分析：

先上测试代码：

public class ReentrantLockTest {
    private static List<Integer> data = new ArrayList<>(50000);
    @Test
    public void test1() throws InterruptedException {
        Thread thread1 = new WithOutThread1();
        Thread thread2 = new WithOutThread2();
        thread1.start();
        thread2.start();
        Thread.sleep(3000);
        System.out.println(data.size());
    }
    public static void main(String args[]) throws InterruptedException {
        ReentrantLock reentrantLoc = new ReentrantLock();
        Thread thread1 = new ReentrantLockThread1(reentrantLoc);
        Thread thread2 = new ReentrantLockThread2(reentrantLoc);
        thread1.start();
        thread2.start();
        Thread.sleep(2000);
        System.out.println(data.size());
    }
    static class ReentrantLockThread1 extends Thread {
        private ReentrantLock reentrantLock;
        public ReentrantLockThread1(ReentrantLock reentrantLock) {
            this.reentrantLock = reentrantLock;
        }
        @Override
        public void run() {
            reentrantLock.lock();
            try {
                 for (int i = 1; i <= 10000; i++) {
                    data.add(i);
                }
                doSomeThing();
            } finally {
                reentrantLock.unlock();
            }
        }
        private void doSomeThing() {
            reentrantLock.lock();
            try {
                for (int i = 10001; i <= 20000; i++) {
                    data.add(i);
                }
            } finally {
                reentrantLock.unlock();
            }
        }
    }
   static class ReentrantLockThread2 extends Thread {
        private ReentrantLock reentrantLock;
        public ReentrantLockThread2(ReentrantLock reentrantLoc) {
            this.reentrantLock = reentrantLoc;
        }
        public ReentrantLockThread2(String name) {
            super(name);
        }
        @Override
        public void run() {
            reentrantLock.lock();
            try {
                Thread.sleep(40000);
                for (int i = 1; i <= 10000; i++) {
                    data.add(i);
                }
                doSomeThing();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                reentrantLock.unlock();
            }
        }
        private void doSomeThing() {
            reentrantLock.lock();
            try {
                 for (int i = 10001; i <= 20000; i++) {
                    data.add(i);
                }
            } finally {
                reentrantLock.unlock();
            }
        }
    }
    class WithOutThread1 extends Thread {
        @Override
        public void run() {
            for (int i = 10001; i <= 20000; i++) {
                data.add(i);
            }
        }
    }
    class WithOutThread2 extends Thread {
        @Override
        public void run() {
            for (int i = 1; i <= 10000; i++) {
                data.add(i);
            }
        }
    }
}

有两个线程模拟并发处理的场景。

lock()方法，获取锁，从这里为入口进入源码分析：

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

这里没什么讲的，进入acquire方法：

此方法是独占模式下线程获取共享资源的顶层入口。如果获取到资源，线程直接返回，否则进入等待队列，直到获取到资源为止，且整个过程忽略中断的影响。这也正是lock()的语义，当然不仅仅只限于lock()。获取到资源后，线程就可以去执行其临界区代码了。

    public final void acquire(int arg) {
        //非公平锁体现在这里，当一个新的线程请求锁的时候，不是先放到队列里面，而是直接先进行抢占，其实就是
        //强插队，插队没插上就乖乖的去后面排队了（进入等待队列）。tryAcquire返回true说明拿到锁了，
        //可以执行临界去的代码了，如果返回false说明获取锁失败，需要进入等待队列，进入
        // acquireQueued(addWaiter(Node.EXCLUSIVE), arg))逻辑,这里的Node.EXCLUSIVE
        //表示独占模式
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

tryAcquire最终调用的是ReentrantLock非公平锁ReentrantLock的nonfairTryAcquire(int acquires)方法

tryAcquire就是通过CAS机制去更改锁内部维护的state变量的值

但是因为这里是一个可重入锁，就是如果当前线程已经获取锁，但是调用的方法又获取锁，就会进入else if逻辑，

就不用通过CAS机制去设置state的值了。

final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

mode有两种：EXCLUSIVE（独占）和SHARED（共享）可以看内部类Node源码

       /** Marker to indicate a node is waiting in shared mode */
        static final Node SHARED = new Node();
        /** Marker to indicate a node is waiting in exclusive mode */
        static final Node EXCLUSIVE = null;

第一次进入该方法（也就是第一个获取锁失败的线程会进入该方法）的时候队列是空的（队头，队尾都是空的）

首先会 new Node(Thread.currentThread(), mode);

Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

然后就会走initializeSyncQueue()方法

通过CAS机制将队头设为new Node()，如果设置成功，队尾也为new Node()

执行完initializeSyncQueue()方法之后，tail就不是null了，就会执行if里面的逻辑

然后将和当前线程绑定的节点node添加到队尾

private Node addWaiter(Node mode) {
    //创建当前线程节点
     Node node = new Node(Thread.currentThread(), mode);
    //尝试快速方式直接放到队尾。
        // Try the fast path of enq; backup to full enq on failure
    //尾节点 为啥这样写的原因https://www.zhihu.com/question/411529864
        Node pred = tail;
    //如果尾节点不为null
        if (pred != null) {
            //将新建的node加入队尾
            node.prev = pred;
            //cas操作tail改为node成功返回
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }
 /**
     * Inserts node into queue, initializing if necessary. See picture above.
     * @param node the node to insert
     * @return node's predecessor
     */
    private Node enq(final Node node) {
        //不断重试
        for (;;) {
            //每次循环开始重新拿一次
            Node t = tail;
            if (t == null) { // Must initialize tail为null说明还未初始化 需要先初始化
                //是直接new的，不关联线程，不参与抢占锁
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

当addWaiter(Node mode)执行完成之后，会将和当前线程绑定的node返回执行acquireQueued(final Node node, int arg)方法了

虽说这里是通过自旋去获取锁，但是这里不是一直无休止的执行，后面当前线程会休息，且看

shouldParkAfterFailedAcquire(p, node)和parkAndCheckInterrupt()方法

final boolean acquireQueued(final Node node, int arg) {
        //初始值 true
    boolean failed = true;
        try {
            boolean interrupted = false;
             //自旋
            //当然这里不是一直无休止的执行，后面当前线程会休息，这个休息就是阻塞当前线程，做到无法
            //执行临界区代码的目的
            for (;;) {
                //每次获取当前线程node的前驱
                final Node p = node.predecessor();
                //先抢占锁
                //如果前驱为队头，则当前结点就有资格去获取锁了（这里是需要被唤醒的，
                //可能是老大释放完资源
                //唤醒自己的，当然也可能被interrupt了）
                if (p == head && tryAcquire(arg)) {
                    //拿到资源后，将head指向该结点。所以head所指的标杆结点，就是当前
                    //获取到资源的那个结点或null。
                    setHead(node);
                    //help GC  setHead中node.prev已置为null，此处再将上一个头节点的
                    //next置为null,因为上一个节点已释放了锁
                    //为了方便GC回收以前的head结点。也就意味着之前拿完资源的结点出队了！
                    p.next = null; 
                    return interrupte;
                }
                //如果自己可以休了，就通过park()进入waiting状态，直到被unpark()。
                //如果不可中断的情况下被中断了，那么会从park()中醒过来，发现拿不到资源，
                //从而继续进入park()等待。
                 if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            // 如果等待过程中没有成功获取资源（如timeout，或者可中断的情况下被中断了），
            //那么取消结点在队列中的等待。
            if (failed)
                cancelAcquire(node);
        }
    }
private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

shouldParkAfterFailedAcquire(p, node)方法

waiteStatus有5中状态：

• CANCELLED(1)：表示当前结点已取消调度。当timeout或被中断（响应中断的情况下），会触发变更为此状态，进入该状态后的结点将不会再变化。
• SIGNAL(-1)：表示后继结点在等待当前结点唤醒。后继结点入队时，会将前继结点的状态更新为SIGNAL。
• CONDITION(-2)：表示结点等待在Condition上，当其他线程调用了Condition的signal()方法后，CONDITION状态的结点将从等待队列转移到同步队列中，等待获取同步锁。
• PROPAGATE(-3)：共享模式下，前继结点不仅会唤醒其后继结点，同时也可能会唤醒后继的后继结点。
• 0：新结点入队时的默认状态。

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        //拿到前驱的状态
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            //如果已经告诉前驱拿完号后通知自己一下，那就可以安心休息了。
            //我们看下面的else方法pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
            //其实循环第二次还没拿到锁，且前面的执行的线程没有取消的情况就会将前驱的状态设置为
            //Node.SIGNAL
            return true;
        if (ws > 0) {
            //如果前驱放弃了，那就一直往前找，直到找到最近一个正常等待的状态，并排在它的后边。
            //注意：那些放弃的结点，由于被自己“加塞”到它们前边，它们相当于形成一个无引用链，
            //稍后就会被保安大叔赶走了(GC回收)！
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            //如果前驱正常，那就把前驱的状态设置成SIGNAL，告诉它拿完号后通知自己一下。
            //有可能失败，人家说不定刚刚释放完呢！
           compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

parkAndCheckInterrupt()方法

private final boolean parkAndCheckInterrupt() {
        //调用park()使线程进入waiting状态
        LockSupport.park(this);
        //如果被唤醒，查看自己是不是被中断的 并且会清理中断状态
        return Thread.interrupted();
    }

到此lock就被剖析完了，流程大概如下：

不过需要提一下tryLock()和tryLock(long timeout,TimeUnit timeUnit)方法

tryLocK()直接调用tryAcquire()方法，如果获取到锁直接返回true如果没获取到返回false。

tryLock(long timeout,TimeUnit timeUnit)给定一个超时时间，如果获取到锁直接返回true如果没获取到返回false。

这两个方法没有拿到锁不会加入等待队列，所以使用的时候需要注意，如果返回false就不应该执行临界去的代码了。只尝试一次

接下来就是lock.unLock()方法了，字面意思释放锁，其实就是修改锁内部维护的state状态。

这段不用讲了，进入realese(1)逻辑

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

如果tryRelease返回true，说明锁释放成功，需要唤醒放在队列中休息的待执行的线程。

首先拿到队列头，如果头不为空，且waitStatus!=0 ,waitStatus正常应该为-1SIGNAL状态，说明后续有线程入队。

且看unparkSuccessor(h)方法

public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

这里每次c=getState-1，判断当前线程是否为持有锁的线程，如果不是抛出异常。

然后如果c==0说明释放成功了，返回true。如果c!=0返回false，且state设为c。

因为可重入锁的state不一定为1，重入一次就会+1，所以释放的时候也需要多次释放。

因为是当前线程持有锁，所以不需要cas操作

protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }

unparkSuccessor(Node node)方法，node为队列头

private void unparkSuccessor(Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         */
        //获取队列头结点状态 一般为当前线程所在结点
        int ws = node.waitStatus;
        if (ws < 0)
           compareAndSetWaitStatus(node, ws, 0);//置零当前线程所在的结点状态，允许失败。
        //找到下一个需要唤醒的结点s
        Node s = node.next; 
        //如果为空或已取消
        if (s == null || s.waitStatus > 0) {
            s = null;
            // 获取队列尾部，从后向前找，因为没有break，所以会一直找到最前面那个有效的结点，
            for (Node p = tail; p != node && p != null; p = p.prev)
                //从这里可以看出，<=0的结点，都是还有效的结点。
                if (p.waitStatus <= 0)
                    s = p;
        }
        if (s != null)
            //唤醒
            LockSupport.unpark(s.thread);
    }

到这里释放锁过程就剖析完了。

一句话概括：用unpark()唤醒等待队列中最前边的那个未放弃线程，这里我们也用s来表示吧。此时，再和acquireQueued()联系起来，s被唤醒后，进入if (p == head && tryAcquire(arg))的判断（即使p!=head也没关系，它会再进入shouldParkAfterFailedAcquire()寻找一个安全点。这里既然s已经是等待队列中最前边的那个未放弃线程了，那么通过shouldParkAfterFailedAcquire()的调整，s也必然会跑到head的next结点，下一次自旋p==head就成立啦），然后s把自己设置成head标杆结点，表示自己已经获取到资源了，acquire()也返回了！！

我们来讲一下ReentrantLock，它有公平锁和非公平锁，默认为非公平锁。

在使用new ReentrantLock(true)生成的就是公平锁。

看一下公平锁的实现

相比非公平锁，多了个hasQueuedPredecessors()判断。

判断队列中是否有有效的待执行的线程，如果有返回true，否则返回false。

如果返回true，而且不是当前线程拿到锁，那么就直接返回false。

 static final class FairSync extends Sync {
        private static final long serialVersionUID = -3000897897090466540L;
        /**
         * Fair version of tryAcquire.  Don't grant access unless
         * recursive call or no waiters or is first.
         */
        @ReservedStackAccess
        protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
    }

相比非公平锁，多了个hasQueuedPredecessors()判断。

判断队列中是否有有效的待执行的线程，如果有返回true，否则返回false。

public final boolean hasQueuedPredecessors() {
    //尾节点
        Node t = tail; // Read fields in reverse initialization order
    //头节点
        Node h = head;
    //头节点的下一个节点
        Node s;
        return h != t &&
            ((s = h.next) == null || s.thread != Thread.currentThread());
    }

结果一: 返回false，不需要排队
情况一： h != t返回false，那么短路与判断就会直接返回false

说明：当头节点和尾节点相等时，才会返回false。
头节点和尾节点都为null，表示队列都还是空的，甚至都没完成初始化，那么自然返回fasle，无需排队。
头节点和尾节点不为null但是相等，说明头节点和尾节点都指向一个元素，表示队列中只有一个节点，这时候自然无需排队，因为队列中的第一个节点是不参与排队的，它持有着同步状态，那么第二个进来的节点就无需排队，因为它的前继节点就是头节点，所以第二个进来的节点就是第一个能正常获取同步状态的节点，第三个节点才需要排队，等待第二个节点释放同步状态。

情况二:h != t返回true，(s = h.next) == null返回false以及s.thread !=
Thread.currentThread()返回false

说明：h != t返回true表示队列中至少有两个不同节点存在。
(s = h.next) == null返回false表示头节点是有后继节点的。
s.thread != Thread.currentThread()返回fasle表示着当前线程和后继节点的线程是相同的，那就说明已经轮到这个线程相关的节点去尝试获取同步状态了，自然无需排队，直接返回fasle。

结果二.返回true
情况一： h != t返回true，(s = h.next) == null返回true

h != t返回true表示队列中至少有两个不同节点存在。
(s = h.next) == null返回true，说明头节点之后是没有后继节点的，这情况可能发生在如下情景：有另一个线程已经执行到初始化队列的操作了，介于compareAndSetHead(new Node())与tail = head之间，如下图：

这时候头节点不为null，而尾节点tail还没有被赋值，所以值为null，所以会满足h != t结果为true的判断，以及头节点的后继节点还是为null的判断，这时候可以直接返回true，表示要排队了，因为在当前线程还在做尝试获取同步状态的操作时，已经有另一个线程准备入队了，当前线程慢人一步，自然就得去排队。

情况二:h != t返回true，(s = h.next) == null返回false，s.thread !=
Thread.currentThread()返回true。

h != t返回true表示队列中至少有两个不同节点存在。
(s = h.next) == null返回false表示首节点是有后继节点的。
s.thread != Thread.currentThread()返回true表示后继节点的相关线程不是当前线程，所以首节点虽然有后继节点，但是后继节点相关的线程却不是当前线程，那当前线程自然得老老实实的去排队。

1.2 共享锁

下面我们来讲一下共享锁：

以CountDownLatch来分析

测试类

public class CountDownLatchTest {
    public static void main(String[] args) throws InterruptedException {
        CountDownLatch countDownLatch = new CountDownLatch(5);
        Thread thread = new Thread(()->{
            for (int i = 5; i > 0; i--) {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(i);
                countDownLatch.countDown();
            }
        });
        thread.start();
        countDownLatch.await();
        System.out.println("hahahha");
    }
}

先看一下CountDownLatch构造方法：

又实例化了一个内部同步类Sync，我们知道Sync继承了AbstractQueuedSynchronizer

public CountDownLatch(int count) {
        if (count < 0) throw new IllegalArgumentException("count < 0");
        this.sync = new Sync(count);
    }

可以看出state=count

实现了AbstractQueuedSynchronizer的tryAcquireShared(int acquires)，tryReleaseShared(int releases)方法

tryAcquireShared(int acquires) 返回负值代表获取失败；0代表获取成功，但没有剩余资源；正数表示获取成功，还有剩余资源，其他线程还可以去获取。

private static final class Sync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = 4982264981922014374L;
        Sync(int count) {
            setState(count);
        }
        int getCount() {
            return getState();
        }
        //返回值只有 1和-1
        protected int tryAcquireShared(int acquires) {
            return (getState() == 0) ? 1 : -1;
        }
        protected boolean tryReleaseShared(int releases) {
            // Decrement count; signal when transition to zero
            //自旋
            for (;;) {
                int c = getState();
                //如果状态为0，说明没有在执行的线程了返回false
                if (c == 0)
                    return false;
                int nextc = c - 1;
                //CAS设置state
                if (compareAndSetState(c, nextc))
                    //如果nextc==0说明，本次线程执行完之后，就没有可执行的线程了，返回true
                    //相当于释放锁
                    return nextc == 0;
            }
        }
    }

我们知道CountDownLatch的await()方法可以阻塞主线程，我们来看看

public void await() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }

最终调用的是tryAcquireShared(arg)方法，之后getState!=0都会返回-1，就是只要还有正在运行的线程就会返回-1。然后就会执行doAcquireSharedInterruptibly(arg)

public final void acquireSharedInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
    }

看到这个代码就有点熟悉，parkAndCheckInterrupt()会使线程睡眠，所以主线程会睡眠，就相当于阻塞了。

private void doAcquireSharedInterruptibly(int arg)
        throws InterruptedException {
        final Node node = addWaiter(Node.SHARED);
        try {
            //自旋
            for (;;) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } catch (Throwable t) {
            cancelAcquire(node);
            throw t;
        }

我们再看一下CountDownLatch的countDown()方法

public void countDown() {
        sync.releaseShared(1);
    }

这里又调用到内部类Sync的tryReleaseShared(arg)方法了

当执行完最后一个线程并调用countDown()之后tryReleaseShared(arg)返回true，说明要释放锁了

执行doReleaseShared()方法

public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

doReleaseShared()方法

我们看到unparkSuccessor(h)会释放唤醒主线程，主线程就会继续执行了

private void doReleaseShared() {
        //自旋
        for (;;) {
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                    if (!h.compareAndSetWaitStatus(Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h);
                }
                else if (ws == 0 &&
                         !h.compareAndSetWaitStatus(0, Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            if (h == head)                   // loop if head changed
                break;
        }
    }

1.3 AQS和synchronized 区别

Java中每一个对象都可以作为锁，这是synchronized实现同步的基础：

1. 普通同步方法，锁是当前实例对象
2. 静态同步方法，锁是当前类的class对象
3. 同步方法块，锁是括号里面的对象

1. 来源：
   lock是一个接口，而synchronized是java的一个关键字，synchronized是内置的语言实现；
2. 异常是否释放锁：
   synchronized在发生异常时候会自动释放占有的锁，因此不会出现死锁；而lock发生异常时候，不会主动释放占有的锁，必须手动unlock来释放锁，可能引起死锁的发生。（所以最好将同步代码块用try catch包起来，finally中写入unlock，避免死锁的发生。）
3. 是否响应中断
   lock等待锁过程中可以用interrupt来中断等待，而synchronized只能等待锁的释放，不能响应中断；
4. 是否知道获取锁
   Lock可以通过trylock来知道有没有获取锁，而synchronized不能；
5. Lock可以提高多个线程进行读操作的效率。（可以通过readwritelock实现读写分离）
6. 在性能上来说，如果竞争资源不激烈，两者的性能是差不多的，而当竞争资源非常激烈时（即有大量线程同时竞争），此时Lock的性能要远远优于synchronized。所以说，在具体使用时要根据适当情况选择。
7. synchronized使用Object对象本身的wait 、notify、notifyAll调度机制，而Lock可以使用Condition进行线程之间的调度
8. Lock可以实现公平锁和非公平锁，synchronized为非公平锁。

2 红黑树

参考博客【https://juejin.im/post/6844904205526777864】

AVL树的特点：

• 具有二叉查找树的特点(左子树任一节点小于父节点，右子树任一节点大于父节点)，任何一个节点的左子树与右子树都是平衡二叉树
• 任一节点的左右子树高度差小于1，即平衡因子为范围为[-1,1]

AVL树比红黑树更加平衡，但AVL树可能在插入和删除过程中引起更多旋转。因此，如果应用程序涉及许多频繁的插入和删除操作，则应首选Red Black树(如 Java 1.8中的HashMap)。如果插入和删除操作的频率较低，而搜索操作的频率较高，则AVL树应优先于红黑树。

红黑树是一种自平衡二叉搜索树（BST），且红黑树节点遵循以下规则：

• 每个节点只能是红色或黑色
• 根节点总是黑色的
• 红色节点的父或子节点都必然是黑色的(两个红色的节点不会相连)
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

说白了红黑树的平衡就是为了满足以上的规则。

在讲解插入和删除之前先声明几个概念：

红黑树中真正的叶子结点为nil结点，是黑色，其实所有的叶子结点都指向同一个nil结点，如下图。

左旋右旋：

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

红黑树的插入，删除都分了很多情景，具体的代码操作都是根据这些场景划分去实现的。

2.1 插入

首先需要明白新插入的结点应该是什么颜色？红色还是黑色。

答案：红色。为什么呢？红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

插入场景：

• 红黑树为空树，插入结点设为根结点，并改为黑色

• 插入结点已存在，相当于更新，原来结点的值改为插入结点的值

• 插入结点的的父结点为黑色，直接插入，不需要调整，因为不影响树的平衡

• 插入结点的父结点为红色，其实主要就是分析这种场景，因为父结点为红色，插入结点为红色所以不满足性质3，需要重新调整树，使其平衡。
  可以访问：【https://www.liuchengtu.com/lct/#R19a31f234576b12a21d1e5bcab5fc3ba】
  看下图：
  

2.2 删除

删除的相对插入的更复杂一些。

当我们删除一个结点的时候，我们需要从左子树找到一个最大值或者右子树中找到一个最小值，即前继结点或者后继结点 来进行替换。那么不就相当于删除替换结点。所以有以下结论：

删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！

那么问题来了，如果没有左子树或者右子树怎么办？那么它本身就相当于替换结点。删除即可。

所有以下场景：

• 当替换结点为红色的时候，直接删除，不会影响树的平衡

• 当替换结点为黑色的时候，会破坏红黑树的平衡，需要重新平衡。这里面又分了多种情况，看下图
  图片看不清，可以访问【https://www.liuchengtu.com/lct/#R0aa349b388897f1f799e5366cdac32f6】
  

3 HashMap

源博客【https://www.jianshu.com/p/c658df4f4c77】

我这里完全是copy这个博客的，因为讲的实在很好。

主要从以下几点讲解：

• HashMap 的存储结构
• 常用变量说明，如加载因子等
• HashMap 的四个构造函数
• tableSizeFor()方法及作用
• put()方法详解
• hash()方法，以及避免哈希碰撞的原理
• resize()扩容机制及原理
• get()方法
• 为什么HashMap链表会形成死循环，JDK1.8做了哪些优化
• 链表升级为红黑树分析

说明：本篇主要以JDK1.8的源码来分析，顺带讲下和JDK1.7的一些区别。

3.1 HashMap存储结构

这里需要区分一下，JDK1.7和 JDK1.8之后的 HashMap 存储结构。在JDK1.7及之前，是用数组加链表的方式存储的。

但是，众所周知，当链表的长度特别长的时候，查询效率将直线下降，查询的时间复杂度为 O(n)。因此，JDK1.8 把它设计为达到一个特定的阈值之后，就将链表转化为红黑树。

这里简单说下红黑树的特点：

1. 每个节点只有两种颜色：红色或者黑色
2. 根节点必须是黑色
3. 每个叶子节点（NIL）都是黑色的空节点
4. 从根节点到叶子节点，不能出现两个连续的红色节点
5. 从任一节点出发，到它下边的子节点的路径包含的黑色节点数目都相同

由于红黑树，是一个自平衡的二叉搜索树，因此可以使查询的时间复杂度降为O(logn)。（红黑树不是本文重点，不了解的童鞋可自行查阅相关资料哈）

HashMap 结构示意图：

3.1 常用的变量

在 HashMap源码中，比较重要的常用变量，主要有以下这些。还有两个内部类来表示普通链表的节点和红黑树节点。

//默认的初始化容量为16，必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
//当红黑树上的元素个数，减少到6个时，就退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。
//这是为了避免，数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;
//存放所有Node节点的数组
transient Node<K,V>[] table;
//存放所有的键值对
transient Set<Map.Entry<K,V>> entrySet;
//map中的实际键值对个数，即数组中元素个数
transient int size;
//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;
//数组扩容阈值
int threshold;
//加载因子
final float loadFactor;                 
//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
    //key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置
    final int hash;
    final K key;
    V value;
    //指向单链表的下一个节点
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
//转化为红黑树的节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    //当前节点的父节点
    TreeNode<K,V> parent;  
    //左孩子节点
    TreeNode<K,V> left;
    //右孩子节点
    TreeNode<K,V> right;
    //指向前一个节点
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    //当前节点是红色或者黑色的标识
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

3.2 HashMap 构造函数

HashMap有四个构造函数可供我们使用，一起来看下：

//默认无参构造，指定一个默认的加载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量，下面会说
public HashMap(int initialCapacity) {
    //同样使用默认加载因子
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//可指定容量和加载因子，但是笔者不建议自己手动指定非0.75的加载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16
    //注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂，为什么这里赋值给了 threshold 呢？
    //先卖个关子，等到 resize 的时候再说
    this.threshold = tableSizeFor(initialCapacity);
}
//可传入一个已有的map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
//把传入的map里边的元素都加载到当前map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            //put方法的具体实现，后边讲
            putVal(hash(key), key, value, false, evict);
        }
    }
}

3.3 tableSizeFor()

上边的第三个构造函数中，调用了 tableSizeFor 方法，这个方法是怎么实现的呢？

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

我们以传入参数为14 来举例，计算这个过程。

首先，14传进去之后先减1，n此时为13。然后是一系列的无符号右移运算。

//13的二进制
0000 0000 0000 0000 0000 0000 0000 1101 
//无右移1位，高位补0
0000 0000 0000 0000 0000 0000 0000 0110 
//然后把它和原来的13做或运算得到，此时的n值
0000 0000 0000 0000 0000 0000 0000 1111 
//再以上边的值，右移2位
0000 0000 0000 0000 0000 0000 0000 0011
//然后和第一次或运算之后的 n 值再做或运算，此时得到的n值
0000 0000 0000 0000 0000 0000 0000 1111
...
//我们会发现，再执行右移 4,8,16位，同样n的值不变
//当n小于0时，返回1，否则判断是否大于最大容量，是的话返回最大容量，否则返回 n+1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//很明显我们这里返回的是 n+1 的值，
0000 0000 0000 0000 0000 0000 0000 1111
+                                     1
0000 0000 0000 0000 0000 0000 0001 0000

将它转为十进制，就是 2^4 = 16 。我们会发现一个规律，以上的右移运算，最终会把最低位的值都转化为 1111 这样的结构，然后再加1，就是1 0000 这样的结构，它一定是 2的n次幂。因此，这个方法返回的就是大于当前传入值的最小（最接近当前值）的一个2的n次幂的值。

3.4 put()方法详解

//put方法，会先调用一个hash()方法，得到当前key的一个hash值，
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//把hash值和当前的key，value传入进来
//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断table是否为空，如果空的话，会先调用resize扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
    //若没有，则把key、value包装成Node节点，直接添加到此位置。
    // i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { 
        //如果当前位置已经有元素了，分为三种情况。
        Node<K,V> e; K k;
        //1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
        //则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //2.如果当前是红黑树结构，则把它加入到红黑树 
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //遍历链表
        //3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果头结点的下一个节点为空，则插入新节点
                    p.next = newNode(hash, key, value, null);
                    //如果在插入的过程中，链表长度超过了8，则转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //插入成功之后，跳出循环，跳转到①处
                    break;
                }
                //若在链表中找到了相同key的话，直接退出循环，跳转到①处
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //链表遍历
                p = e;
            }
        }
        //说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //用新值替换旧值，并返回旧值。
            //如果用户值替换或者oldValue为空，说明e的旧值本来就是空的，因为hashmap可存空值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，
            //只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能
            // Callbacks to allow LinkedHashMap post-actions
            //void afterNodeAccess(Node<K,V> p) { }
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //fail-fast机制
    ++modCount;
    //如果当前数组中的元素个数超过阈值，则扩容
    if (++size > threshold)
        resize();
    //同样的空实现
    afterNodeInsertion(evict);
    return null;
}

3.5 hash()计算原理

前面 put 方法中说到，需要先把当前key进行哈希处理，我们看下这个方法是怎么实现的。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里，会先判断key是否为空，若为空则返回0。这也说明了hashMap是支持key传 null 的。若非空，则先计算key的hashCode值，赋值给h，然后把h右移16位，并与原来的h进行异或处理。为什么要这样做，这样做有什么好处呢？

我们知道，hashCode()方法继承自父类Object，它返回的是一个 int 类型的数值，可以保证同一个应用单次执行的每次调用，返回结果都是相同的（这个说明可以在hashCode源码上找到），这就保证了hash的确定性。在此基础上，再进行某些固定的运算，肯定结果也是可以确定的。

我随便运行一段程序，把它的 hashCode的二进制打印出来，如下。

public static void main(String[] args) {
    Object o = new Object();
    int hash = o.hashCode();
    System.out.println(hash);
    System.out.println(Integer.toBinaryString(hash));
}
//1836019240
//1101101011011110110111000101000

然后，进行 (h = key.hashCode()) ^ (h >>> 16) 这一段运算。

//h原来的值
0110 1101 0110 1111 0110 1110 0010 1000
//无符号右移16位，其实相当于把低位16位舍去，只保留高16位
0000 0000 0000 0000 0110 1101 0110 1111
//然后高16位和原 h进行异或运算
0110 1101 0110 1111 0110 1110 0010 1000
^
0000 0000 0000 0000 0110 1101 0110 1111
=
0110 1101 0110 1111 0000 0011 0100 0111

可以看到，其实相当于，我们把高16位值和当前h的低16位进行了混合，这样可以尽量保留高16位的特征，从而降低哈希碰撞的概率。

思考一下，为什么这样做，就可以降低哈希碰撞的概率呢？先别着急，我们需要结合 i = (n - 1) & hash 这一段运算来理解。

(n-1) & hash 作用

//②
//这是 put 方法中用来根据hash()值寻找在数组中的下标的逻辑，
//n为数组长度， hash为调用 hash()方法混合处理之后的hash值。
i = (n - 1) & hash

我们知道，如果给定某个数值，去找它在某个数组中的下标位置时，直接用模运算就可以了（假设数组值从0开始递增）。如，我找 14 在数组长度为16的数组中的下标，即为 14 % 16，等于14 。 18的位置即为 18%16，等于2。

而②中，就是取模运算的位运算形式。以18%16为例

//18的二进制
0001 0010
//16 -1 即 15的二进制
0000 1111
//与运算之后的结果为
0000 0010
// 可以看到，上边的结果转化为十进制就是 2 。
//其实我们会发现一个规律，因为n是2的n次幂，因此它的二进制表现形式肯定是类似于
0001 0000
//这样的形式，只有一个位是1，其他位都是0。而它减 1 之后的形式就是类似于
0000 1111 
//这样的形式，高位都是0，低位都是1，因此它和任意值进行与运算，结果值肯定在这个区间内
0000 0000  ~  0000 1111
//也就是0到15之间，（以n为16为例）
//因此，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快。

为什么高低位异或运算可以减少哈希碰撞

我们想象一下，假如用 key 原来的hashCode值，直接和 (n-1) 进行与运算来求数组下标，而不进行高低位混合运算，会产生什么样的结果。

//例如我有另外一个h2，和原来的 h相比较，高16位有很大的不同，但是低16位相似度很高，甚至相同的话。
//原h值
0110 1101 0110 1111 0110 1110 0010 1000
//另外一个h2值
0100 0101 1110 1011 0110 0110 0010 1000
// n -1 ,即 15 的二进制
0000 0000 0000 0000 0000 0000 0000 1111
//可以发现 h2 和 h 的高位不相同，但是低位相似度非常高。
//他们分别和 n -1 进行与运算时，得到的结果却是相同的。（此处n假设为16）
//因为 n-1 的高16位都是0，不管 h 的高 16 位是什么，与运算之后，都不影响最终结果，高位一定全是 0
//因此，哈希碰撞的概率就大大增加了，并且 h 的高16 位特征全都丢失了。

爱思考的同学可能就会有疑问了，我进行高低16位混合运算，是可以的，这样可以保证尽量减少高区位的特征。那么，为什么选择用异或运算呢，我用与、或、非运算不行吗？

这是有一定的道理的。我们看一个表格，就能明白了。

可以看到两个值进行与运算，结果会趋向于0；或运算，结果会趋向于1；而只有异或运算，0和1的比例可以达到1:1的平衡状态。（非呢？别扯犊子了，两个值怎么做非运算。。。）

所以，异或运算之后，可以让结果的随机性更大，而随机性大了之后，哈希碰撞的概率当然就更小了。

以上，就是为什么要对一个hash值进行高低位混合，并且选择异或运算来混合的原因。

3.6 resize() 扩容机制

在上边 put 方法中，我们会发现，当数组为空的时候，会调用 resize 方法，当数组的 size 大于阈值的时候，也会调用 resize方法。 那么看下 resize 方法都做了哪些事情吧。

final Node<K,V>[] resize() {
    //旧数组
    Node<K,V>[] oldTab = table;
    //旧数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。
    int oldThr = threshold;
    //初始化新数组的容量和阈值，分三种情况讨论。
    int newCap, newThr = 0;
    //1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。
    //为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity。
    //我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。
    if (oldCap > 0) {
        //容量达到了最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新数组的容量和阈值都扩大原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //2.到这里，说明 oldCap <= 0，并且 oldThr(threshold) > 0，这就是 map 初始化的时候，第一次调用 resize的情况
    //而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。
    //因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。
    //所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)
    //但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，这个会在③处理。
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，
    //于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，
    //因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）。
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中
    //如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需要重新分配元素。
    if (oldTab != null) {
        //遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //1.如果当前元素的下一个元素为空，则说明此处只有一个元素
                //则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并
                //判断当前位置的链表是否需要移动到新的位置
                //同一个数组里面的链表的hash值都是一样的，所以只需要移动头部就可以
                else { // preserve order
                    // loHead 和 loTail 分别代表链表旧位置的头尾节点
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //如果当前元素的hash值和oldCap做与运算为0，则原位置不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //否则，需要移动到新的位置
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //原位置不变的一条链表，数组下标不变
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //移动到新位置的一条链表，数组下标为原下标加上旧数组的容量
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

上边还有一个非常重要的运算，我们没有讲解。就是下边这个判断，它用于把原来的普通链表拆分为两条链表，位置不变或者放在新的位置。

if ((e.hash & oldCap) == 0) {} else {}

我们以原数组容量16为例，扩容之后容量为32。说明下为什么这样计算。

还是用之前的hash值举例。

//e.hash值
0110 1101 0110 1111 0110 1110 0010 1000
//oldCap值，即16
0000 0000 0000 0000 0000 0000 0001 0000 
//做与运算，我们会发现结果不是0就是非0，
//而且它取决于 e.hash 二进制位的倒数第五位是 0 还是 1，
//若倒数第五位为0，则结果为0，若倒数第五位为1，则结果为非0。
//那这个和新数组有什么关系呢？
//别着急，我们看下新数组的容量是32，如果求当前hash值在新数组中的下标，则为
// e.hash &( 32 - 1) 这样的运算 ，即 hash 与 31 进行与运算，
0110 1101 0110 1111 0110 1110 0010 1000 
&
0000 0000 0000 0000 0000 0000 0001 1111 
=
0000 0000 0000 0000 0000 0000 0000 1000
//接下来，我们对比原来的下标计算结果和新的下标结果，看图

看下面的图，我们观察，hash值和旧数组进行与运算的结果 ，跟新数组的与运算结果有什么不同。

会发现一个规律：

若hash值的倒数第五位是0，则新下标与旧下标结果相同，都为 0000 1000

若hash值的倒数第五位是1，则新下标（0001 1000）与旧下标（0000 1000）结果值相差了 16 。

因此，我们就可以根据 （e.hash & oldCap == 0） 这个判断的真假来决定，当前元素应该在原来的位置不变，还是在新的位置(原位置 + 16)。

如果，上边的推理还是不明白的话，我再举个简单的例子。

18%16=2     18%32=18
34%16=2     34%32=2
50%16=2     50%32=18

怎么样，发现规律没，有没有那个感觉了？

计算中的18，34 ，50 其实就相当于 e.hash 值，和新旧数组做取模运算，得到的结果，要么就是原来的位置不变，要么就是原来的位置加上旧数组的长度。

3.7 get()方法

有了前面的基础，get方法就比较简单了。

public V get(Object key) {
    Node<K,V> e;
    //如果节点为空，则返回null，否则返回节点的value。这也说明，hashMap是支持value为null的。
    //因此，我们就明白了，为什么hashMap支持Key和value都为null
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //首先要确保数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //若hash值和key都相等，则说明我们要找的就是第一个元素，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果不是的话，就遍历当前链表（或红黑树）
        if ((e = first.next) != null) {
            //如果是红黑树结构，则找到当前key所在的节点位置
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果是普通链表，则向后遍历查找，直到找到或者遍历到链表末尾为止。
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //否则，说明没有找到，返回null
    return null;
}