[数据结构与算法]并发编程-08.HashMap等集合

HashMap

数据结构

JDK 1.6 数组 + 链表

JDK 1.8 开始 数组 + 链表 + 红黑树

引入链表结构解决hash冲突，JDK1.8开始采用尾插法（1.8以前头插法），链表时间复杂度O(n)

hash 并不是采用取模(%)运算，而是采用位&运算，从效率上来讲，位运算效率远高于%取模运算，位运算是最接近机器能识别的语言

虽然引入了红黑树，解决了链表成环问题，但效率并未得到大的提升，在数据量较小的时候效率甚至会更低，在数据量较大的时候效率大概有 5-10% 的提升

HashMap容量

定义： 数组的大小

new HashMap()： 如果不写构造参数，默认容量16，DEFAULT_INITIAL_CAPACITY = 1 << 4

注意： HashMap容量必须满足2ⁿ。比如 new HashMap(20)，因为2⁴ < 20 < 2⁵，故将其初始容量设置为32。

HashMap容量必须满足2ⁿ>的原因：

① JDK1.8 高低位运算需要使用

②按位与高效替代取余也必须满足2ⁿ-1

roundUpToPowerOf2(size); // 强制将其转换为最接近size且大于sized的2的指数次幂

HashMap是线程不安全的。高并发场景下 get 操作也可能带来数据丢失。JDK1.8以下可能多线程情况下扩容可能发生链表成环，引发死锁问题。

HashMap保证有序性的扩展

• 单线程环境：TreeMap：key 有序，

• 多线程环境：跳表ConcurrentSkipListMap：O(logⁿ)，底层是基于链表O(n)的，维护了索引降低了时间复杂度

源码分析

重要成员变量

DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash表默认初始容量 16

MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量 2³⁰

DEFAULT_LOAD_FACTOR = 0.75f；默认负载因子

TREEIFY_THRESHOLD = 8；链表转红黑树阈值

UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值

MIN_TREEIFY_CAPACITY = 64；链表转红黑树时 hash 表最小容量阈值，达不到优先扩容

JDK 1.8 链表转红黑树的两个条件：

• 链表长度 > 8
• 链表转红黑树时 Hash 表最小容量阈值，否则优先扩容

默认加载因子:DEFAULT_LOAD_FACTOR = 0.75f

数组使用率大于此百分比数值时会进行扩容，该值是综合实践与空间上的均衡后考虑的。全放满再扩容，容易发生 hash 碰撞，时间复杂度O(n)，效率不高。如果小于此值，可能浪费空间。但 0.75 亦不是最优解，最优的考虑是基于概率问题的牛顿二项式，基于时间与空间后折中计算后大约为 0.693。

为什么链表长度大于 8 才开始扩容

源码中有注释，在默认加载因子0.75的情况下，根据概率分布泊松分布，当链表长度达到 8 出现的几率是千万分之6，之后的概率不到千万分之一（数据量极大时才会转换）

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

JDK 1.7 扩容链表成环导致死锁问题分析

/**
 * 扩容转移数据
 */
void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
    for (Entry<K,V> e : table) { // 遍历数组
    	while(null != e) { // 哈希碰撞，重新计算hash
            Entry<K,V> next = e.next;// 记录oldhash表中e.next
            if (rehash) {
            	e.hash = null == e.key ? 0 : hash(e.key); // 再次进行hash计算
            }
        	int i = indexFor(e.hash, newCapacity);// rehash计算出数组的位置(hash表中桶的位置)
            e.next = newTable[i];// 头插法，e要插入链表的头部， 所以要先将e.next指向new hash表中的第一个元素
            newTable[i] = e;// 将e放入到new hash表的头部
            e = next;// 转移e到下一个节点， 继续循环下去
        }
    }
}

/**
 * 计算索引
 */
static int indexFor(int h, int length) {
	return h & (table.lenth-1); // 按位与(&)替代取模(%)更高效，但必须是2的n次幂-1
}

