4万字聊聊阿里二面，能抗多少？（上）

//无参构造ArrayList的话 会初始化空对象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 底层的数组对象
transient Object[] elementData;
// 默认初始化为10 
private static final int DEFAULT_CAPACITY = 10;
// 默认最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 无参构造方法
public ArrayList() {
    //无惨构造，默认参数赋给数组对象
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 有参构造方法
public ArrayList(int initialCapacity) {
    //有参构造时，会传一个大小，如果大于0 就把传入的参数作为length
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果等于0，就直接用自带的DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //如果这个大小小于0肯定是不允许的
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
// add方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
// add方法中的ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// add方法中ensureCapacityInternal的calculateCapacity
// 这个函数其实就是处理 当是无参构造时，他会在add函数里 做+1处理 并且与自带的大小比较，取最大的值。
// 这里就是为什么很多会说 ArrayList初始化默认长度为10的原因（添加数据后是10）
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// add方法中的ensureCapacityInternal的ensureExplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
    //modCount就是他的修改次数同时主要处理快速失败的一个作用，官方原话是这么说的
    //If an implementation does not wish to provide fail-fast iterators, this field may be ignored.
    //如果一个实现不希望提供快速失败迭代器，这个字段可以被忽略。  
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 这个函数主要处理的是一个 扩容 的一个作用。
// 扩容完之后， 开始处理数据的真实大小。通过Arrays.copyOf 函数 截取当前的 扩容后的大小 也就是15赋值给elementData 底层数组
private void grow(int minCapacity) {
        // 首先取整个链表 数据的长度，   比如 length = 10
        int oldCapacity = elementData.length;
      //10 + 5 = 15   这个 15 就是最新的链表长度 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // copy 数组，耗时主要是在这个地方
        elementData = Arrays.copyOf(elementData, newCapacity);
}
// 这个函数其实没啥用，主要就是两极的判断， 如果小于0 抛出异常，如果大于最大值 等等
private static int hugeCapacity(int minCapacity) {
    // 
      if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}
// 最后处理完之后， 回到add函数的 第二行代码，把新加的数据 写入当前数组对象中

//无参构造方法   1.7
public ArrayList() {
        this(10);
}
 public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
}
//无参构造方法   1.8
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

final float loadFactor; //记录 hashMap 装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 0.75
static final int MAXIMUM_CAPACITY = 1 << 30;  // 1073741824
static final int TREEIFY_THRESHOLD = 8;   //链表长度到8，就转为红黑树
static final int UNTREEIFY_THRESHOLD = 6; // 树大小为6，就转回链表
transient Node<K,V>[] table;  // 哈希桶数组
transient int modCount; //记录　hashMap 发生结构性变化的次数（注意　value 的覆盖不属于结构性变化）
int threshold; //threshold的值应等于 table.length * loadFactor, size 超过这个值时进行　resize()扩容
// 无参构造
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 根据大小参数以及负载因子构造
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;
        this.threshold = tableSizeFor(initialCapacity);
}
// 根据大小参数构造   日常使用中，我们还是首选无参构造以及 根据大小参数构造的。
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// put 放入函数
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// hash 函数
static final int hash(Object key) {
        int h;
    /*key 的 hash　值的计算是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销*/
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// put 函数的内嵌函数
// 参数onlyIfAbsent表示是否替换原值
// 参数evict我们可以忽略它，它主要用来区别通过put添加还是创建时初始化数据的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
      // 空表，需要初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            // resize()不仅用来调整大小，还用来进行初始化配置
            n = (tab = resize()).length;
      //这里就是看下在hash位置有没有元素，实际位置是hash % (length-1)
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 将元素直接插进去
            tab[i] = newNode(hash, key, value, null);
        else {
            //这时就需要链表或红黑树了
          // e是用来查看是不是待插入的元素已经有了，有就替换
            Node<K,V> e; K k;
            // p是存储在当前位置的元素
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;  //要插入的元素就是p，这说明目的是修改值
            // 若原来元素是红黑树节点，调用红黑树的插入方法:putTreeVal
            else if (p instanceof TreeNode)
                // 把节点添加到树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 这时候就是链表的头节点，要把待插入元素挂在链尾
                for (int binCount = 0; ; ++binCount) {
                    //向后循环
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 链表比较长，需要树化，
                      // 由于初始即为p.next，所以当插入第8个元素才会树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 找到了对应元素，就可以停止了
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 继续向后
                    p = e;
                }
            }
            // e就是被替换出来的元素，这时候就是修改元素值
            if (e != null) { // 待插入元素在　hashMap 中已存在
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 默认为空实现，允许我们修改完成后做一些操作
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
      // size太大，达到了capacity的0.75，需要扩容
        if (++size > threshold)
            resize();
      // 默认也是空实现，允许我们插入完成后做一些操作
        afterNodeInsertion(evict);
        return null;
}
// 动态扩容
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
      // 如果是第一次resize 肯定是0，无需扩容。 如果是装不下了  扩容的时候 就会选取 oldTab.length
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
      // 判断负载因子是否大于0
        int oldThr = threshold;
        int newCap, newThr = 0;
      // 如果大于0 这里主要是做一个安全措施，如果大于了最大值MAXIMUM_CAPACITY  就会使用更大的上限
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
           // 把上文的threshold 负载因子 扩大一倍  也就是 左移一位  赋值给newCap，与HashMap自带的上限做比较，并且与自带的默认容量比较  如果符合的话  就 计算当前的容量 （扩大一倍）
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
      //当前上文的负载因子大于0，把当前的值赋给 newCap （这个值主要是决定下文Node的大小）
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 否则就采用默认的大小 16
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
      //这里主要就是判断 0 的一些保护措施
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
      // 创建 Node的大小 ，把当前的Node节点给哈希桶数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
      // 判断oldTab  ，这里的oldTab其实就是 HashMap自带的 哈希桶数组在 resize第一行声明了
        if (oldTab != null) {
            // 开始对oldTab进行 循环， 终止值 就是 这个oldTab的大小 上文 判断了 取0 或者 .length了
            // 把　oldTab 中的节点　reHash 到　newTab 中去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // 每一次循环 把当前节点赋值给临时变量 e 判断是否为空
                if ((e = oldTab[j]) != null) {
                    // 当前节点归为null
                    oldTab[j] = null;
         // 如果当前只有一个节点，就取当前的hash值与 newCap-1 做二进制 位运算 直接在newTab中进行重定位
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果当前 e 是树节点 要进行 红黑树的 rehash　操作
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 若是链表，进行链表的 rehash　操作
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //根据算法　e.hash & oldCap　判断节点位置　rehash　后是否发生改变
                            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;
                            // rehash　后节点新的位置一定为原来基础上加上　oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}
  //这个函数的功能是对红黑树进行　rehash 操作
     final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
             TreeNode<K,V> b = this;
             // Relink into lo and hi lists, preserving order
             TreeNode<K,V> loHead = null, loTail = null;
             TreeNode<K,V> hiHead = null, hiTail = null;
             int lc = 0, hc = 0;
     　　　　　//由于　TreeNode 节点之间存在双端链表的关系，可以利用链表关系进行 rehash
             for (TreeNode<K,V> e = b, next; e != null; e = next) {
                    next = (TreeNode<K,V>)e.next;
                    e.next = null;
                    if ((e.hash & bit) == 0) {
                        if ((e.prev = loTail) == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                        ++lc;
                    }
                    else {
                        if ((e.prev = hiTail) == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                        ++hc;
                    }
                }
                //rehash 操作之后注意对根据链表长度进行　untreeify　或　treeify　操作
                if (loHead != null) {
                    if (lc <= UNTREEIFY_THRESHOLD)
                        tab[index] = loHead.untreeify(map);
                    else {
                        tab[index] = loHead;
                        if (hiHead != null) // (else is already treeified)
                            loHead.treeify(tab);
                    }
                }
                if (hiHead != null) {
                    if (hc <= UNTREEIFY_THRESHOLD)
                        tab[index + bit] = hiHead.untreeify(map);
                    else {
                        tab[index + bit] = hiHead;
                        if (loHead != null)
                            hiHead.treeify(tab);
                    }
                }//end if
            }//end split

protected int elementCount;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
protected int capacityIncrement; // 如果容量增量小于或等于零，则每次需要增长时，向量的容量都会增加一倍。  
// 构造一个 无参的 栈。他继承于Vector
public Stack() {
}
// 入栈
public E push(E item) {
        addElement(item);
        return item;
}
public synchronized void addElement(E obj) {
    // 入栈时  递增 modCount 记录修改次数
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
        // 如果
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}
// 这个函数应该在ArrayLisrt会比较熟悉的， 
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
      // 如果当前容量 大于0 说明不需要增长  直接取当前容量， 否则就取  整个容量的 2倍（这里的2倍主要是从 oldCapacity+oldCapacity 得到的 oldCapacity又代表elementData.length ）
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
    // 这里就是一些安全措施
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
    // newCapacity 就是 上文我们 三目运算符计算的 进行对象复制
        elementData = Arrays.copyOf(elementData, newCapacity);
}
// 出栈
public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
}
// 这里直接返回容量的大小
public synchronized int size() {
        return elementCount;
}
public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
}
// 由上列调用可以看出，取的就是末尾数据 弹出
public synchronized E elementAt(int index) {
    // 这里做了安全措施，如果当前弹出的下标 大于 容量  就抛出异常。 这句代码也验证了 顶部的 ` 因为栈的数量，下标不能搞错， 搞错就崩了。`
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
    // 弹出当前下标的元素  给上文的 obj
    return elementData(index);
}
public synchronized void removeElementAt(int index) {
      // 每次 删除的时候  自增一个 记录修改次数
        modCount++;
      // 如果当前的下标 大于 容量  抛出异常   （这个就是一个安全措施 没啥好说的）
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
      // 复制数组
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
      // 复制成功后  数量-1
        elementCount--;
      // 弹出的那个对象 为null 清空回收 结束
        elementData[elementCount] = null; /* to let gc do its work */
}

ArrayBlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(3);
//  这里大概的看了一下 感觉都很像，其实好好想想 这三种 都是继承AbstractQueue 而且又实现了Queue 能不像嘛
public ArrayBlockingQueue(int capacity) {
    this(capacity, false);
}
public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
}
LinkedBlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();
public LinkedBlockingQueue() {
        this(Integer.MAX_VALUE);
}
public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node<E>(null);
}
PriorityBlockingQueue priorityBlockingQue = new PriorityBlockingQueue();
public PriorityBlockingQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityBlockingQueue(int initialCapacity,
                                 Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        this.comparator = comparator;
        this.queue = new Object[initialCapacity];
}

