Tanks to CS-Notes。

Java容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

Collection

Collection存储着对象的集合。

Collection整体架构

Collection接口继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

List

ArrayList

可变长动态数组，支持随机访问，是不安全的。

Collections.synchronizedList(); //得到一个线程安全的 ArrayList。

ArrayList实现了List 和RandomAccess接口，可以随机访问。

添加元素

它在add()时，会首先进行扩容校验，然后将数据插入到尾部，并使size+1。它的add(index,e)时，也会进行扩容校验，然后复制数组(操作代价高)，将index位置插入数据，并将后面的数据向后移动。

其默认大小是10，每次扩容为旧容量的1.5倍。oldCapacity+(oldCapacity>>1)=oldCapacity+oldCapacity/2。

由此可见 ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。

删除元素

同样在delete(index)时，我们需要将indx+1后面的元素都往前复制，删除代价也是很高的。

序列化

由于ArrayList是基于动态数组实现的，并不是所有的空间都被使用。因此需要防止被自动序列化。从而ArrayList 自定义了序列化与反序列化，只序列化了使用的要素。

transient Object[] elementData;

Vector

与ArrayList使用一致，是可变长数组但是是线程安全的同步容器。在添加元素的时候使用synchronized进行同步写数据。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

Stack

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。

堆栈只定义了默认构造函数，用来创建一个空栈。堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

LinkedList

双向链表实现的List，它的插入和删除更加有效，只是移动指针。

在查询时，需要遍历查询，效率较低。当index离链表头较近，就从节点头部遍历，否则就从尾部开始遍历。使用空间(双向链表)来换取时间

同样在删除的时候，可以直接删除指针即可。

LinkedList

可以用它来实现双向队列。

Set

HashSet

HashSet的底层使用了HashMap来保存元素。支持快速查找，但是不支持有序操作。不允许存储重复元素，当重复时，进行覆盖。

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

比较关键的就是这个 add() 方法。可以看出它是将存放的对象当做了 HashMap 的健，value 都是相同的 PRESENT 。由于 HashMap 的 key 是不能重复的，所以每当有重复的值写入到 HashSet 时，value 会被覆盖，但 key 不会受到影响，这样就保证了 HashSet 中只能存放不重复的元素。

LikedHashSet

具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序

TreeSet

基于红黑树实现，支持有序性操作(不能存入null值)，例如根据一个范围查找元素的操作。但是查找效率O(logN)不如HashSet的O(1)。当需要排序的功能时，我们才使用TreeSet，而不考虑HashSet

Collection的sort方法使用的排序算法

Collection.sort在内部也是转换为了Arrays.sort

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Arrays.sort具体采用的排序算法如下：基本类型 DualPivotQuicksort 双轴快速排序

对象数组 LegacyMergeSort 归并排序在后续的版本中会被删除
当count<7 使用Insertion sort(先获得一定长度的序列，然后再合并，在效率上将有所提高。) 当count>=7 mergeSort ComparableTimSort(调用时无Comparator)/TimSort(调用时传递了Comparator) 当count<32 使用二分插入排序(binary sort) 当count>=32 调用TimSort(调用时传递了Comparator)

通过判断排序的对象的数目，在排序算法的内部，进行优化，提高了效率。但是为什么对于基本类型和对象数组，我们还是考虑了不同的排序算法呢？

这是考虑了排序算法的稳定性！！！！对于基础类型，相同值是没有差别的，排序的先后相同值的相对位置是并不重要的，所以采取了更为高效的快速排序，尽管它是不稳定的排序算法；对于非基础类型，排序前后相等的实例的相对位置不宜改变，所以采取稳定的归并排序或者ComparableTimSort

Map

Map存储着键值对的映射表。

Map整体架构

HashMap

HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

Hashmap 不是同步的，如果多个线程同时访问一个 HashMap，而其中至少一个线程从结构上（指添加或者删除一个或多个映射关系的任何操作）修改了，则必须保持外部同步，以防止对映射进行意外的非同步访问。

