Java架构核心基础知识硬核整理，赶快收藏起来吧!!!

// 动态初始化：初始化时由程序员只指定数组长度，由系统为数组元素分配初始值
char c1[] = new char[5];
// 静态初始化： 初始化时由程序员显示置顶每个数组的初始值，由系统决定数组长度
char c2[] = new char[]{'E','D','U','Y','U'};
char c3[] = {'E','D','U','Y','U'};

public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(3);//尾插
    queue.offer(6);
    queue.offer(9);
    queue.offer(12);
    System.out.println(queue);
    System.out.println(queue.peek());//访问队列头元素
    System.out.println(queue);
    System.out.println(queue.poll());//删除队列头元素
    System.out.println(queue);
}

package com.bobo.util.treemap;

public class BRTree {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

    public void setRoot(RBNode root) {
        this.root = root;
    }


    /**
     * 表示 节点
     * @param <K>
     * @param <V>
     */
    static class RBNode<K extends Comparable<K>,V>{
        // 节点是双向的
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode() {
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

    /**
     * 围绕p左旋
     *     p               pr(r)
     *    / |             / \
     *   pl  pr(r) =>    p   rr
     *      / \         / \
     *     rl  rr     pl  rl
     *
     *  左旋的时候
     *  p-pl 和 pr-rr的关系不变
     *  pr-rl 要变为 p-rl
     *      也就是 rl要变为 p的右子节点
     *      同时 p要成为 rl 的父节点
     *  还有就是要判断  p 是否有父节点
     *  如果没有
     *     r 变为 root 节点
     *  如果有
     *     r.parent = p.parent
     *     还要设置 r为 p.parent 的子节点(可能左也可能右)
     *     如果 p.parent.left == p
     *        p.parent.left = r;
     *     否则
     *        p.parent.right = r;
     *    最后
     *       p.parent = r;
     *       r.left = p;
     * @param p
     */
    private void leftRotate(RBNode p){
        if(p != null){
            RBNode r = p.right;
            // 1.设置 pr-rl 要变为 p-rl
            // 把rl设置到p的右子节点
            p.right = r.left;
            if(r.left != null){
                // 设置rl的父节点为p
                r.left.parent = p;
            }
            // 2.判断p的父节点情况
            r.parent = p.parent; // 不管 p是否有父节点，都把这个父节点设置为 r的父节点
            if(p.parent == null){
                root = r; // p没有父节点 则r为root节点
            }else if(p.parent.left == p){
                p.parent.left = r; // 如果p为 p.parent的左子节点 则 r 也为 p.parent的左子节点
            }else{
                p.parent.right = r; // 反之设置 r 为 p.parent的右子节点
            }
            // 最后 设置 p 为 r 的左子节点
            r.left = p;
            p.parent = r;
        }
    }

    /**
     * 围绕p右旋
     * @param p
     */
    public void rightRotate(RBNode p){
        if(p != null){
            RBNode r = p.left;
            p.left = r.right;
            if(r.right != null){
                r.right.parent = p;
            }
            r.parent = p.parent;
            if(p.parent == null){
                root = r;
            }else if(p.parent.left == p){
                p.parent.left = r;
            }else{
                p.parent.right = r;
            }
            r.right = p;
            p.parent = r;
        }
    }

 /**
     * 新增节点
     * @param key
     * @param value
     */
    public void put(K key , V value){
        RBNode t = this.root;
        if(t == null){
            // 说明之前没有元素，现在插入的元素是第一个
            root = new RBNode<>(key , value == null ? key : value,null);
            return ;
        }
        int cmp ;
        // 寻找插入位置
        // 定义一个双亲指针
        RBNode parent;
        if(key == null){
            throw new NullPointerException();
        }
        // 沿着跟节点找插入位置
        do{
            parent = t;
            cmp = key.compareTo((K)t.key);
            if(cmp < 0){
                // 左侧找
                t = t.left;
            }else if(cmp > 0){
                // 右侧找
                t = t.right;
            }else{
                // 插入节点的值==比较的节点。值替换
                t.setValue(value==null?key:value);
                return;
            }
        }while (t != null);
        // 找到了插入的位置  parent指向 t 的父节点  t为null
        // 创建要插入的节点
        RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);
        // 然后判断要插入的位置 是 parent的 左侧还是右侧
        if(cmp < 0){
            parent.left = e;
        }else{
            parent.right = e;
        }
        // 调整  变色 旋转
        fixAfterPut(e);
    }

private boolean colorOf(RBNode node){
        return node == null ? BLACK:node.color;
    }

