public interface Condition {
//进入等待状态，直到其他线程调用signal()或者signalAll()方法进行唤醒。或者其他线程中断当前线程。如果当前线程返回，则已经重新获得锁。
void await() throws InterruptedException;

//不可中断
void awaitUninterruptibly();

//超时后返回，单位为毫秒
long awaitNanos(long nanosTimeout) throws InterruptedException;

//超时后返回，单位为 TimeUnit中的枚举
boolean await(long time, TimeUnit unit) throws InterruptedException;

//超时到将来的具体时间
boolean awaitUntil(Date deadline) throws InterruptedException;

//唤醒一个线程
void signal();

//唤醒所有线程
void signalAll();
}

private volatile int state;

protected final int getState() {
    return state;
}

protected final void setState(int newState) {
    state = newState;
}

protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

//独占式获取同步状态，在具体实现中，需要原子判断当前state是否符合预期（为旧值，其他线程未修改），如果符合，将状态设置为新值。
protected boolean tryAcquire(long arg) {
    throw new UnsupportedOperationException();
}

//释放同步状态
protected boolean tryRelease(long arg) {
    throw new UnsupportedOperationException();
}

//共享式获取
protected long tryAcquireShared(long arg) {
    throw new UnsupportedOperationException();
}

//共享式释放
protected boolean tryReleaseShared(long arg) {
    throw new UnsupportedOperationException();
}

//判断当前状态是否被独占
protected boolean isHeldExclusively() {
    throw new UnsupportedOperationException();
}

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

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

NOde的部分字段
static final class Node {
    volatile int waitStatus;

    volatile Node prev;

    volatile Node next;

    volatile Thread thread;

    Node nextWaiter;


}

private final boolean compareAndSetHead(Node update) {
    return unsafe.compareAndSwapObject(this, headOffset, null, update);
}

/**
 * CAS tail field. Used only by enq.
 */
private final boolean compareAndSetTail(Node expect, Node update) {
    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<>(m);
}

hash >>> segmentShift) & segmentMask  // 定位Segment所使用的hash算法 
int index = hash & (tab.length - 1);  // 定位HashEntry所使用的hash算法

int size();
public boolean isEmpty()
public boolean contains(Object o)
public int indexOf(Object o)
public Object[] toArray() //返回一个包含当前所有元素的数组
public int lastIndexOf(Object o)

public E set(int index, E element)
public E get(int index)
public void add(int index, E element) //在指定下标插入元素
public boolean add(E e) 
public boolean remove(Object o) //删除指定下标的元素
public E remove(int index)
public void clear()
public boolean addAll(Collection<? extends E> c) //在当前列表后依次添加c中的元素

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
public boolean removeLastOccurrence(Object o)
public boolean removeFirstOccurrence(Object o)

public E pop()
public void push(E e)
public E pollFirst() //删除链表首部元素
public E pollLast() 
public E peekFirst() //取得链表头节点
public E peekLast()  //取得链表尾节点
public boolean offerFirst(E e) 
public boolean offerLast(E e)

public E push(E item)
public synchronized E pop()
public boolean empty()
public synchronized int search(Object o)
public synchronized E peek() 

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Set s = Collections.synchronizedSet(new HashSet(...));

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

public static void main(String[] args) {
    Map<String, Integer> scores = new LinkedHashMap<>();
    scores.put("chemistry", 93);
    scores.put("math", 98);
    scores.put("biology", 92);
    scores.put("english", 97);
    scores.put("physics", 94);
    scores.put("chinese", 99);
    scores.put("geography", 95);
    Iterator<Map.Entry<String, Integer>> iterator = scores.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, Integer> score = iterator.next();
        System.out.println("subject: " + score.getKey() + " score: " + score.getValue());
    }
}

static class Node<K,V> implements Map.Entry<K,V> {
    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;
    }
    //hashCode通过key于value计算得到
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
}

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)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) //判断数组位置是否已经插入元素，如果没有就插入数组中
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))) //通过hash和key确定，是否key相同，是的话覆盖value即可
            e = p;
        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) { //到达尾部，没有找到key相同的节点，插入尾部
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
        //找到key相同的节点，直接返回，执行1
                
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break;
                p = e;
            }
        }
        //1，在key相同的节点，修改value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //size大于阈值，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    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)))) //首先通过hash值在哈希表数组中寻找，如果hash和key都符合，则表示找到，可以返回
            return first;
        if ((e = first.next) != null) { //出现hash冲突，
            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);
        }
    }
    return null;
}