HahMap就是数组和链表的结合体。

注意遍历使用entry效率高

HashMap

HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");

新建一个 HashMap，默认大小为 16；
插入 <K1,V1> 键值对，先计算 K1 的 hashCode ，所在的桶下标1(假设)，插入
插入 <K2,V2> 键值对，先计算 K2 的 hashCode ，所在的桶下标2(假设)，插入
插入 <K3,V3> 键值对，先计算 K3 的 hashCode ，所在的桶下标2(假设)，插在 <K2,V2> 前面。

这里应该注意到两点

hashcode的计算，通过key的hashCode经过扰动函数处理后得到hash值。

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

链表的插入是以头插法方式进行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在链表头部。
当链表长度大于8时，需要将链表转换为红黑树。

查找需要分成两步进行：

计算键值对所在的桶；
在链表上顺序查找，时间复杂度显然和链表的长度成正比。

hash冲突：拉链法

我们先来看看HashMap put时的情形

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    //获取key的hashCode(),
    //获取hashCode()16个高位 进行异或操作
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put方法的实现是根据key的hashCode进行hash运算，得到值hash；根据hash值去确定数组的位置，index=hash& (table.length.-1)（效率高） length是2的次方

说明：

  x % 2的n次方= x & (2的n次方-1);
  HashMap的数组长度，总是2的n次方
  因此 位桶的位置 index= hash & (length -1) //等价于 hash % length，采用位运算效率高

Java中每个位桶都是采用的链表+红黑树来实现的。

HashMap 在我们明白HashMap是如何进行put之后，我们来讨论什么是哈希冲突？其实就是再采用哈希函数对输入域进行映射到哈希表的时候，因为哈希表的位桶的数目远小于输入域的关键字的个数，所以，对于输入域的关键字来说，很可能会产生这样一种情况，也就是，不同关键字会映射到同一个位桶中的情况。 Java中是使用拉链式来解决冲突的，

 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是否为空或者length等于0, 如果是则调用resize方法进行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 通过hash值计算索引位置, 如果table表该索引位置节点为空则新增一个
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else { // table表该索引位置不为空
            Node<K,V> e; K k;
            if (p.hash == hash &&// 判断p节点的hash值和key值是否跟传入的hash值和key值相等
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;// 如果相等, 则p节点即为要查找的目标节点，赋值给e
            else if (p instanceof TreeNode) //添加红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// 走到这代表p节点为普通链表节点
                for (int binCount = 0; ; ++binCount) {// 遍历此链表, binCount用于统计节点数
                    if ((e = p.next) == null) {// p.next为空代表不存在目标节点则新增一个节点插入链表尾部
                        p.next = newNode(hash, key, value, null);

                         // 计算节点是否超过 TREEIFY_THRESHOLD（8）个, 减一是因为循环是从p节点的下一个节点开始的
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);// 如果超过8个，调用treeifyBin方法将该链表转换为红黑树
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e; // 将p指向下一个节点
                }
            }
            // e不为空则代表根据传入的hash值和key值查找到了节点,将该节点的value覆盖,返回oldValue
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);// 用于LinkedHashMap
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)  // 插入节点后超过阈值则进行扩容
            resize();
        afterNodeInsertion(evict);  // 用于LinkedHashMap
        return null;
    }

并发访问HashMap的问题

1.体现在容量大于总量 initialCapacity*负载因子 loadFactor发生扩容时会出现环形链表从而导致死循环。由于hashmap非线程安全，扩容时如果多线程并发进行操作，则可能有两个线程分别操作新表和旧表，导致节点成环，查询时会形成死锁。在JAVA8之后，优化了不会再出现此问题循环链表，执行get操作，死循环

2.并发put，有可能造成键值对的丢失，如果两个线程同时读取到当前node，在链表尾部插入，先插入的线程是无效的，会被后面的线程覆盖掉

HashMap扩容问题

