Java知识体系之集合

Java知识体系

集合

List

特性

• ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。
• LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。
• Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
• Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。

选择

• 对于需要快速插入，删除元素，应该使用LinkedList。
• 对于需要快速随机访问元素，应该使用ArrayList。
• 对于“单线程环境” 或者 - “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
• 对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。
  　　

Vector和ArrayList比较

相同点：

• 都是List
• 都是通过数组实现的，本质上都是动态数组
• 默认数组容量是10

不同点：

• ArrayList是非线程安全； 而Vector是线程安全的，它的函数都是synchronized的，即都是支持同步的。 ArrayList适用于单线程，Vector适用于多线程。
• ArrayList支持序列化，而Vector不支持
• 容量增加方式不同

Map

特性

• HashMap 是基于“拉链法”实现的散列表。一般用于单线程程序中。
• Hashtable 也是基于“拉链法”实现的散列表。它一般用于多线程程序中。
• WeakHashMap 也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值对也会被从WeakHashMap中删除；而HashMap中的键是强键。
• TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。

HashMap与HashTable的区别

Set

HashMap

Java：手把手带你源码分析 HashMap 1.7
Java集合学习手册（1）：Java HashMap

HashMap是基于哈希表的Map接口实现类，所谓的哈希表，也称散列表，是一种根据关键字值（key - value）而直接进行访问的数据结构。它基于数组，通过把关键字映射到数组的某个下标来加快查找速度，但是又和数组、链表、树等数据结构不同，在这些数据结构中查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。

哈希函数

它把一个大范围的数字哈希（转化）成一个小范围的数字，这个小范围的数对应着数组的下标。使用哈希函数向数组插入数据后，这个数组就是哈希表。

哈希冲突

但是，把巨大的数字范围压缩到较小的数字范围，那么肯定会有几个不同的数字哈希化到同一个数组下标，即产生了冲突。
冲突的解决一般有两种方式：开放地址法(ThreadLocalMap)和链地址法

• 开放地址法
  以发生冲突的哈希地址为输入，通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。
  
  • 线性探查法：从发生冲突的地址开始，依次探查下一个地址，直到找到一个空闲单元。例如ThreadLocalMap
  • 平方探查法：设冲突地址为d0，则探查序列为：d0+1^2,d0-1^2,d0+2^2...
    冲突发生时，在表的左右进行跳跃式探测，比较灵活
• 再hash法
  这种方法是同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
• 链地址法
  将所有哈希地址相同的都链接在同一个链表中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

put

如果key为null，就放到数组的第一位，如果不为null，根据key计算hash值，然后根据这个值计算下标，然后看是否发生hash冲突，如果没有发生，就直接存储，如果有冲突，就将数组中的数据后移，然后存入到数组中

get

如果key为null，就放到数组的第一位，找到key == null的即可；其他的，计算hash，计算位置，遍历链表，先判断hash，再equals

hash()

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}

高16bit不变，低16bit和高16bit做了一个异或。hashcode之后二次处理，为了hash值更加均匀

indexFor()

static int indexFor(int h, int n) {
    return h & (n-1);
}

哈希码 与运算(&) （数组长度-1），数组长度为n的幂，所以数组长度-1就是奇数，这样最后一位为1，所以取决于hash值，可能为偶数也可能为奇数，更加均匀分布

加载因子和容量

• 加载因子过大，空间利用率高，不过冲突概率大，链表长；
• 加载因子过小，相反。
• 默认值：0.75

头插法

链表的添加方式为头插法，即 将该位置（数组上）原来的数据放在该位置的（链表）下1个节点中（next）、在该位置（数组上）放入需插入的数据-> 从而形成链表

扩容

扩容，保存旧的数组，新建新的数组，原来的两倍，遍历，重新计算hash值和位置，转移到新数组中去

Fail-Fast机制

我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