注意： 任意数与(&) 2ⁿ 只能有两种结果（如果table.length = 16 只可能得到0或16,还可能越界,故采用 h & (table.lenth-1)，即能防止越界，还可以得到 table.length 个结果。

单线程情况下扩容：

假设 hash 表初始长度为 2，某一数组位置上有 key：{3,5,7}，按照 Hash 算法取余运算（key%table.length）得到其都碰撞在table[1]上。

假设 hash 表长度扩容到 4，重新计算 hash 得到 table[3] : {3,7}，table[1]：{5}，当 e.next == null 时跳出循环，扩容结束，扩容过程如下：

多线程情况下扩容：

假设有两个线程同时进行 put ,并且同时进入 transfer() 方法，高并发环境下，极易导致链表成环的问题。

JDK8 的改进

• JDK8 对 HashMap 进行了优化，完全抛弃了原来到扩容方法，采用高低位拆分转移方式，避免了链表环的产生。
• 因为使用了高低位指针，完全绕开了rehash，必须满足高低位的移动，故数组扩容量必须是2ⁿ
• 引入红黑树

TREEIFY_THRESHOLD = 8；链表转红黑树阈值(长度大于等于 9 开始扩容)

UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值

MIN_TREEIFY_CAPACITY = 64；链表转红黑树时hash表最小容量阈值，达不到优先扩容

resize方法部分源码分析：

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) { // & 原数组长度，只有0或oldTable.length
        // xxx.hashcode & table.length = 0 使用低位指针
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        // xxx.hashcode & table.length = 0 使用高位指针
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
// 高位指针
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead; // 移到新的数组上同样hash桶的位置
}
//低位指针
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead; // index + oldTable.length
}

ConcurrentHashMap

数据结构

JDK1.7 分段锁（Segment 数组） + 链表 + CAS + 红黑树

JDK1.8 分段锁（Node<K,V> 锁住链表(桶Bucket)）+ 链表 + CAS + 红黑树

写(put)同步（有Hash碰撞才同步），读 (get) 无锁，加锁时是给第一个Hash表某一 Segment 加锁，实现分段锁的效果，不同的 Segment 的 put 操作也是可以并发执行的

JDK 1.7 与 JDK1.8 在实现 ConCurrentHashMap 与 HashTable 区别

HashTable： 全局锁，直接锁住整个 Hash 表

JDK 1.7 ConCurrentHashMap： 分段锁（Segment 数组） + 链表 + CAS ，大的 Hash 表里面套小的 Hash 表，小的 Hash 表里面存储数据当加锁的时候锁住某个小的 Hash 表

Segmen<K,V> 继承了 ReentrantLock，所有天生代加锁、解锁操作，Segment 是一种可重入锁，HashEntry存储键值对

JDK 1.7 HashMap结构（未展示红黑树部分）

Segment<K,V> s0 = new Segment<K,V>(loadFactor,(int cap * loadFactor)),
						(HashEntry<K,V>][]) new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V> []) new Segment[ssize];

JDK 1.8 ConCurrentHashMap： JDK1.8 分段锁（Node<K,V> 锁住链表(桶Bucket)）+ 链表 + 红黑树 + CAS + synchronized

JDK1.8 抛弃了 Segment 分段锁，采用1.8 采用 Node + CAS + synchronized 来保证并发安全进行实现，锁粒度更细，只锁单个链表（Node[i]）

JDK 1.7 HashMap结构

// 部分代码已省略，仅展示表示结构部分
for (Node<K,V>[] tab = table;;) { // Node数组
	Node<K,V> f;// 链表
}

JDK 1.8 ConcurrentHashMap 相较于 JDK 1.7 的优化