HashMap具有扩容机制，当HashMap中元素的个数(size)超过临界值(threshold)时，会发生自动扩容。

threshold=loadFactory*capacity loadFactory默认值是0.75。

所以，如果我们没有设置初始容量大小(initialCapacity)，随着元素的不断增加，HashMap会发生多次扩容，而HashMap中的扩容机制决定了每次扩容都需要重建hash表，是非常影响性能的。

Map<String, String> map = new HashMap<String, String>(1);//实际大小为2

上述代码虽然设置了初始容量为1，但是HashMap内部会处理采用第一个大于该数值的2的幂作为初始化容量。

这里为什么是2的幂？

实现散列得更均匀。2^n 散列均匀
位运算的效率比取余的效率高。数组的大小是n，在put一个结点时，我们需要找到数组对应的下表，其下标 i= hash % n 当 n为2的幂我们可以使用 hash & (n-1) 替换。

当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。那么，是不是我们只需要把已知的HashMap中即将存放的元素个数直接传给initialCapacity就可以了呢？

关于这个值《阿里巴巴开发手册》有这么一个建议： initialCapacity=(需要存储的个数/loadFactory)+1 如果无法确定大小，请设置为默认值16。

假如我们要存储7个数据，如果我们设置初始大小为7的话，经过JDK自己的运算后，会设置为8.那么threshold=loadFactory*capacity=0.75*8=6，此时7>6 会发生扩容。如果我们考虑loadFactory使用公式，设置初始大小为10，经过JDK自己的运算后，会设置为16,threshold=loadFactory*capacity=0.75*16=12此时不会发生扩容。

以上的操作是一种用内存换性能的做法，真正使用的时候，要考虑到内存的影响。

LinkedHashMap

具有顺序(双向链表)的HashMap，这里顺序可是设置为插入顺序(accessOrder为false，默认)，也可以设置为访问顺序(accessOrder为true)。

当根据访问顺序排序的时候，每次get都会将访问的值移动到链表的尾部，这样重复操作就能得到一个按照访问顺序排序的链表。

LRU

LRU 缓存利用了这样的一种思想。LRU 是 Least Recently Used 的缩写，翻译过来就是“最近最少使用”，也就是说，LRU 缓存把最近最少使用的数据移除，让给最新读取的数据。而往往最常读取的，也是读取次数最多的，所以，利用 LRU 缓存，我们能够提高系统的 performance。

结合LinkedHashMap其访问顺序的排序特点，实现LRU缓存。

用这个类有两大好处：一是它本身已经实现了按照访问顺序的存储，也就是说，最近读取的会放在最前面，最最不常读取的会放在最后（当然，它也可以实现按照插入顺序存储）。第二，LinkedHashMap 本身有一个方法用于判断是否需要移除最不常读取的数，但是，原始方法默认不需要移除（这里，LinkedHashMap 相当于一个linkedlist），所以，我们需要 override 这样一个方法，使得当缓存里存放的数据个数超过规定个数后，就把最不常用的移除掉。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int MAX_ENTRIES = 3;
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);//true开启访问顺序排序
    }

    LRUCache(int cacheSize) {
        super(MAX_ENTRIES, 0.75f, true);//true开启访问顺序排序
        MAX_ENTRIES=cacheSize;
    }
}

HashTable(基本淘汰)

和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。

TreeMap

基于红黑树实现,排好序的Map,

WeakHashMap

WeakHashMap 的 Entry 继承自 WeakReference，被 WeakReference 关联的对象在下一次垃圾回收时会被回收。

WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>

Tomcat的ConcurrentCache

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能。

ConcurrentCache 采取的是分代缓存：

经常使用的对象放入 eden 中，eden 使用 ConcurrentHashMap 实现，不用担心会被回收（伊甸园）；
不常用的对象放入 longterm，longterm 使用 WeakHashMap 实现，这些老对象会被垃圾收集器回收。
当调用 get() 方法时，会先从 eden 区获取，如果没有找到的话再到 longterm 获取，当从 longterm 获取到就把对象放入 eden 中，从而保证经常被访问的节点不容易被回收。
当调用 put() 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象。

