适配器（设计模式）

适配器模式之所以存在，和不同手机充电线的接头互不相同是一样的。

比如说，假设现在只有一个带标准USB插口的充电器，怎么样才既能给Android手机充电，又能给iPhone充电呢？答案当然是使用不同的充电线，一条有micro接口，一条有雷电接口。也就是说，我们使用充电线后，虽然仍旧是使用标准USB接口充电，但实际上负责传电的已经变成了micro usb接口和雷电接口，充电线其实就是个另类的适配器。

再举个例子：

假设我们现在有个类son，实现了Eat接口，Eat接口里有EatFood方法，同时还有一个外部类mother（内部聚合了一个son版Eat接口），mother会调用Eat接口的EatFood方法，让son去吃饭。现在mother让son去吃饭时再带上一个女孩一起吃(绝对是亲生的的有木有)，但不允许修改son和Eat接口，这时怎么办？（要求是不改变原有接口的同时，还能使用新功能）

这时我们可以创建一个撩妹版son（handSomeSon），他也实现了Eat接口，他在实现EatFood方法时，偷偷地在调用了另一个新接口EatWithGirl的EatFoodWithGril方法，这样一来，mother（内部聚合了一个handSomeSon版Eat接口）还是调用Eat接口的EatFood方法，撩妹版son就和妹子去吃饭去了。也就是说，我们不改变原有接口Eat，却使用到了新接口EatWithGirl的功能。

至于适配器模式的优缺点，可以总结如下。

优点

  • 将目标类(mother)与适配者类(EatWithGirl接口）解耦，并不直接连通。
  • 代码灵活性和扩展性都非常好，符合开闭原则。
  • 类适配器模式（handSomeSon继承自实现了EatWithGirl接口的类）有个优点，可以在适配器handSomeSon中修改实现了EatWithGirl接口的类的方法，适配器更加灵活。
  • 对象适配器模式（handSomeSon内部有实现了EatWithGirl接口的类的对象实例）有个优点，可以同时适配实现了EatWithGirl接口的类和该类的子类。

缺点

  • 类适配器模式的缺点正好和对象适配器的优点相反，而对象适配器模式的缺点正好和类适配器的优点相反。
  • 适配器可能会有许多子类（对象适配器）或许多适配器类（类适配器）

JDK源代码之Vector

Vector是和HashTable一个时代的容器，拥有支持同步的特点（各个方法前一律加上synchronized关键字）。后来不支持同步的ArrayList替代了Vector，日渐流行，也正是因为这个原因，Vector和ArrayList的内部实现都差不多。

具体的源码我就不一一注释，只放出让我觉得有意思的方法。

Vector默认的容量是10，扩容时加上一个capacityIncrement或直接翻倍。

System.arraycopy与Arrays.copyOf

我在研究源码时，发现Vector里间替地使用以上2个方法，它们究竟有什么差别呢？
翻出Arrays.copyOf的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")

    // 利用反射机制创建一个新的数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);

    // copyOf依旧调用System.arraycopy
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

可见，copyOf也会调用arraycopy，而且会创建一个新的数组。
而arraycopy会调用系统底层的复制方法，不同系统的arraycop是不同滴。

removeElementAt(int index)与insertElementAt(E obj, int index)

以上2个方法都会调用系统底层的数组复制函数，复杂度都是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 删除元素
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);
    }
    elementCount--;

    // GC优化
    elementData[elementCount] = null; /* to let gc do its work */
}

// 增加元素
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    // 调用系统底层的arraycopy
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

synchronized

Vector之所以与ArrayList不同，支持同步，完成是多亏了synchronized这个关键字。
Vector和HashTable一样，虽然支持同步，但却被抛弃了。

JKD源代码之HashTable

HashTable是个比较古老的实现，现在已经不推荐使用，虽然它比HashMap多了支持同步，但在同步并发方面ConcurrentHashMap更强，而不考虑同步的话，HashMap效率比它高了不少，正如官方注释一样：“If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.”