else { // preserve order
    Node<K,V> loHead = null, loTail = null;
    Node<K,V> hiHead = null, hiTail = null;
    Node<K,V> next;
    do {
        next = e.next;
        if ((e.hash & oldCap) == 0) { //决定存在数组高位还是低位
            if (loTail == null)
                loHead = e;
            else
                loTail.next = e; //会形成一个链表，link_1;
            loTail = e;
        }
        else {
            if (hiTail == null)
                hiHead = e;  //也会形成一个链表，link_2;
            else
                hiTail.next = e;
            hiTail = e;
        }
    } while ((e = next) != null);
    if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead; //存link_1在新数组低位
    }
    if (hiTail != null) {
        hiTail.next = null;
        newTab[j + oldCap] = hiHead; //存link_2在数组高位
    }
}

//核心线程数和最大工作线程数量相等，避免创建大量线程，适用于服务器负载较重的情况。
//使用无界队列LinkedBlockingQueue作为任务管理队列，意味着线程池中工作线程不会超过核心线程。
public static ExecutorService newFixedThreadPool(int nThreads) {
    return new ThreadPoolExecutor(nThreads, nThreads,
                                  0L, TimeUnit.MILLISECONDS,
                                  new LinkedBlockingQueue<Runnable>());
}

//没有核心线程，最大工作线程取整数的最大值，适用于有比较多短期的小任务场景；
//使用SynchronousQueue作为工作队列，当主线程提交任务速度大于线程处理速度时，会不断创建线程，有可能会因为创建过多线程导致CPU和内存耗尽
public static ExecutorService newCachedThreadPool() {
    return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                  60L, TimeUnit.SECONDS,
                                  new SynchronousQueue<Runnable>());
}

//只会创建一个工作线程，适用于需要保证顺序的执行各个任务的场景。
public static ExecutorService newSingleThreadExecutor() {
    return new FinalizableDelegatedExecutorService
        (new ThreadPoolExecutor(1, 1,
                                0L, TimeUnit.MILLISECONDS,
                                new LinkedBlockingQueue<Runnable>()));
}

//只会创建单个核心线程，工作线程为Integer.MAX_VALUE
public static ScheduledExecutorService newSingleThreadScheduledExecutor(ThreadFactory threadFactory) {
    return new DelegatedScheduledExecutorService
        (new ScheduledThreadPoolExecutor(1, threadFactory));
}

//可以设置多个核心线程,工作线程为Integer.MAX_VALUE
public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize) {
    return new ScheduledThreadPoolExecutor(corePoolSize);
}

public static <T> Callable<T> callable(Runnable task, T result) {
    if (task == null)
        throw new NullPointerException();
    return new RunnableAdapter<T>(task, result);
}

//使用DelayWorkerQueue作为工作队列，这是一个无界阻塞队列，使用PriorityQueue实现。
public ScheduledThreadPoolExecutor(int corePoolSize,
                                   ThreadFactory threadFactory,
                                   RejectedExecutionHandler handler) {
    super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
          new DelayedWorkQueue(), threadFactory, handler);
}

ScheduledFutureTask(Callable<V> callable, long ns) {
    super(callable);
    this.time = ns; //表示这个任务将要被执行的具体时间
    this.period = 0; //表示任务执行的间隔周期，
    this.sequenceNumber = sequencer.getAndIncrement(); //被添加入任务队列的顺序
}

private void setNextRunTime() {
    long p = period;
    if (p > 0)
        time += p;
    else
        time = triggerTime(-p);
}

public ThreadPoolExecutor(int corePoolSize,//核心线程数
                          int maximumPoolSize, //最大工作线程数，不能小于corePoolSize
                          long keepAliveTime, //非核心线程超时时间，闲置时间超过会被销毁
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue, //用于保存等待执行的任务的阻塞队列
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler //拒绝策略)

public class CountDownLatchTest {
    private static CountDownLatch countDownLatch = new CountDownLatch(2)；
    public static void main(String[]args) throws InterruptedException {
        Thread threadOne = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("continue");
                countDownLatch.countDown();
                System.out.println("continue");
                countDownLatch.countDown();
            }
        });
        threadOne.start();
        countDownLatch.await();
        System.out.println("over");
    }
}

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

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

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


protected boolean tryReleaseShared(int releases) {
    // Decrement count; signal when transition to zero
    for (;;) {
        int c = getState();
        if (c == 0)
            return false;
        int nextc = c-1;
        if (compareAndSetState(c, nextc))
            return nextc == 0;
    }
}

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