• 锁粒度更小，数据结构上抛弃了原来到 Segment 数组作为分段锁，采用 Node<K,V> []结构
• 整体采用 CAS 无锁并发，效率更高(插入时采用sychronized锁住了桶对象(即：单个链表))
• 多线程协助扩容，引入了标志位，当一个线程插入数据时发现正在扩容(hash = MOVED)，不会阻塞等待扩容完成，而是检查是否可以协助其一起完成扩容操作（最少协助迁移16个槽位），这样既不会阻塞线程也达到了并发处理，加快迁移速度的效果

JDK 1.8 ConCurrentHashMap 源码分析：

重要成员变量

和HashMap一样有的成员变量（部分参数名不同）

• DEFAULT_CAPACITY= 16; Hash表默认初始容量 16

• MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量 2³⁰

• LOAD_FACTOR = 0.75f；默认负载因子

• TREEIFY_THRESHOLD = 8；链表转红黑树阈值

• UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值

• MIN_TREEIFY_CAPACITY = 64；链表转红黑树时hash表最小容量阈值，达不到优先扩容

ConCurrentHashMap独有的种要成员变量

• MIN_TRANSFER_STRIDE = 16; table 扩容时, 每个线程最少迁移 table 的槽位个数
• MOVED = -1; 当 Node.hash 为 MOVED 时, 代表着 table 正在扩容
• TREEBIN= -2; 代表此元素后接红黑树
• Node<K,V>[] nextTable; table迁移过程临时变量, 迁移过程中将元素全部迁移到nextTable上
• int sizeCtl; 用来标志 table 初始化和扩容的，不同的取值代表着不同的含义:

• • • 0: table还没有被初始化

    • -1: table正在初始化

    • 小于-1: 实际值为resizeStamp(n)<<RESIZE_STAMP_SHIFT+2, 表明table正在扩容

    • 大于0: 初始化完成后, 代表 table 最大存放元素的个数, 默认为0.75 * n

• int transferIndex: table 容量从 n 扩到 2n 时, 是从索引 n->1 的元素开始迁移, transferIndex 代表当前已经迁移的元素下标
• class ForwardingNode<K,V> extends Node<K,V>: 一个特殊的Node节点, 其hashcode=MOVED, 代表着此时table正在做扩容操作。扩容期间, 若table某个元素为null, 那么该元素设置为ForwardingNode, 当下个线程向这个元素插入数据时, 检查hashcode=MOVED, 就会帮着扩容

• 一个线程插完元素后, 检查 table 使用率, 若超过阈值, 调用 transfer() 进行扩容
• 一个线程插入数据时, 发现 table 对应元素的 hash = MOVED, 那么调用helpTransfer()协助扩容。