在get()/put()/remove()等方法上，HashTable都加上了synchronized关键字，以此来实现同步，但熟悉JVM的童鞋都知道，synchronized关键字的代价很高，涉及到内核态和用户态的切换，所有HashTable的效率比较低。

在计算数组下标时，HashTable用了相对比较简单的求模运算，而不像HashMap那样做了移位优化：

1
int index = (hash & 0x7FFFFFFF) % tab.length;

获取：public synchronized V get(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 计算出数组下标
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 遍历该链，找到哈希码和key都相同的元素
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

可见，HashTable内部在处理冲突时，只是单纯地用链来实现，而不像HashMap一样，在冲突过多时，使用红黑树来优化。

添加：public synchronized V put(K key, V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public synchronized V put(K key, V value) {
    // Make sure the value is not null
	// 不允许value为空
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 遍历现有元素，如果有相同的key，就替换
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    // 如果不存在相同的key，就往里边插入一个新的key
    addEntry(hash, key, value, index);
    return null;
}

HashTable不允许空的key，也不允许空的value。

添加一个新的键值对：private void addEntry(int hash, K key, V value, int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // 将新的键值对插到链头
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

在这里可以看出，当有新的冲突出现时，新的冲突会插在链头（也许是用了程序局部性原理）

删除：public synchronized V remove(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 找到数组下标
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
    	       // 寻找待删除的键值对
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            // 如果不是链头
            if (prev != null) {
                prev.next = e.next;
            // 处在链头
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

重散列算法：protected void rehash()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 同样，容量扩大一倍（默认容量是11）
    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    // 从后往前遍历旧数组
    for (int i = oldCapacity ; i-- > 0 ;) {
        // 遍历该下标处的冲突链
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            // 计算新下标
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            // 插入新数组
            newMap[index] = e;
        }
    }
}

JDK源代码之HashMap

HashMap首先是一种Map结构，将一个key映射到一个value，有点特殊的是，HashMap不仅允许value为空，也允许key为空。

其次，HashMap继承自抽象map，而不是像HashTable那样继承自Dictionary（虽然都实现了Map接口）；另外，HashTable是同步的，而HashMap并不支持同步。

HashMap内部使用了Hash机制，该机制可以有效地将add与get的平均复杂度降低为O(1)（以前get在最坏的情况下会是O(n)，现在当哈希码相同的同一条链上元素数目超过8时，该链会转为平衡树，所以最坏的情况下是O(logN)）

重要字段

默认容量：DEFAULT_INITIAL_CAPACITY

HashMap的默认容量，初始值设为16。初始值的设置是有讲究的，必须是2的N次方形式，为什么？在为key计算下标时，我们需要让key的哈希码和数组容量做与运算，2的冥可以使得数据更加分散。

最大容纳因子：loadFactor

HashMap的饱和比例，默认为0.75，当HashMap中的数据量达到75%时，HashMap会启用resize()方法扩大容量，扩大为之前的2倍，也就是newCap = oldCap << 1。

节点数组：Node<K,V>[] table

可见HashMap内部其实使用了数组，节点数组，每个Node节点是一个键值对，各个键值对之间通过next指针相连在一起。

Node的源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    // 每个键值对的哈希码也是独一无二的
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    // 更换该键值对的值
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    // 判断两个键值对是否equals，不仅key要相同，而且value也要相同
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Set<Map.Entry<K,V>> entrySet

存储键值对的一个set集合，它和上面的table有什么区别？似乎被抛弃了，因为已经有了entrySet()方法。

size

HashMap内部数据的大小。

threshold

size的数值超过它时，HashMap必须扩容。

重要方法

计算哈希码：static final int hash(Object key)：

1
2
3
4
5
6
7
static final int hash(Object key) {
    int h;

    // 如果对象为空则返回0
    // 如果不为空，就求得key.hashCode()的结果h，将h与其左移16位后的结果做异或。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里为什么要和左移16位的结果呢？官方是这样解释的：“Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide.”。
原来，这是为了减小冲突，把高位的数据扩散到低位。举个例子，假设HashMap的数组大小是16，那么计算出来的哈希码必须和16（二进制是4个1）做与的运算，这样一来，哈希码只有低4位才起作用，如果有大量的key的哈希码的低4位都相同而更高位不同，它们最终依旧会放在同一个下标，哪怕它们之间因为高位不同而差别巨大。

扩容并重散列：final Node<K,V>[] resize()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {

       // HashMap原先的容量已经达到极限，无法扩容，直接返回旧的table
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }

        // 将容量直接翻倍，“可用容量”也翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 在HashMap为空的情况下进行扩容，初始化各项参数
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // 得到新的table数组，大小是原先的两倍
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {

       // 逐项扫描旧table数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;

            // 如果旧tabel数组的某一下标处不为空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;

                // 如果该下标处只有一个元素，而没有因哈希码相同而处在同一条链上元素
                if (e.next == null)
                   // 直接放入新的table数组。因为数组容量扩大一倍，有可能下标是之前的两倍，也有可能不变
                    newTab[e.hash & (newCap - 1)] = e;

                // 如果该下标处的元素是一个树节点。（哈希码冲突的key都放在同一棵树上，树根放在该哈希码对应的数组下标处）
                else if (e instanceof TreeNode)
                	 // 将旧的树分裂，放到新的数组中去
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                // 如果同一链中数据不到8个（仍未分裂为树），则将旧链分为2条新链
                else { // preserve order

                	 // 下标较小的新链(low)
                    Node<K,V> loHead = null, loTail = null;
                	// 下标较大的新链(high)
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 之前都是与oldCap-1（假设二进制有4位）做与运算，结果是4位二进制，如今与oldCap
                        // （有5位，且最高位为1其余为0）做运算，第5位是0的到下标低的新链，第5位是1的到下标大的新链
                        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);

                    // 将两条新链加入新table数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

该方法处理的数组下标处元素有以下3种情况：

  1. 该下标处不存在冲突的数据
  2. 该下标处存在冲突的数据，冲突的数据不够多，用一条链来存储（新的冲突的数据不再放在链头部，而是放在链尾部）
  3. 该下标处存在冲突的数据，冲突的数据特别多，用一棵平衡树来存储

该方法是HashMap中极为重要的方法，处理HashMap扩大容量时的各种情况。

关于该方法的性能：

  1. 如果是第一种情况，复杂度当然是O(1)
  2. 如果是第二种情况，复杂度是该链的长度，最差情况下会达到O(n)
  3. 如果是第三种情况，那么复杂度和红黑树的遍历有关，在下面分析到树的分裂时再具体分析。搜索插入删除的复杂度都能做到O(logN)。

插入：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)：将一个键值对插入HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 如果旧table数组为空，就需要调用resize方法来扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 哈希码与数组大小做与运算，寻找合适的下标。
    // 如果该下标处为空，就新建一个Node节点.
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    // 该下标已经有元素存在
    else {
        Node<K,V> e; K k;
        // 该下标的元素的key就是要插入的key
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 该下标的元素是个树节点（说明哈希码冲突的key过多，已经被逼用红黑树结构来存储）
        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);
                    // 如果该链的长度达到一定长度，就转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 该链中已经有该key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 插入后，考虑是否要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

该方法会将一个键值对插入到HashMap，哈希码由hash()方法计算得到。

和resize()方法类似，在插入键值对时也要分情况考虑：

  1. 如果数组下标处为空，则直接插入一个Node节点
  2. 如果数组下标处不为空，且是一个树节点，则插入键值对到该下标对应的红黑树中去
  3. 如果数组下标处不为空，且是一条链的链头，则尝试插入到链尾
  4. 在这过程中，如果key已经存在则返回

在插入后还要考虑是否要扩容。

获取value：final Node<K,V> getNode(int hash, Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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) {
        // 该下标处就是我们要找的key
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果该节点是树节点，则遍历对应的红黑树
        if ((e = first.next) != null) {
            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;
}

getNode方法根据key的哈希码和key来查找相应的value。
同样的，该方法也会分情况讨论。

删除：final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
    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;
        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 {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }

        // 分情况，将该节点删除
        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;
}

想要删除一个节点，首先要查找到该节点，事实上，该方法中的搜索过程和getNode一模一样。
找到后，也是根据数组下标处元素的不同来分情况，这里不再赘述。

static final int tableSizeFor(int cap)：对一个整数，求出大于它且最接近它的2的冥

1
2
3
4
5
6
7
8
9
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;
}

该方法非常巧妙，将最高位的1不断地置换到所有地位上去（结果类似于000011111111），最终加1，记得到2的冥次(也就是000111111111)。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)：将一堆数据插入HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {

       // 如果HashMap数组为空，没有元素
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);

            // 当前设置的“可用容量”不够，扩大“可用容量”。
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        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);
        }
    }
}

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)：将旧数组上的树分裂到新数组上去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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;
    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;
        }
    }

    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);
        }
    }
}