public final void acquireSharedInterruptibly(int arg)
        throws InterruptedException {
    if (Thread.interrupted())
        throw new InterruptedException();
    if (tryAcquireShared(arg) < 0)
        doAcquireSharedInterruptibly(arg);
}
protected int tryAcquireShared(int acquires) {
    return (getState() == 0) ? 1 : -1;
}

public class SemaphoreTest {
    private static final int THREAD_COUNT = 30; //线程规模
    private static ExecutorService threadPool = Executors.newFixedThreadPool(THREAD_COUNT);
    private static Semaphore s = new Semaphore(10);

    public static void main(String[] args) {
        for (int i = 0; i < 100 * THREAD_COUNT; i++) { //任务数量远大于线程数
            threadPool.execute(new Runnable() {
                @Override
                public void run() {
                    try {
                        s.acquire();  //获取信号量
                        printThreadCount();
                        s.release(); //释放信号量
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
        }
        threadPool.shutdown();
    }

    private static synchronized void printThreadCount() {
        System.out.println("当前可用许可证数："+s.availablePermits() + " 等待线程数" + s.getQueueLength());
    }
}

private final Sync sync;

public Semaphore(int permits) {
    sync = new NonfairSync(permits);
}

Sync(int permits) {
    setState(permits);
}

protected final void setState(int newState) {
    state = newState;
}

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

protected int tryAcquireShared(int acquires) {
    return nonfairTryAcquireShared(acquires);
}

final int nonfairTryAcquireShared(int acquires) {
    for (;;) {
        int available = getState();
        int remaining = available - acquires;//目前剩余信号量，小于0证明已经无可用
        //尝试判断，小于0或者原子重置信号量值失败，都会返回负值，然后进入等待队列
        if (remaining < 0 ||
            compareAndSetState(available, remaining))
            return remaining;
    }
}

/**
 * Atomically increments by one the current value.
 *
 * @return the updated value
 */
public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

/**
 * Atomically adds the given value to the current value.
 *
 * @param delta the value to add
 * @param valueOffset the value memory address.
 * @return the updated value
 */
public final int addAndGet(int delta) {
    return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
}

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

private volatile int value;

/**
 * Creates a new {@code AtomicBoolean} with the given initial value.
 *
 * @param initialValue the initial value
 */
public AtomicBoolean(boolean initialValue) {
    value = initialValue ? 1 : 0;
}

/**
 * Atomically sets to the given value and returns the previous value.
 *
 * @param newValue the new value
 * @return the previous value
 */
public final boolean getAndSet(boolean newValue) {
    boolean prev;
    do {
        prev = get();
    } while (!compareAndSet(prev, newValue));
    return prev;
}

public final boolean compareAndSet(boolean expect, boolean update) {
    int e = expect ? 1 : 0; //将boolean类型映射为int类型
    int u = update ? 1 : 0;
    return unsafe.compareAndSwapInt(this, valueOffset, e, u);//通过原子操作更新当前值。
}

public final int updateAndGet(int i, IntUnaryOperator updateFunction) {
    long offset = checkedByteOffset(i);//得到下标在内存中的地址
    int prev, next;
    do {
        prev = getRaw(offset);
        next = updateFunction.applyAsInt(prev);//转为int
    } while (!compareAndSetRaw(offset, prev, next));
    return next;
}

//在内存中取得当前值
private int getRaw(long offset) {
    return unsafe.getIntVolatile(array, offset);
}

//以原子方式修改数组偏移量的值
private boolean compareAndSetRaw(long offset, int expect, int update) {
    return unsafe.compareAndSwapInt(array, offset, expect, update);
}

package longkai;

import java.util.concurrent.atomic.AtomicReference;

public class AtomicReferenceTest {
    public static void main(String[] args) {
        AtomicReference<User> atomicReference = new AtomicReference<User>();
        User firstUser = new User("long", 23);
        atomicReference.set(firstUser);
        User secondUser = new User("kai", 24);
        atomicReference.compareAndSet(firstUser, secondUser);
        System.out.println(atomicReference.get().getName());
        System.out.println(atomicReference.get().getAge());

    }
}

class User {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public String getName() {
        return name;
    }
}

public final boolean compareAndSet(V expect, V update) {
    return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
}

/**
 * 如果当前值为var4，则将值更新为var5
 */
public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var5);