源码分析

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    // Node<K,V>[] 数组
    for (Node<K,V>[] tab = table;;) { // 自旋，保证插入都成功
        Node<K,V> f; int n, i, fh;
        // 未初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); // 初始化Hash表，见下源码
        // 已初始化，索引位为null，CAS往索引位添加HashEntry，没有插入成功自旋重新插
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                break;                   // 添加到空位时没有锁
        }
        // 当前put线程发现hash表正在扩容，协助其扩容=>最少分配16个槽位迁移给该线程迁移
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f); // 见下源码
        // 该索引位有数据，且未在扩容
        else {
            V oldVal = null;
            synchronized (f) { // 锁住前一个对象
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        // 自旋，保证插入成功，e = f 尾部插入
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 判断 key 是否在链表上存在，不存在构建链表
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 构建链表
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    // 后面就是红黑树
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 链表转红黑树
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

初始化Hash表

/**
 * Initializes table, using the size recorded in sizeCtl.
 * 初始化Hash表
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // 自旋，表初始化也存在竞争
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // 没有拿到锁的一直yield等待拿到锁的线程初始化完毕
        // CAS竞争锁，sizeCtl 0 => -1 改变标志位，已初始化
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

协助扩容，主要功能如下：

• 检查是否扩容完成

• 经过一些列的判断如果还需要帮助扩容，对sizeCtrl = sizeCtrl+1, 然后调用 transfer() 进行真正的扩容

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { //table扩容
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            // 根据 length 得到一个标识符号
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {// 说明还在扩容
                //判断是否标志发生了变化 ||  扩容结束了
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                     //达到最大的帮助线程 ||  判断扩容转移下标是否在调整（扩容结束）
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                // 将 sizeCtl + 1, （表示增加了一个线程帮助其扩容）
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab); // 扩容，见下面源码
                    break;
                }
            }
            return nextTab;
        }
        return table;
}

扩容transfer ：新建一个nextTab, size是之前的2倍, 将table上的非空元素迁移到nextTab上面去

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
       // subdivide range，每个线程最少迁移16个槽位，大的话，最多
        stride = MIN_TRANSFER_STRIDE;
    // initiating  才开始初始化新的nextTab
    if (nextTab == null) {
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];  //扩容2倍
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;//更新的转移下标，
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    //是否能够向前推进到下一个周期
    boolean advance = true;
    // to ensure sweep before committing nextTab，完成状态，如果是，则结束此方法
    boolean finishing = false;
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) { //取下一个周期
            int nextIndex, nextBound;
            //本线程处理的区间范围为[bound, i),范围还没有处理完成，那么就继续处理
            if (--i >= bound || finishing)
                advance = false;
            //目前处理到了这里（从大到小， 下线），开始找新的一轮的区间
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            //这个条件改变的是transferIndex的值，从16变成了1
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                     //nextBound 是这次迁移任务的边界，注意，是从后往前
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound; //一块区间最小桶的下标
                i = nextIndex - 1; //能够处理的最大桶的下标
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) { //每个迁移线程都能达到这里
            int sc;
            if (finishing) { //迁移完成
                nextTable = null;
                //直接把以前的table丢弃了，上面的MOVE等标志全部丢弃，使用新的
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1); //扩大2n-0.5n = 1.50n, 更新新的容量阈值
                return;
            }
            //表示当前线程迁移完成了
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                 //注意此时sc的值并不等于sizeCtl，上一步，sizeCtl=sizeCtl-1了。这两个对象还是分割的
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        //如果对应位置为null， 则将ForwardingNode放在对应的地方
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED) //别的线程已经在处理了，再推进一个下标
            advance = true; // already processed，推动到下一个周期，仍然会检查i与bound是否结束
        else { //说明位置上有值了，
            //需要加锁，防止再向里面放值，在放数据时，也会锁住。比如整个table正在迁移，还没有迁移到这个元素，另外一个线程向这个节点插入数据，此时迁移到这里了，会被阻塞住
            synchronized (f) {
                if (tabAt(tab, i) == f) {//判断i下标和f是否相同
                    Node<K,V> ln, hn; //高位桶， 地位桶
                    if (fh >= 0) {
                        int runBit = fh & n;//n为2^n, 取余后只能是2^n
                        Node<K,V> lastRun = f;
                        ///找到最后一个不和fn相同的节点
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            //只要找到这，之后的取值都是一样的，下次循环时，就不用再循环后面的
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else { //比如1，16，32,如果低位%16，那么肯定是0。
                            hn = lastRun;
                            ln = null;
                        }
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                 //这样就把相同串的给串起来了
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                //这样就把相同串的给串起来了，注意这里ln用法，第一个next为null，烦着串起来了。
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln); //反着给串起来了
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) {// 如果是红黑树
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null; //也是高低节点
                        TreeNode<K,V> hi = null, hiTail = null;//也是高低节点
                        int lc = 0, hc = 0;
                        for (Node<K,V> e = t.first; e != null; e = e.next) { //中序遍历红黑树
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
                            if ((h & n) == 0) { //0的放低位
                                //注意这里p.prev = loTail，每一个p都是下一个的prev
                                if ((p.prev = loTail) == null)
                                    lo = p; //把头记住
                                else
                                    loTail.next = p;  //上一次的p的next是这次的p
                                loTail = p; //把上次p给记住
                                ++lc;
                            }
                            else { //高位
                                if ((p.prev = hiTail) == null)
                                    hi = p; //把尾记住
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :// //判断是否需要转化为树
                            (hc != 0) ? new TreeBin<K,V>(lo) : t; //如果没有高低的话，则部分为两个树
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}

链表迁移原理：

• 遍历链表每个节点。 若节点的f.hash&n==0成立, 则将节点放在i, 否则, 则将节点放在n+i上面。
• 迁移前, 对该元素进行加锁。 遍历链表时, 这里使用lastRun变量, 保留的是上次hash的值, 假如整个链表全部节点f.hash&n==0, 那么第二次遍历, 只要找到lastRun的值, 那么认为之后的节点都是相同值, 减少了不必要的f.hash&n取值。遍历完所有的节点后, 此时形成了两条链表, ln存放的是f.hash&n=0的节点, hn存放的是非0的节点, 然后将ln存放在nextTable第i元素的位置, n+i存放在n+i的位置。

CopyOnWrite机制

问题：ArrayList 的 failfast 机制（失败快速重置机制）:

在ArrayList在执行写操作（插入删除等）过程中，另一个线程去对它进行读操作，会破坏平衡，抛出异常（ConcurrentModificationException）,是线程不安全的，所有 JAVA 引入了CopyOnWriteArrayList保证线程安全。

写多读少的情况下： 扩展ArrayList，重写add 方法加锁

读多写少，竞争不激烈情况下可以考虑：

CopyOnWrite 的核心思想： 读写分离，空间换时间，避免为保证并发安全导致的激烈锁竞争

适用：读多写少，竞争不激烈

特点：

• 读写分离
• 写加锁，读不加锁
• 只最终一致性，写过程中的更新等不会被读到
• 要保证其他线程及时读到最新数据可以使用volatile变量

CopyOnWriteArrayList 读写过程：

CopyOnWriteArrayList 源码分析：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //加锁
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //复制一个array副本
        Object[] newElements = Arrays.copyOf(elements, len + 1); 
        newElements[len] = e; // 往副本里写入
        setArray(newElements); // 副本替换原数组，成为新的原数组
        return true;
    } finally {
        lock.unlock(); // 释放锁
    }
}
public E get(int index) {
    return get(getArray(), index); 
}

运算符

在阅读源码时可能遇到运算符不了解的情况，下面整理了一些常用的运算符：

二进制数在内存中是以补码的形式存放的（否则有符号运算时会发生异常）。正数的补码、反码都是其本身。负数的反码为符号位为1,其它位是原码取反。补码是符号位为1,其它位是原码取反，未位加1，即反码未位加 1

<< 表示左移。不分正负数，低位补 0，相当于乘 2ⁿ

>> 表示右移。如果该数为正，则高位补 0，若为负数，则高位补 1，相当于除 2ⁿ

>>> 表示无符号右移。也叫逻辑右移，即若该数为正，则高位补 0，而若该数为负数，则右移后高位同样补 0。正数时和 >> 结果相同。

& 表示按位与。只有两个数的二进制同时为1，结果才为1，否则为0。（负数按补码形式参加按位与运算），3 &5 即 00000011 & 00000101 = 00000001 ，所以 3 & 5的值为1

| 表示按位或。参加运算的两个数只要两个数中的一个为1，结果就为1，2 | 4 即 00000010 | 00000100 = 00000110 ，所以2 | 4的值为 6

~ 表示按位取反。~n = -(n+1)，n+1就可以表示为 -~n

4
//补码: 0 100
//取反: 1 011
//反码: 1 010
//原码: 1 101 = -5

^ 表示按位异或。参加运算的两个数，如果两个相应位为值不同，则该位结果为1，否则为0， 2 ^ 4 即 00000010 ^ 00000100 =00000110 ，所以 2 ^ 4 的值为6

运算符优先级：

n |= n >>> 1 => n = n | n >>> 1 => n = n | (n >>> 1)