树的分裂，其复杂度似乎也是O(n)？将链转为树时涉及到红黑树的插入平衡等调整，尚未接触红黑树，待日后补充。

总结：不同于以前HashMap单纯用链来处理冲突，现在的HashMap引入了红黑树来应付大量的冲突，HashMap的效率提高了不少，当n是一百万时也可以接受，**至少在最坏情况下复杂度不再是O(n)**。

Object源码（JAVA）

我们都知道，JAVA是门面向对象语言，也就是说，JAVA中对象的地位是极高的。

遍观JDK源码，所有的类都继承自始祖级别的类：Object类。

Object类内部的方法有如下这些：

方法 说明
getClass() 获得该对象的Class类对象
clone() 克隆一份新对象，两个对象不==，但equals
toString() 以字符串形式，输出对象信息
hashCode() 获得该对象的哈希码
equals() 判断两个对象内容是否相等
finalize() 用于GC，当算法将该对象放入待清除队列后会尝试调用该方法一次
wait() 使得当前线程释放该对象的锁，让该对象恢复自由
notify() 唤醒一个等待该对象的线程，使得该对象被线程拥有
notify() 给所有等待的线程发去唤醒消息

源码

  1. toString()：该函数仅仅打印出对象所属的类+‘@’+对象哈希码

    1
    2
    3
    public String toString() {
        return getClass().getName() + "@" + Integer.toHexString(hashCode());
    }

  2. equals()：平时我们说==与equals是不同的两种东西，但这里的equals内部就是用了==来作比较。

    1
    2
    3
    public boolean equals(Object obj) {
        return (this == obj);
    }

  3. hashCode()：这里Object的hashCode方法没有实现，可以看一下String的hashCode是怎么实现的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 以下是String的hashCode()
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

    可见String在计算哈希码前会尝试返回上一次已经计算出来的结果，为什么要乘以31再加上字符的ANSC码呢？

  • 第一，乘上一个数是为了分权重（越在前面的字符在哈希码中权值越大，这使得前缀相同长度相同的字符串的哈希码差不多大，可以存放在相邻的地方）。
  • 第二，乘上31是因为31是素数，可以增大结果的唯一性。