Queue

阻塞队列

当然，为了解决队列的阻塞问题，我们引入了阻塞队列。它会对当前线程产生阻塞，比如一个线程从一个空的阻塞队列中取元素，此时线程会被阻塞直到阻塞队列中有了元素。当队列中有元素后，被阻塞的线程会自动被唤醒（不需要我们编写代码去唤醒，这是非阻塞队列需要实现的同步以及线程唤醒的问题）。这样提供了极大的方便性。

ArrayBlockingQueue

基于数组实现的一个阻塞队列，在创建ArrayBlockingQueue对象时必须制定容量大小。并且可以指定公平性与非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。

ArrayBlockingQueue一旦创建，容量不能改变。其并发控制采用可重入锁来控制，不管是插入操作还是读取操作，都需要获取到锁才能进行操作。当队列容量满时，尝试将元素放入队列将导致操作阻塞;尝试从一个空队列中取一个元素也会同样阻塞。

LinkedBlockingQueue

基于链表实现的一个阻塞队列，在创建LinkedBlockingQueue对象时如果不指定容量大小，则默认大小为Integer.MAX_VALUE。底层基于单向链表实现的阻塞队列，可以当做无界队列也可以当做有界队列来使用，同样满足FIFO的特性，与ArrayBlockingQueue 相比起来具有更高的吞吐量，为了防止 LinkedBlockingQueue 容量迅速增，损耗大量内存。通常在创建LinkedBlockingQueue 对象时，会指定其大小，如果未指定，容量等于Integer.MAX_VALUE。

PriorityBlockingQueue

优先队列（本质是堆实现的），队列中的元素是有优先级的，优先级最高的元素就排在队列的第一位，当我们从队列中去取的是，得到的是优先级最高的那个元素。这个优先级我们是可以自己定义的，比如值最大的，优先级最高，也可以定义成值最小的，优先级最高，甚至可以指定比较某个具体的对象的某个属性，比如学生的学号，年龄这种的。以上2种队列都是先进先出队列，而PriorityBlockingQueue却不是，它会按照元素的优先级对元素进行排序，按照优先级顺序出队，每次出队的元素都是优先级最高的元素。注意，此阻塞队列为无界阻塞队列，即容量没有上限（通过源码就可以知道，它没有容器满的信号标志），前面2种都是有界队列。

PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序进行排序，也可以通过自定义类实现 compareTo() 方法来指定元素排序规则，或者初始化时通过构造器参数 Comparator 来指定排序规则。

PriorityBlockingQueue 并发控制采用的是 ReentrantLock，队列为无界队列（ArrayBlockingQueue 是有界队列，LinkedBlockingQueue 也可以通过在构造函数中传入 capacity 指定队列最大的容量，但是 PriorityBlockingQueue 只能指定初始的队列大小，后面插入元素的时候，如果空间不够的话会自动扩容）

简单地说，它就是 PriorityQueue 的线程安全版本。不可以插入 null 值，同时，插入队列的对象必须是可比较大小的（comparable），否则报 ClassCastException 异常。它的插入操作 put 方法不会 block，因为它是无界队列（take 方法在队列为空的时候会阻塞）。

DelayQueue

基于PriorityQueue，一种延时阻塞队列，DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。DelayQueue也是一个无界队列，因此往队列中插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。

ConcurrentLinkedQueue

ConcurrentLinkedQueue 主要使用 CAS 非阻塞算法来实现线程安全。适合在对性能要求相对较高，同时对队列的读写存在多个线程同时进行的场景。

BlockingQueue

阻塞队列（BlockingQueue）被广泛使用在“生产者-消费者”问题中，其原因是BlockingQueue提供了可阻塞的插入和移除的方法。当队列容器已满，生产者线程会被阻塞，直到队列未满；当队列容器为空时，消费者线程会被阻塞，直至队列非空时为止。

线程安全的容器

