集合框架

List,Set,Map 三者的区别？

List：存储的元素是有序的（按照添加顺序进行存储），存储的元素可以重复，能够存储空值
Set：存储的元素是无序的且不可重复
Map：存储的是Key-Value键值对并且存储的内容是无序的

Collection之List

首先List集合内包含Array List、Linked List、Vector三种，这三者的区别可以分为一下几点：

底层数据结构：Array List与Vector是通过动态数组实现的，而Linked List则是通过双向链表实现的
是否保证线程安全：Array List与Linked List属于线程不安全，而Vector属于线程安全
效率问题：Array List采用数组存储，所以对于插入和删除操作受元素的位置影响，而查找和修改可以通过下标值直接操作数组，Linked List采用链表实现，所以对于插入和删除操作不受元素位置影响，而查找和删除则需要遍历整个链表确定元素位置
内存空间占用：Array List内存空间需要预留一部分，而Linked List则是需要存储指针信息

List的扩容机制

首先JDK7与JDK8在初始化数组列表的时候存在差异，JDK7的时候属于饿汉式的创建，new无参构造的Array List对象的时候直接创建长度为10的数组，而JDK8则是在第一次调用ADD方法添加元素时才进行数组容量的分配（默认长度为10），接下来我们具体看看是如何扩容的

初次调用ADD方法

 /**
 * 将指定的元素追加到此列表的末尾。
 */
public boolean add(E e) {
       //添加元素之前，先调用ensureCapacityInternal方法
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      //这里看到ArrayList添加元素的实质就相当于为数组赋值
      elementData[size++] = e;
      return true;
  }

这里我们可以看到首先调用ensureCapacityInternal方法，这个方法的作用就是对数组进行初始化使用，首先我们判断数组element是否为我们构造方法中传入的空数组如果是就判断ensureCapacityInternal传入的参数与默认容量的大小，初次minCapacity会赋值为10完成对数组的初始化，核心代码如下：

 //得到最小扩容量
 private void ensureCapacityInternal(int minCapacity) {
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          // 获取默认的容量和传入参数的较大值
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity); //扩容机制
   }

当我们完成对minCapacity的初始化就会判断是否需要进行扩容，这里调用ensureExplicitCapacity方法进行判断。

当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入（执行）grow(minCapacity) 方法。
添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。
直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。

对于grow方法中如何扩容的，则是通过位运算完成的。int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

快速失败与安全失败

快速失败：使用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行修改，会抛出Concurrent Modification Exception，内部原理是：迭代器在遍历集合时使用了mod Count变量，如果在遍历时修改内容，就会修改mod Count的值，在迭代器进行遍历使用hasNext、Next方法时都会检查mod Count是否为expectedModCount，是的话就继续遍历否则就抛出异常。
安全失败：遍历集合的时候先复制原有集合内容，在拷贝的集合上进行遍历。
虽然这种方式避免了修改时抛出异常，但是迭代器无法访问修改后的内容。

Map

首先Map集合内包含Hash Map、Hash Table、Linked Hash Map、Tree Map四种，这几种Map的区别主要有以下几点：

Hash Map与Hash Table区别：

底层数据结构不同：Hash Map在JDK8之后引入红黑树以解决查询效率问题，而Hash Table则没有实现
线程是否安全：Hash Map属于线程不安全，Hash Table属于线程安全，通过synchronized关键字实现
效率：Hash Map比Hash Table效率更高
对null指的处理：Hash Map可以存储null值，key为null只存在一个而value可以存在多个，而HashTable得键值都不允许有null值的出现。
初始化容量与扩容机制不同：*Hash Map在初始化的时候容量为16，扩容的大小为原来的2倍，而Hash Table初始化容量为11，扩容的大小为2n+1；

Hash Map与Tree Map的区别：

线程是否安全：Hash Map与Tree Map都属于线程不安全
数据结构不同：Hash Map通过数组+链表+红黑树实现，而Tree Map则是通过红黑树实现
功能不同：Hasp Map适用于插入、删除、定位元素，而Tree Map适用于按自然排序与定制排序遍历Key

Hash Map底层结构实现

首先我们说一下JDK8之前是如何实现的，Hash Map底层使用数组加链表的结构，通过Key的hasCode经过扰动函数得到hash值，通过hash&（n-1）n为数组长度得到映射位置，如果当前位置存在元素，则判断该元素的hash值以及key是否相同，如果相同则覆盖，不相同则采用头插法添加元素进链表。
JDK7的扰动函数如下:

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

JDK8的扰动函数如下：

int h;

  // key.hashCode()：返回散列值也就是hashcode
  // ^ ：按位异或
  // >>>:无符号右移，忽略符号位，空位都以0补齐
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

相比之下JDK8的扰动函数性能更好
JDK8之后，对Hash Map的底层做了优化，在解决哈希冲突的时候有了变化引入了红黑树，当链表长度大于等于8且数组的长度大于等于64的时候链表就会转化成红黑树，如果链表长度大于8而数组长度小于64则会对数组进行扩容不会进行树的转化，当链表长度为6时，红黑树会自动退化为链表

Hash Map 的长度为什么是 2 的幂次方

为了提高运算效率，对于key进行映射如果使用%进行模运算这样会大大降低其速率，因此引入了位运算&，通过对（n-1）&hash得到数组下标，这也就说明了为什么数组长度必须时2的幂次方，假如不是2的幂次方就会出现这种情况就会使数组中存在没有使用的空间导致元素之间碰撞增多。除此之外在进行扩容时候面对扩容带来数组中的元素需要全部重新进行映射问题，使用2的幂次方数组长度可以很好的解决，假如数组的长度为16使用二进制表示为1111，此时扩容为32的长度使用二进制表示为11111，我们可以通过最高位0、1来判断当前元素是否需要进行重新映射，如果为0则不需要，如果为1则表示需要进行重新计算数值为i+oldcap

Hash Map会带来的问题

在JDK7的时候，多线程的情况下扩容操作会产生链表循环问题，JDK8之后就解决了这个问题但是也产生了覆写的问题，多个线程操作同一个数组位置的时候，都会先取得该位置下的头节点，然后各自去进行计算操作，这样就会导致覆写问题。
正式由于Hash Map存在这样的并发问题，所以引入了Concurrent Hash Map来保证并发的时候不会出现上述问题。

Concurrent Hash Map

在JDK7之前由segment+数组+链表实现，其结构如图所示

image.png

其中segment继承字Reentrant Lock，将数据分为一段一段的存储，然后给每个数据添加一把锁，当某个线程占用锁访问数据时，其他段的数据不受影响其他线程仍然可以访问。从而保证了并发的效率（默认为16）
在JDK8之后取消了segment转而代替的时数组+链表+红黑树实现，通过CAS+synchronized保证并发的安全性，当链表长为8时会链表会转变为红黑树，synchronized通过锁定链表或者树的根节点来保证并发的安全性