从0到1理解JVM垃圾回收机制

从C++转到JAVA，首先要知道的一条是，JAVA拥有相对比较完善的内存垃圾回收机制（回想以前在中大的作业平台上写C++代码，在new之后总会忘记free，导致我每次都不能开开心心地AC，巨汗-_-!）

JAVA是一门半编译半解释的语言，在编译阶段无法确定回收垃圾的具体位置（虽然有部分是可以确定的），所以回收垃圾的任务主要交由JVM来处理，我们经常听到高手们谈到的所谓GC指的就是垃圾回收。

垃圾回收主要有两步：

  • 识别哪些是垃圾
  • 使用回收的算法将垃圾‘扫入’垃圾桶

谁是垃圾

在之前的博文里，我们知道JAVA运行时主要分程序计数器、虚拟机栈、本地方法栈、堆、方法区。前3者随着线程同生共死，当线程结束时，它们的内存就被回收了，只有剩下的堆和方法区需要我们竭尽全力地进行垃圾回收。

那么，在堆和方法区里，我们怎么知道谁是垃圾呢？

寻找垃圾算法之引用计数法

熟悉操作系统的童鞋都知道，引用计数算法的主要思想是：当有个地方引用了某个对象时，该对象的计数器增加1，当那个地方不再引用该对象时，该对象的计数器减1；直到计数器的值为0，系统就认为该对象不再有用，把它标记为垃圾。