对于非线程安全的容器，比如ArrayList、LinkedList、HashMap，当出现多线程并发访问时，会出现问题。因此在编写程序时，必须要求程序员手动地在任何访问到这些容器的地方进行同步处理，这样导致在使用这些容器的时候非常地不方便。

由此java提供了一系列的同步容器（使用了synchronized进行同步，只有一把锁，读写操作存在竞争问题，效率损失）：

Vector、Stack、HashTable
Collections类中提供的静态工厂方法创建的类

针对同步容器的性能较低的问题，java又提供了并发容器，在java.util.concurrent目录下。在了解并发容器之前，我们需要了解CAS

CAS

CAS是一种无锁的非阻塞算法。Compare and swap

其实现思想很简单：三个参数，存当前内存值V，旧的预期值A，即将更新的值B。当且仅当，A和V一致时，将内存值修改为B，并返回true，否则说明对象已被其他线程修改，什么都不做，并返回false。

java.util.concurrent(J.U.C)

ConcurrentHashMap

实现了HashTable的所有功能，线程安全，但却在检索元素时不需要锁定，因此效率更高。但是key，value不能允许null值出现。

ConcurrentHashMap 是一个并发散列映射表的实现，它允许完全并发的读取，并且支持给定数量的并发更新。

相比于 HashTable 和同步包装器包装的 HashMap，使用一个全局的锁来同步不同线程间的并发访问，同一时间点，只能有一个线程持有锁，也就是说在同一时间点，只能有一个线程能访问容器，这虽然保证多线程间的安全并发访问，但同时也导致对容器的访问变成串行化的了。

注意当链表长度大于8时，需要将链表转为红黑树

为synchronized+CAS来进行加锁，在 CAS 操作失败时使用内置锁 synchronized。

总的说来，在ConcurrentHashMap中，无论是读操作还是写操作都能保证很高的性能：在进行读操作时(几乎)不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。

ConcurrentLinkedQueue

CopyOnWriteArrayList

安全的ArrayList。

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。写操作需要加锁，防止并发写入时导致写入数据丢失。写操作结束之后需要把原始数组指向新的复制数组。

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景

提供高效地读取操作，使用在读多写少的场景。CopyOnWriteArrayList读取操作不用加锁，且是安全的；写操作时，先copy一份原有数据数组，再对复制数据进行写入操作，最后将复制数据替换原有数据，从而保证写操作不影响读操作。存在内存占用问题，并且只能保证最终一致性，不能保证实时一致性

CopyOnWriteArrayList是多线程安全的容器，遵循了fail-save的准则，因此我们可以在foreach的遍历中，去remove和add元素。但是注意其中的迭代器是不能访问修改后的内容的,它指向原始的容器。迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

public static void main(String[] args) {
    List<String> userNames = new CopyOnWriteArrayList<String>() ;

    Iterator it = userNames.iterator();

    for (String userName : userNames) {
        if (userName.equals("Hollis")) {
            userNames.remove(userName);
        }
    }

    System.out.println(userNames); //  [hollis, HollisChuang, H]

    while(it.hasNext()){
        System.out.println(it.next());
        //Hollis
        //hollis
        //HollisChuang
        //H
    }
}

ConcurrentSkipListMap

ConcurrentSkipListMap的实现就是实现了一个无锁版的跳表，主要是利用无锁的链表的实现来管理跳表底层，同样利用CAS来完成替换

线程安全的跳表。我们这里先解释一下跳表的含义。

对于一链表，及时他是有序的，我们仍然需要顺序遍历链表来查找某个数据。跳表就不一样了，跳表是一种可以用来快速查找的数据结构，有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，你会需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，你只需要部分锁即可。这样，在高并发环境下，你就可以拥有更好的性能。而就查询的性能而言，跳表的时间复杂度也是 O(logn) 所以在并发数据结构中，JDK 使用跳表来实现一个 Map。