    private RBNode parentOf(RBNode node){
        return node != null ? node.parent:null;
    }

    private RBNode leftOf(RBNode node){
        return node != null ? node.left:null;
    }

    private RBNode rightOf(RBNode node){
        return node != null ? node.right:null;
    }

    private void setColor(RBNode node ,boolean color){
        if(node != null){
            node.setColor(color);
        }
    }

    /**
     * 插入节点后的调整处理
     * 1. 2-3-4树 新增元素 2节点添加一个元素将变为3节点 直接合并，节点中有两个元素
     *      红黑树：新增一个红色节点，这个红色节点会添加在黑色节点下(2节点) --- 这种情况不需要调整
     * 2. 2-3-4树 新增元素 3节点添加一个元素变为4节点合并 节点中有3个元素
     *      这里有6中情况，( 根左左 根左右  根右右 根右左)这四种要调整  (左中右的两种)不需要调整
     *      红黑树：新增红色节点 会添加到 上黑下红的节点中 = 排序后中间节点是黑色，两边节点是红色
     *
     *  3. 2-3-4树：新增一个元素 4节点添加一个元素需要裂变：中间元素升级为父节点，新增元素与剩下的其中一个合并
     *      红黑树：新增节点是红色+爷爷节点是黑色，父亲节点和叔叔节点为红色 调整为
     *              爷爷节点变红色，父亲和叔叔节点变为黑色，如果爷爷节点为root节点则调整为黑色
     * @param x
     */
    private void fixAfterPut(RBNode<K, Object> x) {
        x.color = RED;
        // 本质上就是父节点是黑色的就不需要调整，对应的 2 3的情况
        while(x != null && x != root && x.parent.color == RED){
            // 1. x 的父节点是爷爷的 左孩子
            if(parentOf(x) == parentOf(parentOf(x)).left){
                // 获取当前节点的叔叔节点
                RBNode y = rightOf(parentOf(parentOf(x)));
                // 情况3
                if(colorOf(y) == RED){
                    // 说明是 上3的情况  变色处理
                    // 父亲节点和叔叔节点设置为黑色
                    setColor(parentOf(x),BLACK);
                    setColor(y,BLACK);
                    // 爷爷节点设置为 红色
                    setColor(parentOf(parentOf(x)),RED);
                    // 递归处理
                    x = parentOf(parentOf(x));
                }else{
                    // 情况 2
                    if(x == parentOf(x).right){
                        // 如果x是父节点的右节点那么我们需要先根据 父节点 左旋
                        x = parentOf(x);
                        leftRotate(x);
                    }
                    // 叔叔节点为空  对应于 上面的情况2
                    // 将父节点变为黑色
                    setColor(parentOf(x),BLACK);
                    // 将爷爷节点变为红色
                    setColor(parentOf(parentOf(x)),RED);
                    // 右旋转  根据爷爷节点右旋转
                    rightRotate(parentOf(parentOf(x)));

                }
            }else{
                // x 的父节点是爷爷是右孩子
                // 获取父亲的叔叔节点
                RBNode y = leftOf(parentOf(parentOf(x)));
                if(colorOf(y) == RED){
                    // 情况3
                    setColor(parentOf(x),BLACK);
                    setColor(y,BLACK);
                    setColor(parentOf(parentOf(x)),RED);
                    x = parentOf(parentOf(x));
                }else{
                    // 情况2
                    if( x == parentOf(x).left){
                        x = parentOf(x);
                        rightRotate(x);
                    }
                    setColor(parentOf(x),BLACK);
                    setColor(parentOf(parentOf(x)),RED);
                    leftRotate(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

    private RBNode getNode(K key){
        RBNode node = this.root;
        while (node != null ){
            int cmp = key.compareTo((K) node.key);
            if(cmp < 0){
                // 在左子树
                node = node.left;
            }else if(cmp >0){
                // 右子树
                node = node.right;
            }else{
                return node;
            }
        }
        return null;
    }

/**
     * 删除节点
     * @param key
     * @return
     */
    public V remove(K key){
        // 先找到这个节点
        RBNode node = getNode(key);
        if(node == null){
            return null;
        }
        // 把值存起来 删除后 返回
        V oldValue = (V) node.value;
        deleteNode(node);
        return oldValue;
    }

    /**
     * 删除节点
     *   3种情况
     * 1.删除叶子节点，直接删除
     * 2.删除的节点有一个子节点，那么用子节点来替代
     * 3.如果删除的节点右两个子节点，此时需要找到前驱节点或者后继节点来替代
     *    可以转换为 1、2的情况
     * @param node
     */
    private void deleteNode(RBNode node){
        // 3.node节点有两个子节点
        if(node.left !=null && node.right != null){
            // 找到要删除节点的后继节点
            RBNode successor = successor(node);
            // 然后用后继节点的信息覆盖掉 要删除节点的信息
            node.key = successor.key;
            node.value = successor.value;
            // 然后我们要删除的节点就变为了 后继节点
            node = successor;
        }
        // 2.删除有一个子节点的情况
        RBNode replacement = node.left != null ? node.left : node.right;
        if(replacement != null){
            // 替代者的父指针指向原来 node 的父节点
            replacement.parent = node.parent;
            if(node.parent == null){
                // 说明 node 是root节点
                root = replacement;
            }else if(node == node.parent.left){
                // 双向绑定
                node.parent.left = replacement;
            }else{
                node.parent.right = replacement;
            }
            // 将node的左右孩子指针和父指针都指向null node等待GC
            node.left = node.right = node.parent = null;
            // 替换完成后需要调整平衡
            if(node.color == BLACK){
                // fixAfterRemove(replacement)
            }
        }else if(node.parent == null){
            // 说明要删除的是root节点
            root = null;
        }else{
            // 1. node节点是叶子节点 replacement为null
            // 先调整
            if(node.color == BLACK){
                // fixAfterRemove(node)
            }
            // 再删除
            if(node.parent != null){
                if(node == node.parent.left){
                    node.parent.left = null;
                }else{
                    node.parent.right = null;
                }
                node = null;
            }
        }
    }

    /**
     * 2-3-4树删除操作：
     * 1.情况一：自己能搞定的，对应叶子节点是3节点和4节点
     * 2.情况二：自己搞不定，需要兄弟借，但是兄弟不借，找父亲借，父亲下来，然后兄弟找一个人去代替父亲当家
     * 3.情况三：跟兄弟借，兄弟也没有
     * @param x
     */
    private void fixAfterRemove(RBNode x){
        // 情况2、3
        while(x != root && colorOf(x) == BLACK){
            // 这种情况才需要调整
            // x 是左孩子的情况
            if(x == leftOf(parentOf(x))){
                // 找兄弟节点
                RBNode rNode = rightOf(parentOf(x));
                // 判断此时的兄弟节点是否是真正的兄弟节点 兄弟是红色的情况要调整
                if(colorOf(rNode) == RED){ // 2-3-4树的 3节点 交换颜色，然后左旋一次就可以了
                    setColor(rNode,BLACK);
                    setColor(parentOf(x),RED);
                    leftRotate(parentOf(x)); // 左旋一次
                    rNode = rightOf(parentOf(x)); // 找到真正的兄弟节点
                }
                // 情况3 找兄弟借 没得借
                if(colorOf(leftOf(rNode)) == BLACK && colorOf(rightOf(rNode)) == BLACK){
                    // 情况复杂
                    setColor(rNode,RED);
                    x=parentOf(x); // 向上递归
                }else{
                    // 情况2 找兄弟借 有借
                    // 兄弟节点是 3节点或者4节点
                    if(colorOf(rightOf(rNode)) == BLACK){
                        // 右孩子为空，则左孩子肯定不为空
                        // 兄弟节点 先要左一次右旋
                        setColor(rNode,RED);
                        setColor(leftOf(rNode),BLACK);
                        rightRotate(rNode);
                        // 重新调整叔叔节点的位置
                        rNode = rightOf(parentOf(x));
                    }
                    // 变色  兄弟节点是 3节点还是4节点 都旋转一次
                    setColor(rNode, colorOf(parentOf(x)));
                    setColor(parentOf(x),BLACK);
                    setColor(rightOf(rNode),BLACK);
                    // 左旋
                    leftRotate(parentOf(x));
                    x = root; // 结束循环  递归 针对的是 情况3
                }
            }else{
                // 找兄弟节点
                RBNode rNode = leftOf(parentOf(x));
                // 判断此时的兄弟节点是否是真正的兄弟节点 兄弟是红色的情况要调整
                if(colorOf(rNode) == RED){ // 2-3-4树的 3节点 交换颜色，然后左旋一次就可以了
                    setColor(rNode,BLACK);
                    setColor(parentOf(x),RED);
                    rightRotate(parentOf(x)); // 左旋一次
                    rNode = leftOf(parentOf(x)); // 找到真正的兄弟节点
                }
                // 情况3 找兄弟借 没得借
                if(colorOf(rightOf(rNode)) == BLACK && colorOf(leftOf(rNode)) == BLACK){
                    // 情况复杂
                    setColor(rNode,RED);
                    x=parentOf(x); // 向上递归
                }else{
                    // 情况2 找兄弟借 有借
                    // 兄弟节点是 3节点或者4节点
                    if(colorOf(leftOf(rNode)) == BLACK){
                        // 右孩子为空，则左孩子肯定不为空
                        // 兄弟节点 先要左一次右旋
                        setColor(rNode,RED);
                        setColor(leftOf(rNode),BLACK);
                        leftRotate(rNode);
                        // 重新调整叔叔节点的位置
                        rNode = leftOf(parentOf(x));
                    }
                    // 变色  兄弟节点是 3节点还是4节点 都旋转一次
                    setColor(rNode, colorOf(parentOf(x)));
                    setColor(parentOf(x),BLACK);
                    setColor(leftOf(rNode),BLACK);
                    // 左旋
                    rightRotate(parentOf(x));
                    x = root; // 结束循环  递归 针对的是 情况3
                }
            }
        }
        // 情况1：替代节点是红色，直接染黑  在情况3的情况下  补偿删除的黑色节点，这样红黑树依然保存平衡
        setColor(x,BLACK);
    }

public HashMap() {
    // 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
   this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

 // 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/*
	 指定“容量大小”和“负载因子”的构造函数
	 initialCapacity：指定的容量
	 loadFactor:指定的负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
    	// 判断初始化容量initialCapacity是否小于0
        if (initialCapacity < 0)
            // 如果小于0，则抛出非法的参数异常IllegalArgumentException
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            // 如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
            initialCapacity = MAXIMUM_CAPACITY;
    	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            // 如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
     	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
// 最后调用了tableSizeFor，来看一下方法实现：
     /*
     	返回比指定初始化容量大的最小的2的n次幂
     */
    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;
    }

// 构造一个映射关系与指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
    	// 负载因子loadFactor变为默认的负载因子0.75
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);
 }

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //获取参数集合的长度
    int s = m.size();
    if (s > 0) {
        //判断参数集合的长度是否大于0，说明大于0
        if (table == null) { // 判断table是否已经初始化
                // 未初始化，s为m的实际元素个数
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                // 计算得到的t大于阈值，则初始化阈值
                if (t > threshold)
                    threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
/**
 * hash：key 的 hash 值
 * key：原始 key
 * value：要存放的值
 * onlyIfAbsent：如果 true 代表不更改现有的值
 * evict：如果为false表示 table 为创建状态
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /*
    	1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。
    	2）(tab = table) == null 表示将空的table赋值给tab，然后判断tab是否等于null，第一次肯定是null。
    	3）(n = tab.length) == 0 表示将数组的长度0赋值给n，然后判断n是否等于0，n等于0，由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化，并将初始化好的数组长度赋值给n。
    	4）执行完n = (tab = resize()).length，数组tab每个空间都是null。
    */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /*
    	1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中。
    	2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给结点p。
    	3) (p = tab[i = (n - 1) & hash]) == null 判断结点位置是否等于null，如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的结点放入该位置的桶中。
        小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置。
    */ 
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 创建一个新的结点存入到桶中
        tab[i] = newNode(hash, key, value, null);
    else {
         // 执行else说明tab[i]不等于null，表示这个位置已经有值了
        Node<K,V> e; K k;
        /*
        	比较桶中第一个元素(数组中的结点)的hash值和key是否相等
        	1）p.hash == hash ：p.hash表示原来存在数据的hash值  hash表示后添加数据的hash值 比较两个hash值是否相等。
                 说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。
                    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
                        return new Node<>(hash, key, value, next);
                    }
                    而在Node类中具有成员变量hash用来记录着之前数据的hash值的。
             2）(k = p.key) == key ：p.key获取原来数据的key赋值给k  key 表示后添加数据的key比较两个key的地址值是否相等。
             3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等。
        */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                /*
                	说明：两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录
                */ 
                e = p;
        // hash值不相等或者key不相等；判断p是否为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 说明是链表结点
        else {
            /*
            	1)如果是链表的话需要遍历到最后结点然后插入
            	2)采用循环遍历的方式，判断链表中是否有重复的key
            */
            for (int binCount = 0; ; ++binCount) {
                /*
                	1)e = p.next 获取p的下一个元素赋值给e。
                	2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键，将该键值对插入链表中。
                */
                if ((e = p.next) == null) {
                    /*
                    	1）创建一个新的结点插入到尾部
                    	 p.next = newNode(hash, key, value, null);
                    	 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
                                return new Node<>(hash, key, value, next);
                         }
                         注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个结点肯定是null。
                         2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素。
                    */
                    p.next = newNode(hash, key, value, null);
                    /*
                    	1)结点添加完成之后判断此时结点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树。
                    	2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历结点的个数。值是0表示第一个结点，1表示第二个结点。。。。7表示第八个结点，加上数组中的的一个元素，元素个数是9。
                    	TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7
                    	如果binCount的值是7(加上数组中的的一个元素，元素个数是9)
                    	TREEIFY_THRESHOLD - 1也是7，此时转换红黑树。
                    */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 转换为红黑树
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
   
                /*
                	执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等。
                */
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    /*
                		要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了
                		直接执行下面的if语句去替换去 if (e != null) 
                	*/
                    break;
                /*
                	说明新添加的元素和当前结点不相等，继续查找下一个结点。
                	用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                */
                p = e;
            }
        }
        /*
        	表示在桶中找到key值、hash值与插入元素相等的结点
        	也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值
        	这里完成了put方法的修改功能
        */
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                // 用新值替换旧值
                // e.value 表示旧值  value表示新值 
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改记录次数
    ++modCount;
    // 判断实际大小是否大于threshold阈值，如果超过则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

static final int hash(Object key) {
	int h;
	/*
	1）如果key等于null：返回的是0.
	2）如果key不等于null：首先计算出key的hashCode赋值给h，然后与h无符号右移16位后的
		二进制进行按位异或得到最后的hash值
	*/
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
   //转换为红黑树 tab表示数组名  hash表示哈希值
   treeifyBin(tab, hash);

/*
	替换指定哈希表的索引处桶中的所有链接结点，除非表太小，否则将修改大小。
	Node<K,V>[] tab = tab 数组名
	int hash = hash表示哈希值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    /*
    	如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64)，就去扩容。而不是将结点变为红黑树。
    	目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值，链表长度有可能就变短了，数据会放到数组中，这样相对来说效率高一些。
    */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //扩容方法
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        /*
        	1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化
        	2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e，e是哈希表中指定位置桶里的链表结点，从第一个开始
        */
        // hd：红黑树的头结点   tl：红黑树的尾结点
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 新创建一个树的结点，内容和当前链表结点e一致
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p; // 将新创键的p结点赋值给红黑树的头结点
            else {
                p.prev = tl; // 将上一个结点p赋值给现在的p的前一个结点
                tl.next = p; // 将现在结点p作为树的尾结点的下一个结点
            }
            tl = p;
            /*
            	e = e.next 将当前结点的下一个结点赋值给e，如果下一个结点不等于null
            	则回到上面继续取出链表中结点转换为红黑树
            */
        } while ((e = e.next) != null);
        /*
        	让桶中的第一个元素即数组中的元素指向新建的红黑树的结点，以后这个桶里的元素就是红黑树
        	而不是链表数据结构了
        */
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

final Node<K,V>[] resize() {
    // 得到当前数组
    Node<K,V>[] oldTab = table;
    // 如果当前数组等于null长度返回0，否则返回当前数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //当前阀值点 默认是12(16*0.75)
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果老的数组长度大于0
    // 开始计算扩容后的大小
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 修改阈值为int的最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        /*
        	没超过最大值，就扩充为原来的2倍
        	1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量
        	2）oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16
        */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    // 老阈值点大于0 直接赋值
    else if (oldThr > 0) // 老阈值赋值给新的数组长度
        newCap = oldThr;
    else { // 直接使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize最大上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 新的阀值 默认原来是12 乘以2之后变为24
    threshold = newThr;
    // 创建新的哈希表
    @SuppressWarnings({"rawtypes","unchecked"})
    //newCap是新的数组长度--》32
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 判断旧数组是否等于空
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        // 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 原来的数据赋值为null 便于GC回收
                oldTab[j] = null;
                // 判断数组是否有下一个引用
                if (e.next == null)
                    // 没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入
                    newTab[e.hash & (newCap - 1)] = e;
                //判断是否是红黑树
                else if (e instanceof TreeNode)
                    // 说明是红黑树来处理冲突的，则调用相关方法把树分开
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 采用链表处理冲突
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 通过上述讲解的原理来计算结点的新位置
                    do {
                        // 原索引
                        next = e.next;
                     	// 这里来判断如果等于true e这个结点在resize之后不需要移动位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

// remove方法的具体实现在removeNode方法中，所以我们重点看下removeNode方法
public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
	// 根据hash找到位置 
	// 如果当前key映射到的桶不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果桶上的结点就是要找的key，则将node指向该结点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 说明结点存在下一个结点
            if (p instanceof TreeNode)
                // 说明是以红黑树来处理的冲突，则获取红黑树要删除的结点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 判断是否以链表方式处理hash冲突，是的话则通过遍历链表来寻找要删除的结点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 比较找到的key的value和要删除的是否匹配
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 通过调用红黑树的方法来删除结点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 链表删除
                tab[index] = node.next;
            else
                p.next = node.next;
            // 记录修改次数
            ++modCount;
            // 变动的数量
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

public V get(Object key) {
    Node<K,V> e;
    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;
    // 如果哈希表不为空并且key对应的桶上不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        /* 
        	判断数组元素是否相等
        	根据索引的位置检查第一个元素
        	注意：总是检查第一个元素
        */
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果不是第一个元素，判断是否有后续结点
        if ((e = first.next) != null) {
            // 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取结点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

import java.util.concurrent.CountDownLatch;
 
public class ThreadDemo1 extends Thread {
    CountDownLatch countDownLatch;
 
    public ThreadDemo1(CountDownLatch countDownLatch) {
        this.countDownLatch = countDownLatch;
    }
 
    @Override
    public void run() {
        try {
            Thread.sleep(2000);
            System.out.println(Thread.currentThread().getName() + ":my thread ");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            countDownLatch.countDown();
        }
    }
 
    public static void main(String[] args) {
        // 第一种：使用extends Thread方式
        CountDownLatch countDownLatch1 = new CountDownLatch(2);
        for (int i = 0; i < 2; i++) {
            ThreadDemo1 myThread1 = new ThreadDemo1(countDownLatch1);
            myThread1.start();
        }
 
        try {
            countDownLatch1.await();
            System.out.println("thread complete...");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

 
}

 
import java.util.concurrent.CountDownLatch;
 
 
public class ThreadDemo2  implements Runnable{
    CountDownLatch countDownLatch;
 
    public ThreadDemo2(CountDownLatch countDownLatch) {
        this.countDownLatch = countDownLatch;
    }
    @Override
    public void run() {
        try {
            Thread.sleep(2000);
            System.out.println(Thread.currentThread().getName() + ":my runnable ");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            countDownLatch.countDown();
        }
    }
 
    public static void main(String[] args) {
        // 第二种：使用implements Runnable方式
        CountDownLatch countDownLatch2 = new CountDownLatch(2);
        ThreadDemo2 myRunnable = new ThreadDemo2(countDownLatch2);
        for (int i = 0; i < 2; i++) {
            new Thread(myRunnable).start();
        }
 
        try {
            countDownLatch2.await();
            System.out.println("runnable complete...");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

 
public class ThreadDemo3 implements Callable<Integer> {
 
    public static void main(String[] args) {
        ThreadDemo3 threadDemo03 = new ThreadDemo3();
        //1、用futureTask接收结果
        FutureTask<Integer> futureTask = new FutureTask<>(threadDemo03);
        new Thread(futureTask).start();
 
        //2、接收线程运算后的结果
        try {
            //futureTask.get();这个是堵塞性的等待
            Integer sum = futureTask.get();
            System.out.println("sum="+sum);
            System.out.println("-------------------");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
 
    @Override
    public Integer call() throws Exception {
        int sum = 0;
        for (int i = 0; i <101 ; i++) {
            sum+=i;
        }
        return sum;
    }
}

class FlagThread extends Thread {
 // 自定义中断标识符
 public volatile boolean isInterrupt = false;
 @Override
 public void run() {
     // 如果为 true -> 中断执行
     while (!isInterrupt) {
         System.out.println("业务处理1....");
         // 业务逻辑处理
         Thread.sleep(10000);
         System.out.println("业务处理2....");
     }
 }
}

public static void main(String[] args) throws InterruptedException {
// 创建可中断的线程实例
Thread thread = new Thread(() -> {
  while (!Thread.currentThread().isInterrupted()) {
      System.out.println("thread 执行步骤1：线程即将进入休眠状态");
      try {
          // 休眠 1s
          Thread.sleep(1000);
      } catch (InterruptedException e) {
          System.out.println("thread 线程接收到中断指令，执行中断操作");
          // 中断当前线程的任务执行
          break;
      }
      System.out.println("thread 执行步骤2：线程执行了任务");
  }
});
thread.start(); // 启动线程

// 休眠 100ms，等待 thread 线程运行起来
Thread.sleep(100);
System.out.println("主线程：试图终止线程 thread");
// 修改中断标识符，中断线程
thread.interrupt(); // 首先会改变当前线程的阻塞状态 true 。同时如何线程调用 sleep wait 这些阻塞的方法。那么会抛出 InterruptedException 异常
}

public ThreadPoolExecutor(int corePoolSize,
                               int maximumPoolSize,
                               long keepAliveTime,
                               TimeUnit unit,
                               BlockingQueue<Runnable> workQueue,
                               RejectedExecutionHandler handler) 

package com.boge.flow.aqs;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class AQSDemo {

    // 共享的资源
    private static  int count = 0;

    private static Lock lock = new ReentrantLock();

    /**
     * 造成数据安全问题的原因
     *   1.原子性:执行的最小单元  要么都执行。要么都不执行
     *   2.可见性:
     *   3.有序性：
     */
    // 定义一个方法去操作资源
    public static  void incr(){
        try {
            Thread.sleep(10);
            lock.lock(); // 加锁
            // ...
            lock.lock();
            count ++; // 原子  可见性
        }catch (Exception e){

        }finally {
            lock.unlock();
            lock.unlock(); // 释放锁
        }
    }

    public static void main(String[] args) throws InterruptedException {
        CountDownLatch latch = new CountDownLatch(100);
        // 多个线程去操作共享资源
        for (int i = 0; i < 100; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    incr();
                    latch.countDown();
                }
            }).start();
        }
        latch.await(); // 阻塞
        // 获取 共享的数据
        System.out.println("count = " + count);
    }
}