一个论文引用的例子可以解释该算法：假设你是个德高望重的学者，你写了篇影响巨大的论文，那么你的论文理所当然会被许多人引用和参考，因为你的论文特别有价值；相反，如果你是个三流的研究人员，你写的东西无人问津，就会被视为“垃圾”。

这个算法最大的缺点是：它无法处理相互循环引用的情况。什么意思呢？

还是论文引用的例子：假设现在有3个三流的研究人员A、B和C，他们分别写出了3篇质量极其低下的论文，按理来说，他们的论文是“垃圾”，不会被人引用，但数据显示，3篇论文的被引用数都为1。相关部门调查后发现，A引用了B的论文，B引用了C的论文，而C又引用了A的论文，所以虽然3篇全都是“垃圾”，但却存在着彼此的引用，形成了一个环，使得人们认为3篇论文不是“垃圾”，逃过了被“回收”的危险。

因为这个缺点，引用计数法基本只作为反例，只存在于教科书上。

寻找垃圾算法之可达性分析算法

可达性分析的原理是：一个对象引用了另一个对象时，两个对象之间就存在连线，理清了所有的对象的引用关系之后，它们基本都会处在同一颗树上，此时，将不在树上的对象视为垃圾。也就是说，那些无人知晓的对象都是垃圾。

这个算法的关键点是：从谁开始找呢？

（如果从垃圾开始找，那么那些不是垃圾的反倒视为垃圾，这是极为严重的噩梦！）

有种对象，它的价值比较大，不会被轻易抛弃，相对稳定，存在的时间较长，被称为GC Roots，是可达性分析算法的起始点。GC Roots一般只存在于栈和方法区中（具体是虚拟机栈中局部变量表内引用的对象、本地方法栈中Native方法引用的对象和方法区中静态变量和常量引用的对象），堆中不会有。

清除垃圾的强有力手段

知道谁是垃圾，下一步是启用算法将其清除。也许有人会笑，清除内存中的垃圾有什么难的，直接将它标记为废弃不就得了嘛，还在那边唧唧歪歪的整啥呀？

标记清除算法

这个算法和上面说的“直接标记为废弃”一模一样，先扫描一遍，利用可达性分析算法，将垃圾标记出来，再扫描一遍，将垃圾清除。

这个算法太简单了，简单到不是计算机专业的人也能秒懂，但它的简单也导致了极为复杂的后果：在一整段内存上，将其中的几个地方标记为废弃，会使得这条内存看起来‘坑坑洼洼’的，也就是内存碎片。碎片一多，分配内存时就不能顺利地拿到一块大内存（毕竟内存条上只有细小的碎片）。

为了解决这个碎片的问题，人们又想到了一个方法。

标记复制算法

这个算法的标记阶段和标记清除算法一样，差别在于，它不再清除无用的内存，而是将有用的内存复制到另一片空间，剩下的这片空间称为未拆封全新区域。

举个例子，对于一块1G的内存，我们将它划分为2块512M的小内存，每次我们只使用其中一块；在垃圾回收时先找出垃圾，然后将不是垃圾的对象移动到另一块内存上，并将这一块内存清空；下一次进行回收时也是同样的原理。

但这个算法也有一个缺点：任何时候都有一块内存不会被用到，也就是说，内存被浪费了。

幸好，这个缺点可以减弱到能被接受的程度。（既然每次都会浪费掉一块内存，那么，我们每次都只浪费一块非常小的内存不就行了吗？）