跳表的本质是维护了多个链表，并且链表是有层级关系。最低层的链表维护了跳表内所有的元素，每一级上层链表都是下级链表的子集。注意跳表本身是有序的，因此在查找时，我们首先从高级链表查询，一旦被查找的元素的值大于当前链表的值，就到下一层链表查询。下图是在表中查找18的过程。

跳表是一种典型的空间换取时间的算法

Arrays.asList()

利用asList(),我们可以很容易地将数组转换为集合。

Integer [] str=new Integer [] { 1,2,3,4,5,6,7}
List<Integer> list = Arrays.asList(str);
list.add(8) //UnsupportedOperationException异常

注意Arrays.asList()将数组转为集合后，其底层仍然是数组，(使用的是适配器模式，为数组添加了List的方法而已)，所以你不能使用集合的修改方法。

另外， str[0]=10,则list.get(0)=10，会随之改变。

那么如果正确的转换呢？结合ArrayList的构造函数。

List list = new ArrayList<>(Arrays.asList(“a”, “b”, “c”))

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

List.subList

subList截取List的一部分，返回的是List的内部类SubList(ArrayList$SubList),只是ArrayList的一个视图

对于SubList的所有操作都会最终反映到原列表上。对sourceList的非结构化操作，在subList中也会得到反应。

注意，我们在结构性的改sourceList时，会报错ConcurrentModificationException。这里是由fail-fast导致的。

那么我们如果修改subList，而不想动原List呢？进行拷贝：

Integer [] str=new Integer [] { 1,2,3,4,5,6,7};
List<Integer> list = Arrays.asList(str);
List<Integer> sublist = list.subList(0, 2);//本质是内部类
sublist=sublist.stream().skip(strart).limit(end).collect(Collectors.toList());

集合的foreach遍历

只要想使用foreach循环遍历集合时，必须正确地实现Iterable接口，以此进行集合的遍历。

foreach经过编译-反编译，我们会发现其实是依赖了while和Iterator实现的。

int a[]={1,2,3,4,5,6,7,8};
for (var i : a) {
    System.out.println(i);
}

List<String> b=new ArrayList<>();//List实现了Iterable接口
b.add("1");
b.add("2");
for (var s : b) {
    System.out.println(s);
}

forEach() 与foreach是不同的，forEach()是通过函数式接口 Consumer实现的可以使用lambda表达式

注意我们在foreach 集合时，是不能 删除/添加/修改 集合内容，“只读”操作。

因为编译时，会利用Iterator来实现遍历，Iterator是工作在一个独立的线程中的，拥有一个mutex锁， Iterator被创建之后会建立一个指向原来对象的单链索引表，当原来的对象数量发生变化时，这个索引表的内容不会同步改变，所以当索引指针往后移动的时候就找不到要迭代的对象，因此你是不能修改迭代对象的。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

其中modCount表示该集合实际被修改的次数。 expectedModCount表示该集合预期被修改的次数，其随着Iterator被创建而初始化，只有通过迭代器对集合进行操作，该值才会变化。

以foreach为列子，在循环时，集合调用了Iterator，其让expoectedModCount初始化成功，但是集合本身的remove、add方法，并不是利用Iterator进行变化，它只是使用了集合自己的方法，导致modCount变化，而expoectedModCount未变化，因此抛出了异常。

我们可以使用Iterator本身的方法来remove()来删除对象，Iterator.remove() 方法会在删除当前迭代对象的同时维护索引的一致性。

当然我们也可以直接使用for循环，或者使用多线程并发容器(fail-save，就是指容器遍历并不是在原始容器内容上进行访问，而是先复制原有的集合内容，在拷贝的集合上进行遍历)，

当多个线程对部分集合进行结构上的改变的操作时，有可能会产生fail-fast机制，这个时候就会抛出ConcurrentModificationException。(并发修改产生的异常)

fail-fast机制