fail-fast 机制是java集合(Collection)中的一种错误机制。
当多个线程对Collection进行操作时，若其中某一个线程通过iterator去遍历集合时，该集合的内容被其他线程所改变，则会抛出ConcurrentModificationException异常，即fail-fast

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容（当然不仅仅是HashMap才会有，其他例如ArrayList也会）的修改都将增加这个值（大家可以再回头看一下其源码，在很多操作中都有modCount++这句），那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {
    expectedModCount = modCount;
    if (size > 0) { // advance to first entry
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)  
        ;
    }
}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：

final Entry<K,V> nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    ...
}

注意：modCount声明为volatile，保证线程之间修改的可见性。

迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。
fail-fast机制，是一种错误检测机制。它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。

两种遍历方式

　Map map = new HashMap();
　Iterator iter = map.entrySet().iterator();
　while (iter.hasNext()) {
    　Map.Entry entry = (Map.Entry) iter.next();
    　Object key = entry.getKey();
    　Object val = entry.getValue();
　}

Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
    Object key = iter.next();
    Object val = map.get(key);
}

第一种效率比较高，建议使用

HashMap线程不安全

特别时在扩容的时候，由于采用的是头插法来构建新链表，所以在多线程环境下，会形成环，从而导致死循环
具体参考：
Map 综述（三）：彻头彻尾理解 ConcurrentHashMap

关键代码：

do {
    Entry<K,V> next = e.next;       // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

CurrentHashMap

在ConcurrentHashMap中，无论是读操作还是写操作都能保证很高的性能：在进行读操作时(几乎)不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。
特别地，在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设为16），及任意数量线程的读操作。

ConcurrentHashMap本质上是一个Segment数组，而一个Segment实例又包含若干个桶，每个桶中都包含一条由若干个 HashEntry 对象链接起来的链表。总的来说，ConcurrentHashMap的高效并发机制是通过以下三方面来保证的：

• 通过锁分段技术保证并发环境下的写操作；
• 通过 HashEntry的不变性、Volatile变量的内存可见性和加锁重读机制保证高效、安全的读操作；
• 通过不加锁和加锁两种方案控制跨段操作的的安全性。

Segment

Segment类继承于 ReentrantLock 类，从而使得 Segment 对象能充当锁的角色。每个 Segment 对象用来守护它的成员对象 table 中包含的若干个桶。table 是一个由 HashEntry 对象组成的链表数组，table 数组的每一个数组成员就是一个桶。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile int count; 
    transient int modCount; 
    transient int threshold; 
    transient volatile HashEntry<K,V>[] table;
    final float loadFactor;
    ...
}

• count
  它是一个计数器，它表示每个 Segment 对象管理的 table 数组包含的 HashEntry 对象的个数，也就是 Segment 中包含的 HashEntry 对象的总数。这个count是volatile的
• modCount
  用于统计段结构改变的次数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变，
• threshold loadFactor
  阀值和负载因子
• HashEntry[] table;
  table是一个典型的链表数组，而且也是volatile的，这使得对table的任何更新对其它线程也都是立即可见的

ConcurrentHashMap允许多个修改(写)操作并发进行，其关键在于使用了锁分段技术，它使用了不同的锁来控制对哈希表的不同部分进行的修改(写)，而 ConcurrentHashMap 内部使用段(Segment)来表示这些不同的部分。实际上，每个段实质上就是一个小的哈希表，每个段都有自己的锁(Segment 类继承了 ReentrantLock 类)。这样，只要多个修改(写)操作发生在不同的段上，它们就可以并发进行。

HashEntry

HashEntry用来封装具体的键值对，是个典型的四元组。与HashMap中的Entry类似，HashEntry也包括同样的四个域，分别是key、hash、value和next。
不同的是，在HashEntry类中，key，hash和next域都被声明为final的，value域被volatile所修饰，因此HashEntry对象几乎是不可变的，这是ConcurrentHashmap读操作并不需要加锁的一个重要原因。
next域被声明为final本身就意味着我们不能从hash链的中间或尾部添加或删除节点，因为这需要修改next引用值，因此所有的节点的修改只能从头部开始。
对于put操作，可以一律添加到Hash链的头部。
但是对于remove操作，可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节点整个复制(重新new)一遍，最后一个节点指向要删除结点的下一个结点。
特别地，由于value域被volatile修饰，所以其可以确保被读线程读到最新的值，这是ConcurrentHashmap读操作并不需要加锁的另一个重要原因。实际上，ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。