// 底层存储元素的数组
final Object[] items;
// 出队序号，如果有一个元素出队，那么后面的元素不会向前移动，
// 而是将 takeIndex + 1 表示后面要出队的元素的角标
int takeIndex;
// 入队序号，表示后续插入的元素的角标，putIndex 不一定大于 takeIndex
int putIndex;
// 元素个数
int count;
// 内部锁
final ReentrantLock lock;
// notEmpty 条件
private final Condition notEmpty;
// notFull 条件
private final Condition notFull;
// 这是一个有参构造，因为底层是数组实现的，所以肯定是要初始化数组的，数组的长度肯定是你传入的参数。
// 因为他是线程安全的，所以肯定也是少不了锁的存在。
// 锁这个东西这里就不展开了在下文中也会多次提到GUC的。
public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        // 初始化底层数组
        this.items = new Object[capacity];
        // 默认为非公平锁 非公平锁就是 false  代表 不会按照等待越长就越先执行的规则。 
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
}
public void put(E e) throws InterruptedException {
        checkNotNull(e);
      // 获取锁
        final ReentrantLock lock = this.lock;
      /**
         * lock：调用后一直阻塞到获得锁
         * tryLock：尝试是否能获得锁 如果不能获得立即返回
         * lockInterruptibly：调用后一直阻塞到获得锁 但是接受中断信号(比如：Thread、sleep)
         */
        lock.lockInterruptibly();
        try {
            // 如果队列数组已满，则 notFull 阻塞，当有元素被移除后才唤醒 notFull
            while (count == items.length)
                notFull.await();
            // 元素入队
            enqueue(e);
        } finally {
            // 添加完元素后释放锁，这里一定要注意，千万不要因为忘记放锁，导致程序超时
            lock.unlock();
        }
}
// 首先肯定是要判断是否为空， 如果为空的话抛出异常，这个属于安全措施 没啥好说的
private static void checkNotNull(Object v) {
        if (v == null)
            throw new NullPointerException();
}
// 插入元素的函数，只在加锁状态下调用  而且是插入在尾部
private void enqueue(E x) {
        // assert lock.getHoldCount() == 1;
        // assert items[putIndex] == null;
        final Object[] items = this.items;
    // 要插入的元素e 放入 items数组的 putIndex的位置  （putIndex 就是当前最新要放入的位置下标）
        items[putIndex] = x;
    // 先自增 再匹配 整个数组的长度  这里的写法真漂亮。 没有无效代码
        if (++putIndex == items.length)
            // 下次放入的位置为0  因为是先进先出嘛，所以就导致了 每次放入的位置都是0
            putIndex = 0;
      //元素个数
        count++;
       // 唤醒 notFull
        notEmpty.signal();
}
private E dequeue() {
        // assert lock.getHoldCount() == 1;
        // assert items[takeIndex] != null;
        final Object[] items = this.items;
        @SuppressWarnings("unchecked")
        E x = (E) items[takeIndex];
        // 元素置 null
        items[takeIndex] = null;
        // 如果出队的是数组中的最后一个元素，则重置 takeIndex 为 0
        if (++takeIndex == items.length)
            takeIndex = 0;
      // 出队一个 肯定是要递减的呀
        count--;
        if (itrs != null)
            itrs.elementDequeued();
        // 唤醒 notFull
        notFull.signal();

TreeMap<Integer,String> tree = new TreeMap<Integer,String>();
//定义NavigableMap接口类型m
private transient NavigableMap<E,Object> m;
//申请类型为Object的PRESENT，作为key-value值中的value值，将我们需要保存的值放入key中
private static final Object PRESENT = new Object();
// The comparator used to maintain order in this tree map, or null if it uses the natural ordering of its keys.
private final Comparator<? super K> comparator;
//多态，m其实为一个TreeMap的实现类
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
//无参构造函数，申请一个TreeMap作为参数，由此可见TreeSet依赖于TreeMap进行实现
public TreeSet() {
    this(new TreeMap<E,Object>());
}
//指定比较器的构造函数
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 添加函数 源码
public V put(K key, V value) {
    // 声明一个 主节点 root
        Entry<K,V> t = root;
    // 如果是第一次插入的话 肯定是空，因为他没有父亲，他的主节点就是他自己
        if (t == null) {
            //使用此TreeMap的正确比较方法比较两个键。   下午已经把源码贴出来了
            compare(key, key); // type (and possibly null) check
            // 创建一个父节点
            root = new Entry<>(key, value, null);
            // 因为只有一个节点 size设为 1
            size = 1;
            modCount++;
            return null;
        }
      // 如果走到了这里说明 root 不为空，当前存在节点
        int cmp;
      // 声明一个临时 父亲节点
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                // 当前比较的两个节点 不为空时， 就把之前的root 覆给 临时父节点
                parent = t;
                // 比较当前的key值的顺序
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
}
// Compares two keys using the correct comparison method for this TreeMap.
// 使用此TreeMap的正确比较方法比较两个键。  
final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
}