标记整理算法

标记出垃圾后，既不直接将其清除，也不将有效对象复制到另一块内存上，而是将有效对象复制到内存的开头，如此一来，既不会导致过多碎片，也不会浪费另一块内存。

分代收集算法

上面三个算法都仅考虑对现有垃圾的回收，未曾考虑到时间这个不可避免的因素在垃圾回收中的影响，所以现代的虚拟机都使用一种被称为“分代收集”的算法来进行实际的垃圾回收。分代收集的原理是：根据对象的已存活时长，将其划分到不同区域，在不同区域里采取不同的回收算法。

一般来说，虚拟机会将堆分为2个年代：

  • 新生代
  • 老年代

在新生代里使用了标记复制算法，所以新生代又分为3个区域：

  • 一个eden亚当区（占80%空间）：这个区里存放着大量鲜活的年轻对象，它们中只有少数会存活下来。
  • 两个survivor幸存者区（各占10%空间）：这个区里存放的对象已经有了一定年纪，它们的部分人可能有机会迁往老年代进行养老。

从0到1理解JVM内存分配机制

在JAVA中，除了在即时编译器优化后部分对象会在栈上分得足够空间，其余的对象都会在堆上“求分配空间”，所以之前我们才说，堆里存在着大大小小密密麻麻的对象。

那么在堆里，对象究竟会分到哪部分的内存，新生代还是老年代？

普通对象

答案是：对象一般会分配到新生代中Eden区的内存。

一个普通对象的极端经历

有新对象到来，而Eden又没有足够的空间时，新生代尝试进行新生代的垃圾回收（也就是Minor GC）。在尝试之前，它需要知道，如果情况特别糟糕，这次Minor GC是否安全，也就是新生代所有对象都必须移到老年代以便腾出空间存放新对象，换句话说，新生代会问老年代：“你还有连续空间可以存放我现在的崽崽们吗”，如果老年代给他个肯定，新生代就可以无忧无虑地进行Minor GC了。

如果老年代没有给出肯定答案，新生代就会再问一句：“在以往迁往你那边的对象大小里，取个平均值，你现在还有那么大的连续空间吗？”如果老年代回答yes，新生代就认为接下来的Minor GC的对象有极大的可能小于历史平均值，可以冒些风险进行MinorGC（风险是接下来的对象确实超过了历史平均值，老年代没有连续空间存放新生代来的对象，老年代需要进行老年代的回收也就是Full GC，因为新生代的冒险进行了一次失败的Minor GC，老年代需付出Full GC的代价，而后新生代再重头尝试Minor GC）。当然了，如果老年代说了不，那么新生代就得先等老年代执行了Full GC再执行新生代专属的Minor GC。

那些超大的对象

如果对象十分非常极其以及特别的巨大，那么新生代会直接请求老年代的帮助，将对象分配在老年代（老年代人太好了，新生代装不下的对象它负责装。）

一群长寿的对象

如果对象太老，也就是说在Eden区呆了一代，又在Survivor存活期呆了15代（默认是15代），那么该对象会迁往老年代，可见，JVM的世界里，一个对象的退休年龄是16。

一群稳定的幸存者

Survivor区中的对象不必等15代才能迁往老年代。如果某一年纪的对象的所占空间超过Survivor区大小的一半，它们会被赶走，赶到老年代。那种年纪的对象有这么多一起存活了这么长时间，JVM默认它们这一代的稳定性都比较好，可以提前去老年区过稳定的生活。

从0到1理解JVM运行时数据区

与操作系统类似，JVM（JAVA虚拟机）拥有自己的运行时数据区。在操作系统中，通常有代码区、数据区、堆、栈和静态区等，而JVM中的数据区则有所不同（虽然JVM号称虚拟机，是机器，但它和现实机器始终还是有差别的）。

JVM的运行时数据区类型有下面5种：

类型 属于 抛出异常类型
程序计数器 线程私有 无
虚拟机栈 线程私有 SOF、OOM
本地方法栈 线程私有 SOF、OOM
堆 公有 OOM
方法区 公有 OOM