HashEntry代表hash链中的一个节点，其结构如下所示：

static final class HashEntry<K,V> {
   final K key;                       // 声明 key 为 final 的
   final int hash;                   // 声明 hash 值为 final 的
   volatile V value;                // 声明 value 被volatile所修饰
   final HashEntry<K,V> next;      // 声明 next 为 final 的
    HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
        this.key = key;
        this.hash = hash;
        this.next = next;
        this.value = value;
    }
    @SuppressWarnings("unchecked")
    static final <K,V> HashEntry<K,V>[] newArray(int i) {
    return new HashEntry[i];
    }
}

HashMap的HashEntry：

/**
 * HashMap 中的 Entry 类
 */
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    ...
}

ConcurrentHashMap的数据结构

本质上，ConcurrentHashMap就是一个Segment数组，而一个Segment实例则是一个小的哈希表。
由于Segment类继承于ReentrantLock类，从而使得Segment对象能充当锁的角色，这样，每个 Segment对象就可以守护整个ConcurrentHashMap的若干个桶，其中每个桶是由若干个HashEntry 对象链接起来的链表。
通过使用段(Segment)将ConcurrentHashMap划分为不同的部分，ConcurrentHashMap就可以使用不同的锁来控制对哈希表的不同部分的修改，从而允许多个修改操作并发进行, 这正是ConcurrentHashMap锁分段技术的核心内涵。

put()

在ConcurrentHashMap中，典型结构性修改操作包括put、remove和clear，才需要加锁。

public V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key.hashCode());
    return segmentFor(hash).put(key, hash, value, false);
}

从上面的源码我们看到，ConcurrentHashMap不同于HashMap，它既不允许key值为null，也不允许value值为null。

还可以看到，实际上我们对ConcurrentHashMap的put操作被ConcurrentHashMap委托给特定的段来实现。
也就是说，当我们向ConcurrentHashMap中put一个Key/Value对时，首先会获得Key的哈希值并对其再次哈希，然后根据最终的hash值定位到这条记录所应该插入的段。
定位段的segmentFor()方法源码如下：

final Segment<K,V> segmentFor(int hash) {
    return segments[(hash >>> segmentShift) & segmentMask];
}

segmentFor()方法根据传入的hash值向右无符号右移segmentShift位，然后和segmentMask进行与操作就可以定位到特定的段。
在这里，假设Segment的数量(segments数组的长度)是2的n次方(Segment的数量总是2的倍数，具体见构造函数的实现)，那么segmentShift的值就是32-n(hash值的位数是32)，而segmentMask的值就是2^n-1（写成二进制的形式就是n个1）。
进一步地，我们就可以得出以下结论：

根据key的hash值的高n位就可以确定元素到底在哪一个Segment中。

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();    // 上锁
    try {
        int c = count;
        if (c++ > threshold) // ensure capacity
            rehash();
        HashEntry<K,V>[] tab = table;    // table是Volatile的
        int index = hash & (tab.length - 1);    // 定位到段中特定的桶
        HashEntry<K,V> first = tab[index];   // first指向桶中链表的表头
        HashEntry<K,V> e = first;
        // 检查该桶中是否存在相同key的结点
        while (e != null && (e.hash != hash || !key.equals(e.key)))  
            e = e.next;
        V oldValue;
        if (e != null) {        // 该桶中存在相同key的结点
            oldValue = e.value;
            if (!onlyIfAbsent)
                e.value = value;        // 更新value值
        }else {         // 该桶中不存在相同key的结点
            oldValue = null;
            ++modCount;     // 结构性修改，modCount加1
            tab[index] = new HashEntry<K,V>(key, hash, first, value);  // 创建HashEntry并将其链到表头
            count = c;      //write-volatile，count值的更新一定要放在最后一步(volatile变量)
        }
        return oldValue;    // 返回旧值(该桶中不存在相同key的结点，则返回null)
    } finally {
        unlock();      // 在finally子句中解锁
    }
}