这是ReentrantLock源码的变量 以及 AQS的变量
// 排它锁标识
static final Node EXCLUSIVE = null;
// 如果带有这个标识，证明是失效了
static final int CANCELLED =  1;
// 具有这个标识，说明后继节点需要被唤醒
static final int SIGNAL    = -1;
// Node对象存储标识的地方
volatile int waitStatus;
// 指向上一个节点
volatile Node prev;
// 指向下一个节点
volatile Node next;
// 当前Node绑定的线程
volatile Thread thread;
// 返回前驱节点，如果前期节点为null  就抛出空节点异常
final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
}

// 加锁入口
public void lock() {
    // sync 分为公平和非公平锁
    sync.lock();
}
// 非公平锁
final void lock() {
    // 通过CAS的方式 尝试把state从 0 修改 成1  如果返回true 代表成功，如果返回false  代表失败
    // CAS 是轻量级锁的实现方式
    if (compareAndSetState(0, 1))
        // 将一个属性设置为当前线程，这个属性是AQS的父类提供的  （AbstractOwnableSynchronizer）
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}
private transient Thread exclusiveOwnerThread;
protected final void setExclusiveOwnerThread(Thread thread) {
        exclusiveOwnerThread = thread;
}
// 核心函数
public final void acquire(int arg) {
    //tryAcquire 再次尝试获取锁资源，如果尝试成功 返回true
        if (!tryAcquire(arg) &&
            // 获取锁资源失败后，需要将当前线程封装成一个node 追加到AQS的队列中
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
}
// tryAcquire 函数进入后 
final boolean nonfairTryAcquire(int acquires) {
    // 获取当前线程
            final Thread current = Thread.currentThread();
    // 获取AQS的state的值
            int c = getState();
    // 如果 占有锁资源的人 已经释放了 我们就可以尝试获取锁资源
            if (c == 0) {
    // CAS尝试修改state 从0 修改成 1  如果成功 设置 exclusiveOwnerThread 属性为当前线程
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
    // 当前占有锁资源的线程是否是当前线程
            else if (current == getExclusiveOwnerThread()) {
                // 将state +1
                int nextc = c + acquires;
                // 如果加1 小于0 
                if (nextc < 0) // overflow
                    // 抛出超时锁可重入的最大值
                    throw new Error("Maximum lock count exceeded");
                // 如果没问题 继续修改 0 -1 
                setState(nextc);
                // 返回成功
                return true;
            }
            return false;
}
// 从 acquire 函数的 addWaiter
// 说明前面获取锁资源失败，放到锁队列中等待
private Node addWaiter(Node mode) {
    // 创建node类， 并且设置thread 为当前线程，设置为排他锁
        Node node = new Node(Thread.currentThread(), mode);
        // 获取AQS中队列的尾部节点
        Node pred = tail;
      //如果tail 不为null  说明现在队列有人排队
        if (pred != null) {
            // 把当前节点的prev 设置为刚才的尾部节点
            node.prev = pred;
            // 基于CAS的方式 将tail 节点设置为当前节点
            if (compareAndSetTail(pred, node)) {
                // 将之前的节点为next 设置为当前节点
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
}
// 如果当前没有人排队等待 就进入了enq函数  如果CAS失败，也会进入到这个位置重新往队列的尾部插入
private Node enq(final Node node) {
    // 死循环
        for (;;) {
            // 重新获取当前的tail节点为 t
            Node t = tail;
            if (t == null) { 
                // 如果当前tail节点为null  说明现在没人排队，我是第一个
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                // 如果现在有人排队，那我就把尾部插入，继续排队等待
                node.prev = t;
                // 基于CAS的方式 将tail节点设置为当前节点
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
}
// 已经将node 加入到双向队列中，然后执行当前方法
final boolean acquireQueued(final Node node, int arg) {
    // 标识
        boolean failed = true;
        try {
            // 标识
            boolean interrupted = false;
            for (;;) {
                // 获取当前节点的 上一个节点 
                final Node p = node.predecessor();
                // 如果 p是头，说明就是null  那我就执行 利用 tryAcquire函数 再次获取锁资源
                // 获取成功之后 state从 0改成1 返回true 
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                // 保证上一个节点是 -1  才会返回true，才会将线程阻塞，等待唤醒获取锁资源
                if (shouldParkAfterFailedAcquire(p, node) &&
                    // 基于Unsafe类的 park方法，挂起线程
                    parkAndCheckInterrupt())  // 针对fail属性，这里是唯一可能出现异常的地方，JVM                         内部出现问题时。
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
}
// 如果没有拿到锁资源 执行这个函数 node是当前节点，pred 是上一个节点
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    // 获取上一个节点的状态 state
        int ws = pred.waitStatus;
    // 如果上一个节点状态为 SIGNAL 一切正常
        if (ws == Node.SIGNAL)
            return true;
    // 如果上一个节点已经失效了  （这里失效了我解释一下）
        if (ws > 0) {
            do {
               // 将当前节点的prev指针指向了上一个的上一个
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);  // 一致找到小于等于0的
            // 将重新标识好的最近的有效节点的next
            pred.next = node;
        } else {
            // 小于等于0 ，不等于-1，将上一个有效节点状态修改为 -1
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
}
// 上文中 finally 代码块的 cancelAcquire 函数
// 如果当前为null 结束，健壮性判断
private void cancelAcquire(Node node) {
        if (node == null)
            return;
      // 当node的线程置为 null，竞争锁资源跟我没关系了。
        node.thread = null;
        // node的上一个节点
        Node pred = node.prev;
      // node上一个节点 大于0
        while (pred.waitStatus > 0)
            // 找到前面节点中 非失效的节点
            node.prev = pred = pred.prev;
      // 将第一个不是失效节点的下一个节点 声明出来
        Node predNext = pred.next;
    // 当前节点置为失效节点 给别的node看的
        node.waitStatus = Node.CANCELLED;
    // 如果当前节点是尾节点，将尾结点设置为最近的有效节点（如果当前是尾节点）
        if (node == tail && compareAndSetTail(node, pred)) {
            // 用CAS方式将尾节点的next 设置成null
            compareAndSetNext(pred, predNext, null);
        } else {
            int ws;
            // 中间节点操作
            // 如果上一个节点不是头节点
            if (pred != head &&
                // 获取上一节点状态，是不是有效
                ((ws = pred.waitStatus) == Node.SIGNAL || //
                 (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }
            node.next = node; // help GC
        }
}

public static User user = new User(); 

public class Leo {
    public static void main(String[] args) throws CloneNotSupportedException {
        // 通过new关键字创建对象
        VipInfo vipInfo = new VipInfo();
        // 通过clone方式创建对象
        VipInfo vipInfo1 = (VipInfo)vipInfo.clone();
        // 通过 .class.newInstance() 创建对象
        try {
            VipInfo info = VipInfo.class.newInstance();
        }catch (Exception e) {
        }
    }
}

/**
 * 在将来的某个时间执行给定的任务。 这个任务可以在新线程中执行，也可以在现有的线程池中执行。  
 * 如果任务不能提交执行，可能是因为这个原因“执行者”已经被关闭，或者因为它的容量已经达到，  
 * 当前任务就由RejectedExecutionHandler 进行处理
 */
public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();
    /*
     * 主要分三步走
     * 1. 如果运行的线程少于corePoolSize，则尝试用给定的命令作为第一个命令启动一个新的线程
     * 任务。 调用addWorker会自动检查runState和workerCount，这样可以防止误报 
     * 线程，当它不应该返回false。
     *
     * 2. 如果一个任务可以成功排队，那么我们仍然需要再次检查我们是否应该添加一个线程  
     * (因为现有的已经在上次检查后死亡)或其他进入此方法后池关闭。 所以我们重新检查状态，
     * 如果有必要，回滚排队停止，或启动一个新的线程(如果没有)。  
     *
     * 3. 如果不能对任务进行排队，则尝试添加一个新的线程。 如果它失败了，我们知道我们已经关闭或饱和了       * 因此拒绝任务。  
     */
    int c = ctl.get();
    if (workerCountOf(c) < corePoolSize) {
        if (addWorker(command, true))
            return;
        c = ctl.get();
    }
    if (isRunning(c) && workQueue.offer(command)) {
        int recheck = ctl.get();
        if (! isRunning(recheck) && remove(command))
            reject(command);
        else if (workerCountOf(recheck) == 0)
            addWorker(null, false);
    }
    else if (!addWorker(command, false))
        reject(command);
}

/**
 * A handler for rejected tasks that throws a
 * {@code RejectedExecutionException}.
 */
public static class AbortPolicy implements RejectedExecutionHandler {
    /**
     * Creates an {@code AbortPolicy}.
     */
    public AbortPolicy() { }
    /**
     * Always throws RejectedExecutionException.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     * @throws RejectedExecutionException always
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        throw new RejectedExecutionException("Task " + r.toString() +
                                             " rejected from " +
                                             e.toString());
    }
}

/**
 * A handler for rejected tasks that silently discards the
 * rejected task.
 */
public static class DiscardPolicy implements RejectedExecutionHandler {
    /**
     * Creates a {@code DiscardPolicy}.
     */
    public DiscardPolicy() { }
    /**
     * Does nothing, which has the effect of discarding task r.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
    }
}

/**
 * A handler for rejected tasks that discards the oldest unhandled
 * request and then retries {@code execute}, unless the executor
 * is shut down, in which case the task is discarded.
 */
public static class DiscardOldestPolicy implements RejectedExecutionHandler {
    /**
     * Creates a {@code DiscardOldestPolicy} for the given executor.
     */
    public DiscardOldestPolicy() { }
    /**
     * Obtains and ignores the next task that the executor
     * would otherwise execute, if one is immediately available,
     * and then retries execution of task r, unless the executor
     * is shut down, in which case task r is instead discarded.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        if (!e.isShutdown()) {
            e.getQueue().poll();
            e.execute(r);
        }
    }
}

/**
 * A handler for rejected tasks that runs the rejected task
 * directly in the calling thread of the {@code execute} method,
 * unless the executor has been shut down, in which case the task
 * is discarded.
 */
public static class CallerRunsPolicy implements RejectedExecutionHandler {
    /**
     * Creates a {@code CallerRunsPolicy}.
     */
    public CallerRunsPolicy() { }
    /**
     * Executes task r in the caller's thread, unless the executor
     * has been shut down, in which case the task is discarded.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        if (!e.isShutdown()) {
            r.run();
        }
    }
}