程序计数器

程序计数器和CPU中的PC寄存器起着同样的作用：保存下一条指令的地址。不同的是，CPU中的PC寄存器是共有的，JVM中的程序计数器是线程私有的，每个线程都需要一个程序计数器来记住自己已经执行到哪儿了，线程之间轮流执行一段时间，轮到自己时，就可以借助程序计数器从正确的地方往下执行。

虚拟机栈

顾名思义，该栈属于JVM，用来保存一些必要的数据。熟悉操作系统的人都知道，在执行一个方法时，系统会将返回地址和形参等压入栈，执行过程中会从栈里获得形参，执行完方法的全部指令后再从栈中获得返回地址以便跳出方法。

虚拟机栈的原理也是一样的，在准备执行一个方法时，JVM会为该方法生成一个栈帧，将栈帧压入栈；在执行方法的过程中，JVM借用该栈帧搞一些动作；执行完方法后将该栈帧出栈。也就是说，虚拟机栈主要是服务于方法们的执行过程的，一个方法的诞生需要虚拟机栈，一个方法的死亡也需要虚拟机栈，虚拟机栈是多么的有爱和有担当。

虚拟机栈的栈帧中都有些什么玩意呢？

  • 局部变量表：这玩意可不得了，它保存了一个方法执行过程中所需要的所有局部变量！比如说，我们在一个save()方法里定义了一个int类型的temp变量，每次执行save()时，temp都会出现在局部变量表中。更不得了的是，局部变量表的大小在编译时就固定了！不过值得注意的是，该表中只存放变量，不存放对象。
  • 返回地址：也就是俗话中的“return到哪儿去”。
  • 操作数栈：熟悉计算机组成原理或编译原理的童鞋都知道，虽然现代计算机很多都是基于寄存器，但在很早以前曾有一种基于栈的机器，后来因效率问题基于栈的设计被弃用。而JVM，恰恰就是一种基于栈的设计。写过基于栈的四则计算器的同志都知道操作数栈是什么玩意。
  • 动态链接：我还不是特别明白动态链接，以后再回来补充。

因为该区基于栈结构，所以不可避免在极端情况下会出现栈溢出（SOF）；另外呢，该区的大小是可以动态扩展的，有时候机器没有多余供其扩展，供其挥霍，也就不可避免地出现内存不足（OOM）。

本地方法栈

随着时代的进步，JAVA的执行效率在逐渐地提升，JAVA已经能够做到在合适的时候“调用操作系统的本地方法，以一种C或C++的速度去执行”。那么在执行系统本地方法时，本地方法也需要栈呀，这些栈在哪里呢？不太可能复用虚拟机栈吧（虚拟机栈专门服务于JAVA语言）。应该在哪里设置个栈呢？为了解决这个问题，聪明的人类推出了本地方法栈，它是属于本地方法的栈。

堆

堆是什么呢？熟悉C语言的同学都知道，在C中动态申请一块空间需要使用malloc函数，该函数将在堆里获得空间，这里的堆和JVM中的堆其实也是差不多的。
JVM中的堆，主要用于内存的动态分配。一个对象需要内存时，主要从堆中申请到（注意我用了‘主要’，现如今有栈上分配等技术可以给对象分配内存）。简单地说，堆中充满了大大小小密密麻麻的对象。

由于对象主要都在堆里，当一个对象不再有用时，我们可以将它从堆里抹除，这种做法叫做垃圾回收，英文名叫GC。

出于现代垃圾回收器的需要，堆通常被分为新生代（内含一个EDEN区和两个Survivor区）和老生代。垃圾回收器不断地监视着堆里的众多对象，看谁不爽就把谁KO，将之扼杀于堆中。

堆存放了所有线程的对象，它顺理成章地成为公共区域。

方法区