Segment是ReentrantLock的子类，因此Segment本身就是一种可重入的Lock，所以我们可以直接调用其继承而来的lock()方法和unlock()方法对代码进行上锁/解锁。
需要注意的是，这里的加锁操作是针对某个具体的Segment，锁定的也是该Segment而不是整个ConcurrentHashMap。
因为插入键/值对操作只是在这个Segment包含的某个桶中完成，不需要锁定整个ConcurrentHashMap。
因此，其他写线程对另外15个Segment的加锁并不会因为当前线程对这个Segment的加锁而阻塞。
故而 相比较于 HashTable 和由同步包装器包装的HashMap每次只能有一个线程执行读或写操作，ConcurrentHashMap 在并发访问性能上有了质的提高。
在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设置为 16），及任意数量线程的读操作。

rehash()

在ConcurrentHashMap中使用put操作插入Key/Value对之前，首先会检查本次插入会不会导致Segment中节点数量超过阈值threshold，如果会，那么就先对Segment进行扩容和重哈希操作。
特别需要注意的是，ConcurrentHashMap的重哈希实际上是对ConcurrentHashMap的某个段的重哈希，因此ConcurrentHashMap的每个段所包含的桶位自然也就不尽相同。

扩容的容量是原来的2倍

get()

当我们从ConcurrentHashMap中查询一个指定Key的键值对时，首先会定位其应该存在的段，然后查询请求委托给这个段进行处理，源码如下：

public V get(Object key) {
    int hash = hash(key.hashCode());
    return segmentFor(hash).get(key, hash);
}

V get(Object key, int hash) {
    if (count != 0) {            // read-volatile，首先读 count 变量
        HashEntry<K,V> e = getFirst(hash);   // 获取桶中链表头结点
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) {    // 查找链中是否存在指定Key的键值对
                V v = e.value;
                if (v != null)  // 如果读到value域不为 null，直接返回
                    return v;   
                // 如果读到value域为null，说明发生了重排序，加锁后重新读取
                return readValueUnderLock(e); // recheck
            }
            e = e.next;
        }
    }
    return null;  // 如果不存在，直接返回null
}

特别的，需要注意：

在介绍put操作时，我们就知道ConcurrentHashMap不同于HashMap，它既不允许key值为null，也不允许value值为null。
但是，此处怎么会存在键值对存在且的Value值为null的情形呢？
JDK官方给出的解释是，这种情形发生的场景是：初始化HashEntry时发生的指令重排序导致的，也就是在HashEntry初始化完成之前便返回了它的引用。这时，JDK给出的解决之道就是加锁重读。

 V readValueUnderLock(HashEntry<K,V> e) {
    lock();
    try {
        return e.value;
    } finally {
        unlock();
    }
}

读操作不需要加锁的原因

HashEntry对象几乎是不可变的(只能改变Value的值)，因为HashEntry中的key、hash和next指针都是final的。
这意味着，我们不能把节点添加到链表的中间和尾部，也不能在链表的中间和尾部删除节点。
这个特性可以保证：在访问某个节点时，这个节点之后的链接不会被改变，这个特性可以大大降低处理链表时的复杂性。
与此同时，由于HashEntry类的value字段被声明是Volatile的，因此Java的内存模型就可以保证：某个写线程对value字段的写入马上就可以被后续的某个读线程看到。
此外，由于在ConcurrentHashMap中不允许用null作为键和值，所以当读线程读到某个HashEntry的value为null时，便知道产生了冲突 —— 发生了重排序现象，此时便会加锁重新读入这个value值。
这些特性互相配合，使得读线程即使在不加锁状态下，也能正确访问 ConcurrentHashMap。

