1、List
| List | 线程安全 | 底层实现 |
|---|---|---|
| Vector | 是 | 数组 |
| ArrayList | 否 | 数组 |
| LinkedList | 否 | 链表 |
| CopyOnWriteArrayList | 是 | 数组 |
1、Vector
Vector 实现了一个动态数组。和 ArrayList 很相似，但是两者是不同的：Vector 是同步访问的，对数组的操作加了 synchronize 关键字，虽然线程安全，但是大大影响了访问速度。
2、ArrayList
- 底层是数组，初始大小为10；
- 插入新元素时，先判断数组容量是否足够，若不够就进行扩容。所谓扩容就是新建一个 1.5 倍数组，将旧数组里的内容复制到新数组里；
- 移除元素的时候也涉及到数组中元素的移动，删除指定 index 位置的元素，然后将 index+1 至数组最后一个元素往前移动一格。
小结：如果知道 ArrayList 的容量，尽量在初始化时就指定大小，因为数组的扩容相对来说还是挺耗费性能的。
3、LinkedList
LinkedList 基于链表的动态数组，数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。
对于随机访问 get 和 set，ArrayList 优于 LinkedList，因为 ArrayList 是基于数组，get 和 set 时间复杂度为 O(1)，而 LinkedList 要遍历移动指针。
而对于 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数据，LinedList 是基于链表，只需要断开或连接指针即可。
4、CopyOnWriteArrayList
什么是CopyOnWrite？
答：写时复制。
用通俗的话解释：若多个线程同时访问同一份数据，它们看到的数据是相同的，直到某个线程需要修改数据时，系统会复制一个副本给该线程，而其他线程所见到的仍然是最初的数据。
由于读操作根本不会修改原有的数据，因此像 Vector 对于每一次的读取都进行加锁是一种资源的浪费。
对 CopyOnWriteArrayList 来说，读取是完全不用加锁的，写入也不会阻塞读取操作，只有写入与写入之间需要进行同步等待。
- 实现了 List 接口；
- 写操作持有一个 ReentrantLock lock = new ReentrantLock()；
- 底层是用 volatile transient 声明的数组 array；
- 读写分离：写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给 array。
二、Map
| Map | 线程安全 | 底层实现 |
|---|---|---|
| TreeMap | 否 | 红黑树 |
| Hashtable | 是 | 数组 + 链表 |
| HashMap | 否 | 数组 + 链表 + 红黑树 |
| ConcurrentHashMap | 是 | 数组 + 链表 + 红黑树 |
| ConcurrentSkipListMap | 是 | 跳表 |
1、TreeMap
TreeMap 是一种有序的 key-value 结构的 Map，其元素默认按照 keys 的自然排序排列。对 Integer 来说，其自然排序就是数字的升序；对 String 来说，其自然排序就是按照字母表排序。所以 TreeMap 是有序的 Map。
2、Hashtable
Hashtable 同样是基于哈希表实现的，同样每个元素是一个 key-value 对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
Hashtable 在不指定容量的情况下的默认容量为 11，而 HashMap 为 16，Hashtable 不要求底层数组的容量一定要为 2 的整数次幂，而 HashMap 则要求一定为 2 的整数次幂。
Hashtable 是 JDK 1.0 引入的类，是线程安全的，能用于多线程环境中。
Hashtable 中 key 和 value 都不允许为 null，而 HashMap 中 key 和 value 都允许为 null。事实上，只有 HashMap 的 key 和 value 允许为 null，其他的 Map 都不行。
3、HashMap
在 JDK１.8 之前，HashMap 的结构是：数组 + 链表，但是如果按照链表的方式存储，随着数据的增加，链表节点的数据会越来越多，这会导致查询节点的时间复杂度会逐渐增加，平均时间复杂度Ｏ(n)。 为了提高查询效率，故在 JDK１.8 中引入了改进方法红黑树，此数据结构的平均查询效率为Ｏ(log n) 。当链表长度大于 8 时，会转换成红黑树，当红黑树数量小于 6 时，又会转成链表。
HashMap
问题1：HashMap 的初始长度是多少以及扩容的要求？
HashMap 初始长度为 16，扩容要求一定为 2 的整数次幂。
这是由于 Key 映射到 HashMap 数组的对应位置 index = hash(key) & (length - 1)。长度 16 或者其他 2 的幂，length-1 的值是所有二进制位全为 1，这种情况下，index 的结果等同于 HashCode 后几位的值。只要输入的 HashCode 本身分布均匀，hash 算法的结果就是均匀的。
问题2：HashMap 在高并发情况下有什么问题？
HashMap 的容量是有限的。当经过多次元素插入，使得 HashMap 达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap 需要扩展它的长度，也就是进行 Resize，过程如下：
- 创建一个新的 Entry 空数组，长度是原数组的 2 倍。
- 遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组。
在多线程情况下，如果两个线程都发现 HashMap 需要重新调整大小了，它们会同时尝试调整。在调整的过程中，存储在链表中元素次序会反过来，因为移动到新的 bucket 位置时，HashMap 是将元素放在链表头部，如果条件竞争发生了，链表就会形成环，那么就会发生死循环。
4、ConcurrentHashMap
Hashtable 之所以效率低下，主要是因为其实现使用了 synchronized 锁住了整个 Hash 表；而 ConcurrentHashMap 使用了分段锁机制。
简而言之，ConcurrentHashMap 在对象中保存了一个 Segment 数组，即将整个 Hash 表划分为多个分段；而每个 Segment 元素，即每个分段则类似于一个 Hashtable；这样，在执行 put 操作时首先根据 hash 算法定位到元素属于哪个 Segment，然后对该 Segment 加锁即可。因此，ConcurrentHashMap 在多线程并发编程中可是实现多线程 put 操作。
ConcurrentHashMap 1.7
在 JDK1.8 中，ConcurrentHashMap 的实现原理摒弃了上述这种设计，而是选择了与 HashMap 类似的 数组+链表+红黑树 的方式实现，而加锁则采用 CAS 和 synchronized 实现。
-
先通过 spread 方法计算出 key 的 hash 值，使用了懒加载模式，在第一次 put 数据时，使用 CAS 操作执行初始化操作。初始化大小默认为16。
-
判断该位置的hash值是否为
MOVED，如果为MOVED表示此时数组正在发生扩容，那么当前线程帮助数组一起进行扩容操作。 -
如果当前位置上存在 Node，则使用 synchronized 锁住当前 Node，判断当前节点下如果是链表，就遍历整个链表，如果找到相同的 hash 值和 key 就更新 value，如果没有找到则新建一个 Node 放到链表的最后。如果当前节点是一个红黑树（链表长度超过8会自动转为红黑树），那么按照红黑树的方法查找。
ConcurrentHashMap 1.8
5、ConcurrentSkipListMap
通过上面我们知道：TreeMap 内部元素是有序的，但非线程安全；HashMap 内部元素是无序的，并且非线程安全；ConcurrentHashMap 内部元素是无序的，是线程安全的。
那么有没有一种内部元素是有序的，同时也是线程安全的数据结构呢？
当然有，这就是 ConcurrentSkipListMap，一种基于跳表来实现的 Map。所有的修改操作都是使用 CAS，只要失败就会重试，直至成功，所以就算多线程并发操作也不会出现错误，而且通过 CAS 避免了使用锁，性能比用锁好很多。
跳表
网友评论