方法区是运行时数据区中的最后一个，它存放的主要是运行时的代码。当一个类被加载时，它会从class文件里被加载到方法区中，它的类版本、字段信息、方法信息、接口信息和常量池都会被加载到方法区中。除了存放类的信息，方法区还存放常量、静态变量和代码。也就是说，方法区中的内容大部分都是不变的，除了一个叫做常量池的奇葩。

常量池里边主要是符号引用和直接引用（不明白这两个概念的可以将它们看作一条条的字符串，如“hi”，“hello”等），之所以说常量池会变化，是因为运行时产生的常量也可以加入常量池。

将JVM的运行时数据区和操作系统的运行时数据区做比较，结果如下

JVM 操作系统
程序计数器 PC寄存器
虚拟机栈、本地方法栈 栈
GC堆 ｍalloc堆
方法区 代码区

JDK源代码之LinkedList

LinkedList特性

底层数据结构

LinkedList不同于ArrayList的数组，它基于链表。

效率

LinkedList的插入删除快，遍历慢（ArrayList正好相反）

实现的接口

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了List接口、Deque双向队列接口（既可以当作FILO队列也可以当作FIFO栈）、Cloneable接口、序列化接口。
值得注意的是，LinkedList继承自AbstractSequentialList（AbstractSequentialList和ArrayList一样继承自AbstractList），也就是说，LinkedList比ArrayList更细化了一层。

细化的那层AbstractSequentialList实现了“链表”版的get/set/add/remove方法，这使得LinkedList和ArrayList有了质的差别（毕竟彼此的基因遗传都不同）。

同步机制

与ArrayList一样，LinkedList也是不同步的，可以用包装器来创造一个支持同步的List:
1
List list = Collections.synchronizedList(new LinkedList(...));

LinkedList字段

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

很明显，LinkedList用了first节点和last节点来保存整个链表（ArrayList用的是数组）。
注：transient关键字的作用是防止该字段被序列化（一些敏感的信息不能序列化然后在网络上传输）。

LinkedList方法分析

linkFirst(E e) （将一个元素插入链表头部）

1
2
3
4
5
6
7
8
9
10
11
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

先建立一个以first为后继的新节点，令first为该新节点；然后再修改第二个节点的prev变量使其指向新头部（如果没有第二个节点就修改last）

linkLast(E e)（将一个元素插入链表尾部）

机制与linkFirst(E e)相似，只需将first替换为last

linkBefore(E e, Node succ) （将一个元素插到一个节点之前）

1
2
3
4
5
6
7
8
9
10
11
12
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

该方法会判断另一个节点之前是否有节点存在，没有就修改first。

unlinkFirst(Node f)（将链表头部节点剔除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

该方法中有条垃圾回收优化的语句：

1
f.next = null; // help GC

强行令变量为null，不再引用该对象，该对象便会在下一轮的GC中被回收。
此外，该方法会判断第二个元素是否存在，没有就修改last。

unlinkLast(Node l)（将链表尾部节点剔除）

与unlinkFirst(Node<E> f)类似

JDK源代码之ArrayList

ArrayList的特性

实现的接口

ArrayList的类声明如下：

1
2
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

轻轻一撇，我们便是可以看出，ArrayList继承自抽象泛型类AbstractList<>，它实现了List接口（Collection集合的List），也拥有RandomAccess/Cloneable/Serializable三个“标注”接口。

同步机制

与Vector相比，ArrayList放弃了同步机制。如果我想要一个支持同步的ArrayList，可以使用Collections工具类中的synchronizedList方法构建一个List：

1
List list = Collections.synchronizedList(new ArrayList(...));

时间空间复杂度

ArrayList的get/size/isEmpty等方法的复杂度均为常数，add方法的复杂度为O(n)，其余的都是线性复杂度。

ArrayList字段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static final long serialVersionUID = 8683452581122892189L;

/**
 * Default initial capacity.
 * ArrayList的默认容量。插满会自动扩充。
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 保存ArrayList元素的空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 * ArrayList的实际大小（已经插入了多少数据）
 *
 * @serial
 */
private int size;

ArrayList方法分析

从上往下分析

Read More