• 用HashEntery对象的不变性来降低读操作对加锁的需求；
• 用Volatile变量协调读写线程间的内存可见性；
• 若读时发生指令重排序现象，则加锁重读；

用HashEntery对象的不变性来降低读操作对加锁的需求

HashEntry中的key、hash和next指针都是final的，只有value可以修改，并且value是volatile修饰的，所以当一个写线程修改了某个HashEntry的value字段后，Java内存模型能够保证读线程一定能读取到这个字段更新后的值。所以，写线程对链表的非结构性修改能够被后续不加锁的读线程看到。
对ConcurrentHashMap做结构性修改时，实质上是对某个桶指向的链表做结构性修改。如果能够确保在读线程遍历一个链表期间，写线程对这个链表所做的结构性修改不影响读线程继续正常遍历这个链表，那么读/写线程之间就可以安全并发访问这个ConcurrentHashMap。
在ConcurrentHashMap中，结构性修改操作包括put操作、remove操作和clear操作，下面我们分别分析这三个操作：

• clear操作只是把ConcurrentHashMap中所有的桶置空，每个桶之前引用的链表依然存在，只是桶不再引用这些链表而已，而链表本身的结构并没有发生任何修改。因此，正在遍历某个链表的读线程依然可以正常执行对该链表的遍历。

• put操作如果需要插入一个新节点到链表中时会在链表头部插入这个新节点，此时链表中的原有节点的链接并没有被修改。也就是说，插入新的健/值对到链表中的操作不会影响读线程正常遍历这个链表。

• remove操作根据散列码找到具体的链表，然后遍历这个链表找到要删除的节点，最后把待删除节点之后的所有节点原样保留在新链表中，把待删除节点之前的每个节点克隆到新链表中。
  下图时删除c的效果：
  
  所以在执行remove操作时，原始链表并没有被修改，只是又出现了一条新的链表，也就是说，读线程不会受同时执行 remove 操作的并发写线程的干扰。

用Volatile变量协调读写线程间的内存可见性

在ConcurrentHashMap中，所有执行写操作的方法（put、remove和clear）在对链表做结构性修改之后，在退出写方法前都会去写这个count变量；
所有未加锁的读操作（get、contains和containsKey）在读方法中，都会首先去读取这个count变量。根据 Java 内存模型，对同一个 volatile 变量的写/读操作可以确保：写线程写入的值，能够被之后未加锁的读线程“看到”

跨段操作

在ConcurrentHashMap中，有些操作需要涉及到多个段，比如说size操作、containsValaue操作等。
以size操作为例，如果我们要统计整个ConcurrentHashMap里元素的大小，那么就必须统计所有Segment里元素的大小后求和。
我们知道，Segment里的全局变量count是一个volatile变量，那么在多线程场景下，我们是不是直接把所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢？
显然不能，虽然相加时可以获取每个Segment的count的最新值，但是拿到之后可能累加前使用的count发生了变化，那么统计结果就不准了。

public int size() {
    final Segment<K,V>[] segments = this.segments;
    long sum = 0;
    long check = 0;
    int[] mc = new int[segments.length];
    // Try a few times to get accurate count. On failure due to
    // continuous async changes in table, resort to locking.
    for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
        check = 0;
        sum = 0;
        int mcsum = 0;
        for (int i = 0; i < segments.length; ++i) {
            sum += segments[i].count;   
            mcsum += mc[i] = segments[i].modCount;  // 在统计size时记录modCount
        }
        if (mcsum != 0) {
            for (int i = 0; i < segments.length; ++i) {
                check += segments[i].count;
                if (mc[i] != segments[i].modCount) {  // 统计size后比较各段的modCount是否发生变化
                    check = -1; // force retry
                    break;
                }
            }
        }
        if (check == sum)// 如果统计size前后各段的modCount没变，且两次得到的总数一致，直接返回
            break;
    }
    if (check != sum) { // Resort to locking all segments  // 加锁统计
        sum = 0;
        for (int i = 0; i < segments.length; ++i)
            segments[i].lock();
        for (int i = 0; i < segments.length; ++i)
            sum += segments[i].count;
        for (int i = 0; i < segments.length; ++i)
            segments[i].unlock();
    }
    if (sum > Integer.MAX_VALUE)
        return Integer.MAX_VALUE;
    else
        return (int)sum;
}

