Java [集合]

快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

原理？

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

ArrayList

1）底层实现：Object[]数组，它实现了RandomAccess接口，支持快速随机访问，通过下标的方式来访问集合。
2）数组定长的，所有当集合中的元素个数达到数组长度时再添加元素，它需要扩容，扩容过程是：先判断是否需要扩容，扩容算法Capacity15倍。15=10+10>>1；，调用System.*arraycopy();方法进行复制原数组，最后将新增的元素，加入到集合。
3）它是非线程安全的。
arrayList1.7开始变化有点大，一个是初始化的时候，1.7以前会调用this(10)才是真正的容量为10，1.7即本身以后是默认走了空数组，只有第一次add的时候容量会变成10。

LinkedList

1）底层实现：双向链表，不能通过下标访问。
2）查询慢，增删快。

Vector

1. ArrayList是线程不安全的，Vector是线程安全的
   2. 扩容时候ArrayList扩0.5倍，Vector扩1倍

Vector的关键方法都使用了synchronized修饰。
线程安全的List：Vector或者我们可以使用Collections下的方法来包装一下

CopyOnWriteArrayList

在添加的时候就上锁，并复制一个新数组，增加操作在新数组上完成，将array指向到新数组中，最后解锁。
内存占用：如果CopyOnWriteArrayList经常要增删改里面的数据，经常要执行add()、set()、remove()的话，那是比较耗费内存的。
因为我们知道每次add()、set()、remove()这些增删改操作都要复制一个数组出来。
数据一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
从上面的例子也可以看出来，比如线程A在迭代CopyOnWriteArrayList容器的数据。线程B在线程A迭代的间隙中将CopyOnWriteArrayList部分的数据修改了(已经调用setArray()了)。但是线程A迭代出来的是原有的数据。

HashMap

• HashMap的底层数据结构？

由数组和链表组合构成的数据结构。数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node。

• HashMap的存取原理？

index = HashCode（Key） & （Length - 1）
将元素放入对应数组下标中。
如果两个元素Hashcode一样，那么它们算出的下标就会相同，维护一个链表。

• Java7和Java8的区别？

Entry链表插入：java8之前是头插法，在java8之后，都是所用尾部插入了。
使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

Java8之后链表有红黑树的部分，大家可以看到代码已经多了很多if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。
Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？
根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。

• 有什么线程安全的类代替么?

• 使用Collections.synchronizedMap(Map)创建线程安全的map集合；
  在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex
  我们在调用这个方法的时候就需要传入一个Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。
  如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。
  创建出synchronizedMap之后，再操作map的时候，就会对方法上锁。

• Hashtable
  * ConcurrentHashMap

  • HashMap的扩容方式？负载因子是多少？为什么是这么多？

影响扩容的两个因素：
Capacity：HashMap当前长度，默认16。
LoadFactor：负载因子，默认值0.75f。

1<<4就是16

因为在使用是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。
只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

容量最好是2的幂，这样是为了位运算的方便，位与运算比算数计算的效率高了很多。

分为两步：
扩容：创建一个新的Entry空数组，长度是原数组的2倍。
ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

因为长度扩大以后，Hash的规则也随之改变。

Hash的公式—-> index = HashCode（Key） & （Length - 1）

HashTable

Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。

因为Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。

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

这是因为Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据。
如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。

Hashtable与HashMap的区别
实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
Dictionary 是 JDK 1.0 添加的，貌似没人用过这个，我也没用过。
初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
扩容机制不同：当现有容量大于总容量 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
* 迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。

ConcurrentHashMap

ConcurrentHashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。

如图所示，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

volatile的特性是啥？
保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（实现可见性）
禁止进行指令重排序。（实现有序性）
* volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。

那你能说说他并发度高的原因么？

原理上来说，ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。
不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。
每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
1. 尝试自旋获取锁。
2. 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。

get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁

ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：
1. 根据 key 计算出 hashcode 。
2. 判断是否需要进行初始化。
3. 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
5. 如果都不满足，则利用 synchronized 锁写入数据。
6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

你在上面提到CAS是什么？自旋又是什么？
CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。
CAS 操作的流程如下图所示，线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。这是一种乐观策略，认为并发操作并不总会发生。

CAS就一定能保证数据没被别的线程修改过么？

并不是的，比如很经典的ABA问题，CAS就无法判断了。

那怎么解决ABA问题？
用版本号去保证就好了，就比如说，我在修改前去查询他原来的值的时候再带一个版本号，每次判断就连值和版本号一起判断，判断成功就给版本号加1。

synchronized之前一直都是重量级的锁，但是后来java官方是对他进行过升级的，他现在采用的是锁升级的方式去做的。
针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。