并发容器和队列

//最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
//默认容量
private static final int DEFAULT_CAPACITY = 16;
//array的大小，只用于toarray方法
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//根据这个数来计算segment的个数,segment的个数是仅小于这个数且是2的几次方的一个数（ssize）
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//加载因子
private static final float 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;
//每次进行转移的最小值这个值作为一个下限来避免Rsisize遇到过多的内存争用
private static final int MIN_TRANSFER_STRIDE = 16;
// 生成sizeCtl所使用的bit位数
private static final int RESIZE_STAMP_BITS = 16;
// 进行扩容所允许的最大线程数
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 记录sizeCtl中的大小所需要进行的偏移位数
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// 一系列的标识
//forwarding nodes 主要作用是表征一个节点已经被处理干净（resize的时候被转移到新表了）
static final int MOVED     = -1; // hash for forwarding nodes
//表示树的根节点
static final int TREEBIN   = -2; // hash for roots of trees
//表示transient
static final int RESERVED  = -3; // hash for transient reservations
//31个1用来计算普通的node的哈希码
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
// 获取可用的CPU个数
static final int NCPU = Runtime.getRuntime().availableProcessors();
// 进行序列化的属性
private static final ObjectStreamField[] serialPersistentFields = {
    new ObjectStreamField("segments", Segment[].class),
    new ObjectStreamField("segmentMask", Integer.TYPE),
    new ObjectStreamField("segmentShift", Integer.TYPE),
};

//省略部分代码

//也是用节点数组来构成哈希表，在第一次插入的时候会懒初始化，size是2的整数次幂，直接通过iterators来访问
transient volatile Node<K,V>[] table;
//默认null，扩容时新生成的数组，是原数组的2倍
private transient volatile Node<K,V>[] nextTable;
//用来计算整个表的size，和longadder里面的base一致
private transient volatile long baseCount;
//用来控制表初始化，当为负数值。各种状态下这个int的值如下:
//初始化的：-1
//resize：-(1 + 被激活的参与resize的数量)
//表为空：表的initial size，如果没有这个值则为0
//初始化后：该表下次应该resize的值，等于当前表的size的0.75倍
private transient volatile int sizeCtl;
//当resizing的时候下一个tab下标索引值（当前值+1）
private transient volatile int transferIndex;
//当resize和创建counterCells的时候的自选锁，和longadder一致
private transient volatile int cellsBusy;
//和longadder的cells一致
private transient volatile CounterCell[] counterCells;

//Node节点定义，可以看出Node是一个键值对
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
//ConcurrentHashMap中的HashEntry相对于HashMap中的Entry有一定的差异性：HashEntry中的value以及next都被volatile修饰，这样在多线程读写过程中能够保持它们的可见性。
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val) {
        this.hash = hash;
        this.key = key;
        this.val = val;
    }

    Node(int hash, K key, V val, Node<K,V> next) {
        this(hash, key, val);
        this.next = next;
    }

    public final K getKey()     { return key; }
    public final V getValue()   { return val; }
    public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
    public final String toString() {
        return Helpers.mapEntryToString(key, val);
    }
//不允许直接setValue
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    // 它增加了find方法辅助map.get()方法。
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

//当链表长度过长的时候，会转换为TreeNode，是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。在红黑树结构中实际存放数据的节点
static final class TreeNode<K,V> extends Node<K,V> {……}
//存储对红黑树节点的引用。他是一个对象，包装的很多TreeNode节点，它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象。
static final class TreeBin<K,V> extends Node<K,V> {……}
//一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询下一个节点，而不是以自身为头节点进行查找下一个节点，可以比喻成两个车厢之间的链子。
static final class ForwardingNode<K,V> extends Node<K,V> {……}
//占位加锁节点，执行某个方法时，对其加锁。
static final class ReservationNode<K,V> extends Node<K,V> {……}

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 计算key的hash值
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
// 表不为空并且表的长度大于0并且key所在的桶不为空
        if ((eh = e.hash) == h) {
// 表中的元素的hash值与key的hash值相等
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
// 键相等，返回值
                return e.val;
        }
        else if (eh < 0)// 结点hash值小于0
// 在桶（链表/红黑树）中查找
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {// 对于结点hash值大于0的情况
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    /**
     * 序列化ID。这个类依赖于默认的序列化
     *甚至对于默认序列化的项数组，即使
     *它是空的。否则，它不能被声明为.，即
     *这里需要。
     */
    private static final long serialVersionUID = -817911632652898426L;
    /** 排队的物品 */
    final Object[] items;
    /** 用于下一次获取、轮询、查看或删除的项目索引 */
    int takeIndex;
    /** 下一个put、.或add的项目索引 */
    int putIndex;
    /** 队列中的元素数量 */
    int count;
    /*
     * 并发控制使用经典的两条件算法
     *发现在任何教科书。
     */
    /** 主锁保护所有通道 */
    final ReentrantLock lock;
    /** 等待获取的条件 */
    private final Condition notEmpty;
    /** 等待放入的条件 */
    private final Condition notFull;

public class BlockingQueueTest {
    public static void main(String[] args) throws InterruptedException {
        ArrayBlockingQueue abq = new ArrayBlockingQueue(10, true);
        for (int i = 1; i <= 10; i++) {
            put(abq, i);
            get(abq);
        }
    }

    private static void get(ArrayBlockingQueue abq) throws InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(2);
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    Integer integer = null;
                    try {
                        integer = (Integer) abq.take();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    if (null == integer) {
                        System.out.println("队列是空，没有取到元素");
                    } else {
                        System.out.println("取到了一个元素是:" + integer + "---目前队列中元素个数是 :" + abq.size());
                    }
                }
            });
        executorService.shutdown();
    }

    /**
     * 添加元素
     *
     * @param abq
     * @param i
     */
    private static void put(ArrayBlockingQueue abq, int i) throws InterruptedException {
        abq.put(i);
        System.out.println("存入了一个元素是   " + i);
    }
}

public boolean offer(E e) {
        //首先入队的对象不允许为null
        checkNotNull(e);
        //入队前，创建一个入队节点，构造一个内部函数
        final Node<E> newNode = new Node<E>(e);
        //死循环，入队不成功反复入队。
        for (Node<E> t = tail, p = t;;) {
             //创建一个指向tail节点的引用
            Node<E> q = p.next;
            //如果q=null说明p是尾节点则插入
            if (q == null) {
                // cas插入
                if (p.casNext(null, newNode)) {
                    //cas成功说明新增节点已经被放入链表，然后设置当前尾节点
                    if (p != t) // 一次跳两个节点
                        casTail(t, newNode);  // 失败是可以的.
                    return true;
                }
                // 丢失的CAS与另一线程竞争；重新读取下一个
            }
            else if (p == q)
            //多线程操作时候，由于poll时候会把老的head变为自引用，然后head的next变为新head，所以这里需要
            //重新找新的head，因为新的head后面的节点才是激活的节点
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
 p = (p != t && t != (t = tail)) ? t : q;
        }
    }
private static void checkNotNull(Object v) {
        if (v == null)
            throw new NullPointerException();
    }

public E poll() {
        restartFromHead:
        //死循环
        for (;;) {
            //死循环
            for (Node<E> h = head, p = h, q;;) {
                //保存当前节点值
                E item = p.item;
                //当前节点有值则cas变为null
                if (item != null && p.casItem(item, null)) {
                    //cas成功标志当前节点以及从链表中移除
                    if (p != h) // 类似tail间隔2设置一次头节点
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
                //当前队列为空则返回null
                else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                }
                //自引用了，则重新找新的队列头节点
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
}