size方法主要思路：

• 先在没有锁的情况下对所有段大小求和，这种求和策略最多执行RETRIES_BEFORE_LOCK次(默认是两次)：
• 在没有达到RETRIES_BEFORE_LOCK之前，求和操作会不断尝试执行（这是因为遍历过程中可能有其它线程正在对已经遍历过的段进行结构性更新）；
• 在超过RETRIES_BEFORE_LOCK之后，如果还不成功，则再采用加锁的方式来统计所有Segment的大小。所谓加锁就是，for循环持有所有段锁。
• Segment包含一个modCount成员变量，在会引起段发生结构性改变的所有操作(put操作、 remove操作和clean操作)里，都会将变量modCount进行加1，因此，JDK只需要在统计size前后比较modCount是否发生变化就可以得知容器的大小是否发生变化。

SparseArray

Android常见优化方式-SparseArray
Android中的HashMap,ArrayMap和SparseArray

SparseArray 第一个数组里面，存的是int，第二数组里面存的是Value，index下标是一致的
所以查找的时候，先去第一个数组里面，找到index，然后直接去第二个数组获取value
第一步是 O(lgn) 第二步是O(1)

优点：

• 没有缝隙，减少了封箱操作，没有hash操作，内存占用更少

缺点：

• 在插入数据时也涉及到了排序操作，当数据量比较大的时候可能会效率低，故不适合做大量数据的操作
• 该类的key只能是int型的，在有些地方限制了其使用。

为什么不用一个数组？

用了两个数组来分别保存key和value值，为什么这样做呢？猛地一看，这样做缺点很明显：

• 首先，需要分两次访问数组才能完成数据的读写操作，一次是访问Keys数组，另一次访问Values数组。
• 其次是数据被分散了，这样在CPU读取数据时，需要先后两次刷新到它的数据高速缓存Cache，第一次是keys数组，找到key值后，再去values数组中获取对应的value值时，需要再次刷新Cache。

那么，如果把它们放在一起组成kv键值对，作为一个整体，保存在同一个数组中，CPU在装载数组数据到Cache的时候，可以同时把KV键值对一起加载到Cache，岂不更省事？

class KvEntry {
    int key;
    Object value;
}

我们来对比这两种情况：

• 查找次数
  
  • 两个数组：先根据key值在keys数组中进行查找，经过平均lnN次后，找到了key所在的数组下标索引，然后使用该索引从values数组中取得value值。显然，第二次数组访问操作的复杂度为O(1)，也就是说，虽然分别访问了两个数组，但是访问第二个数组仅仅是使用索引下标读了一次数组，开销很低，也还说得过去
  • 一个数组：保存在entries里面的都是KvEntry的对象引用，根据key值使用二分法查找entries时，先得到一个KvEntry数据项，从中得到它的key值进行比较，经过平均lnN次后，得到key值相等的KvEntry数据项，直接从中返回value对象即可。
• CPU访问内存的开销

CPU运算速度要比内存读写速度快很多，这样会使CPU花费很长时间等待数据到来或把数据写入内存，为了解决CPU运算速度与内存读写速度不匹配的矛盾，为CPU设计了高速缓存Cache，当CPU调用大量数据时，就可先缓存中调用，从而加快读取速度。

分析一下在两种情况下是如何把数据装载到Cache的。