在系统设计中，快速失效系统一种可以立即报告任何可能表明故障的情况的系统。快速失效系统通常设计用于停止正常操作，而不是试图继续可能存在缺陷的过程。这种设计通常会在操作中的多个点检查系统的状态，因此可以及早检测到任何故障。快速失败模块的职责是检测错误，然后让系统的下一个最高级别处理错误。

fail-fast就是在做系统设计的时候，优点考虑异常情况，一旦发生异常，直接停止上报由上级进行出合理。

public int divide(int divisor,int dividend){
    if(dividend == 0){
        throw new RuntimeException("dividend can't be null");
    }
    return divisor/dividend;
}

上面的除法，也是fail-fast理念的实际应用。这样做的好处就是可以预先识别出一些错误情况，一方面可以避免执行复杂的其他代码，另外一方面，这种异常情况被识别之后也可以针对性的做一些单独处理。

java集合的fail-fast机制

我们通常说的Java中的fail-fast机制，默认指的是Java集合的一种错误检测机制，防止在对集合进行遍历过程当中，出现意料之外的修改。

实现方式：

当前线程会维护一个计数比较器，即 expectedModCount，记录已经修改的次数。在进入遍历时，会把实时修改次数 modCount赋值给 expectedModCount，如果这两个数据不相等，则抛出异常。

java.util下的集合类都是属于fail-fast的，而相对应的，j.u.c下的集合类都是fail-safe，

需要注意，即使不是多线程，如果单线程违反了规则，也会抛出异常。比如ArraList.subList()场景、foreach对集合进行修改。

fail-safe机制

与 fail-fast 相对应的，就是 fail-safe 机制。fail-safe 指的是：

在安全的副本（或者没有提供修改操作的正本）上进行遍历，集合修改和副本的遍历是没有任何关系的，但是缺点也很明显，就是读取不到最新的数据。

在J.U.C包中集合都是有这种机制实现的。

java的copy-on-write

Copy-on-write 是解决并发的的一种思路，也是指的是实行读写分离，如果执行的是写操作，则复制一个新集合，在新集合内添加或者删除元素。待一切修改完成之后，再将原集合的引用指向新的集合。

这样的好处就是，可以高并发地对COW进行读和遍历操作，而不需要加锁。因为当前集合不会添加任何元素。

Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

CopyOnWriteArrayList中add/remove等写方法是需要加锁的，目的是为了避免Copy出N个副本出来，导致并发写。

CopyOnWriteArrayList的读方法是没有加锁的。可以对CopyOnWrite容器进行并发的读，当然，这里读到的数据可能不是最新的。因为写时复制的思想是通过延时更新的策略来实现数据的最终一致性的，并非强一致性。

所以CopyOnWrite容器是一种读写分离的思想，读和写不同的容器。而Vector在读写的时候使用同一个容器，读写互斥，同时只能做一件事儿。

By the way，关于写时复制（copy-on-write）的这种思想，这种机制，并不是始于Java集合之中，在Linux、Redis、文件系统中都有相应思想的设计，是一种计算机程序设计领域的优化策略。

Collection

List

ArrayList

添加元素

删除元素

序列化

Vector

Stack

LinkedList

LinkedList

Set

HashSet

LikedHashSet

TreeSet

Collection的sort方法使用的排序算法

Map

HashMap

hash冲突：拉链法

并发访问HashMap的问题

HashMap扩容问题

LinkedHashMap

LRU

HashTable(基本淘汰)

TreeMap

WeakHashMap

Tomcat的ConcurrentCache

Queue

阻塞队列

ArrayBlockingQueue

LinkedBlockingQueue

PriorityBlockingQueue

DelayQueue

ConcurrentLinkedQueue

BlockingQueue

线程安全的容器

CAS

java.util.concurrent(J.U.C)

ConcurrentHashMap

ConcurrentLinkedQueue

CopyOnWriteArrayList

ConcurrentSkipListMap

Arrays.asList()

List.subList

集合的foreach遍历

fail-fast机制

java集合的fail-fast机制

fail-safe机制

java的copy-on-write

CATALOG

FEATURED TAGS

FRIENDS