• 在分为两个数组时，keys数组保存的是int型，CPU把它们加载到Cache后，可以直接使用它们进行比较操作。
• 而当使用一个数组保存KV键值对时，由于保存的是对象引用，因此CPU把它们从内存加载到Cache后，得到的是KvEntry对象引用，也就是KvEntry对象在内存中的地址。因此，在进行比较时，需要再次从内存中加载KvEntry对象到Cache中，注意此时有可能要覆盖会掉上次刚刚加载到Cache中的entries数组中的数据，也就是说，CPU每一次对KvEntry进行比较，就得从内存中加载一次数据到Cache中去，有时候甚至加载两次。

由于数据在一个数组和分成两个数组的查找次数是一样多，二者的性能上区别取决于数据从内存加载到Cache的性能和次数了。

从网上查找了相关数据，可以看到CPU访问一次L1 Cache开销时间是0.5纳秒，而访问一次内存时间开销是100纳秒，二者差距了200倍，CPU进行分支预测时间开销是5纳秒，也远远小于100纳秒。可见，性能瓶颈点不是比较次数的多少，而是访问内存次数的多少，访问内存的次数越多，性能越慢。尽管也有lnN次的比较运算的时间开销，相比内存访问的时间开销反而微不足道。

因此，分为两个数组时，虽然比使用一个数组时多了一次访问values数组的开销，但是仍然比使用一个数组速度要快的多。

SpareArray使用了两个数组来保存key和value，根本原因就是访问key和value的次数不一样，而且key数据能够形成“密集型”数据。因此，让次数多的分离出来，这样，加载它到CPU的高速缓存Cache中时，能够一次加载更多的数据，在查找时，可以比较更多的数据，从而节省了时间。

ArrayMap也正是遵循这样的原则进行设计的，因为ArrayMap的key值得类型是对象型的，不是int或者long型，因此，为了让key成为密集型的数据，就在keys数组中保存key对象的hashCode，因为hashCode是int型。
同样数据库在设计索引时采用的B树数据结构，也是基于这样的考虑，由于磁盘的一次读写比访问内存开销要大得多，那就使用B树减少访问硬盘的次数，增加读取磁盘时的数据量来提高性能。

ArrayMap

深入剖析 Android中的 ArrayMap
深度解读ArrayMap优势与缺陷

阻塞队列BlockingQueue

并发编程4：Java 阻塞队列源码分析（上）

LinkedHashMap & LruCache

LruCache原理和用法与LinkedHashMap

CopyOnWriteArrayList

并发编程6：CopyOnWriteArrayList 的写时复制

关于两个CopyOnWrite容器，其实CopyOnWriteArraySet是通过包装了CopyOnWriteArrayList来实现的，所以在学习时，我们可以专注于理解一种。

首先，CopyOnWrite到底是什么意思呢？它的原理是，任何修改操作，如add、set、remove，都会拷贝原数组，修改后替换原来的数组，通过这种防御性的方式，实现另类的线程安全。请看下面的代码片段，我进行注释的地方，可以清晰地理解其逻辑。

public boolean add(E e) {
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
           // 拷贝
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
           // 替换
        setArray(newElements);
        return true;
    }
}
final void setArray(Object[] a) {
    array = a;
}

所以这种数据结构，相对比较适合读多写少的操作，不然修改的开销还是非常明显的。

参考

集合

java提高篇
Java集合学习手册（10）：hashCode方法与equal方法
Java集合学习手册（9）：Java 集合对比
面试/笔试第五弹 —— Java面试问题集锦（下篇） 中的集合部分
Java 集合系列目录(Category)

HashMap

Java：手把手带你源码分析 HashMap 1.7
Java集合学习手册（1）：Java HashMap 主要看6.5 Fail-Fast机制和6.6 两种遍历方式
Java源码分析：关于 HashMap 1.8 的重大更新
开放地址法
HashMap，ArrayMap，SparseArray源码分析及性能对比

ArrayList

Java集合学习手册（6）：Java ArrayList

ConcurrentHashMap

Map 综述（三）：彻头彻尾理解 ConcurrentHashMap