List 集合的三个子类：
ArrayList：底层是数组，查询快（地址连续）、增删慢、线程非安全。
LinkedList：底层是链表，查询慢、增删快、无索引、线程非安全。
Vector：底层是数组，线程安全。
1.1 构造方法
ArrayList 底层是一个数组结构，当指定初始容量为0时返回的是 EMPTY_ELEMENTDATA，不指定容量时返回 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
1.2 add 方法
1. 确认list容量，尝试容量加1看有无必要，因为当添加一个元素后，可能对超过集合初始容量，将会引发扩容。如果没有超过初始容量则保存最小容量不变，无需对容量+1。
2. 添加元素
第一个方法得到数组的最小容量，避免资源浪费，第二个方法判断最小容量是否大于数组长度，大于则调用grow()进行扩容。
grow()扩容的实现
newCapacity 这里对数组容量扩容1.5倍，扩容完毕后调用 copyOf() ,完成对数组元素的拷贝。
总的来说 add(E e) 的实现： 首先检查数组容量是否足够，够直接添加元素，不够进行扩容。
1.3 get 方法
检查角标是否越界，然后添加元素。
1.4 set 方法
检查是否越界，替换元素。
1.5 remove() 方法
numMoved 是需要移动的元素个数，从 index+1位置开始拷贝 numMoved 个元素 到数组的 index 位置，就等于将被删除元素后面的所有元素往前移动一个位置。因此List集合删除效率低。
Vector 是同步的（线程安全），其内部方法都使用 synchronized 修饰，同样Vector因此效率比较低下。ArrayList 线程非安全。
ArrayList 底层扩容是在原有基础上扩容1.5 倍，Vector是扩容 2 倍。
LinkedList 集合特点：
1. 底层是双向链表，查询慢，增删快。 2. 包含大量操作首尾的方法。
3.1 add 方法
了解过链表底层实现的应该对 LinkedList 的方法并不陌生，无论是添加还是删除方法，都拆分为 对头部和尾部元素的具体操作。
这里 add 方法采用尾插法，同样也有 addFirst addLast 方法。
3.2 remove 方法
unlink(x) 完成对元素的删除，删除元素调用 equals 方法其实就是判断元素是否存在链表中，unlink 方法中实现了双向链表中删除元素的操作。
将被删除节点断开，通过①②连接链表。
3.3 get 方法
判断下标是否合法，然后调用node方法获取链表元素。
3.4 set 方法
与 get 方法类似，根据下标判断从头遍历还是从尾遍历。
Set 集合的使用频率相比 List 集合较低，通常结合 set 集合 元素不可重复的特点进行一些操作，比如寻找只出现一次的数字、或者在实际项目中需要存储不可重复元素可以考虑使用 Set 集合。
HashSet集合
A：底层数据结构是HashMap
B：允许null，非同步
TreeSet集合
A：底层数据结构是红黑树(是一个自平衡的二叉树)
B：保证元素的排序方式，不允许null，非同步
LinkedHashSet集合
A：底层数据结构由HashMap和双向链表组成。
B：允许null
java.util.HashSet 集合 implements Set接口
HashSet是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于：hashCode与equals方法。
2.1 HashSet特点：
1.不允许存储重复元素，允许元素为null
2.没有索引，没有带索引的方法，也没有for循环遍历
3.是一个无序的集合，存储元素和取出元素的顺序有可能不一致
4.底层是HashMap(查询速度非常快)
Set<Integer> set = new HashSet<>(); //多态 //使用add方法往集合中添加元素 set.add(1); set.add(3); set.add(2); set.add(1); //使用迭代器遍历set集合 Iterator<Integer> it = set.iterator(); while(it.hasNext()){ Integer n = it.next(); System.out.println(n); //1,2,3 不允许存储重复元素，无序 } //增强for遍历set集合 for(Integer n:set){ System.out.print(n); }2.2 HashSet集合存储结构（哈希表）
在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理哈希冲突，同一hash值的链表都存储在一个链表里。但是当hash值相等的元素较多时，通过key值在链表中依次查找的效率较低。JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过（8）时，将链表转换为红黑树，这样大大减少了查找时间。
要保证HashSet集合元素的唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。（面试常考hashCode 和 equals 的联系）
① 重写 hashCode 必须同时重写equals。
② 相等（相同）的对象必须具有相等的哈希码（或者散列码）。
③ 如果两个对象的hashCode相同，它们并不一定相同。
java.util.Map<k,v>集合 存储的元素是键值对类型，key - value是一一对应的映射关系。
Map集合特点：
key 和 value 数据类型是任意的，一般我们习惯使用key为String类型，value为Object类型。
key 不允许重复，value 可以重复，key只允许存在一个null的情况，value可以存在多个null值。
1. Map 集合存储元素是键值对的方式，键唯一，值可以重复。
2. Collection 集合存储元素是单独出现的，Collection 的子接口Set值是唯一的，List是可重复的。
List 集合底层是链表或者数组，存储的顺序和取出的顺序是一致的，但同样会带来一个缺点，想要获取某个元素，就要访问所有元素，直到找到为止。
在哈希表中，我们不在意元素的顺序，能够快速查找到元素。哈希表中每个对象按照哈希值保存在对应的位置上。哈希表是由数组+链表实现的，每个列表称为桶，
JDK1.8 之前 哈希值相同的对象以链表形式存储在一个桶中，这种情况称为哈希冲突，此时需要用该对象与桶上的对象进行比较，看看是否已经存在桶中，如果存在就不添加。（这个过程使用hashCode和equals进行判断，这也是之前我们说过为什么要同时重写hashCode和equals的原因），接下来了解了HashMap的put方法底层原理，应该会对为什么同时重写更加清晰了。
JDK1.8 之后 当链表长度超过8，会从链表转换为红黑树结构。当哈希表存储元素太多，需要对其进行扩展，创建一个桶更多的哈希表，那么什么时候需要进行扩容？装填因子(load factor)决定了何时进行扩展，装载因子默认为0.75，表中如果超过75%的位置已经填入元素，将进行双倍的扩展。
3.1 HashMap 类前注释解读
主要讲了 HashMap 的一些特点：key value 允许为null，不保证有序，不同步（线程非安全），想实现同步调用Collections.synchronizedMap，装载因子为0.75。使用迭代器进行遍历。当知道要存储的元素个数时，尽可能设置初始容量。
3.2 HashMap 属性
当链表长度大于8，数组元素超过64 由链表结构转化为红黑树。
JDK1.7 时，在实例化之后，底层创建了长度是16的Entry数组。
JDK1.8 时，底层为Node数组，调用put方法后创建长度为16的数组。虽然长度为16，但是切记，负载因子0.75，因此数组只存放12个元素。
3.3 put 方法
put 方法是HashMap的核心，也是面试常考点。
调用 hash(key) 方法，以key计算哈希值，hash 方法中得到key的hashCode 与 key的hashCode 高16位做异或运算，得到的值可以减少碰撞冲突的可能性。
1、hash(key)，取key的hashcode进行高位运算，返回hash值 2、如果hash数组为空，直接resize() 3、对hash进行取模运算计算，得到key-value在数组中的存储位置i （1）如果table[i] == null，直接插入Node<key,value> （2）如果table[i] != null，判断是否为红黑树p instanceof TreeNode。 （3）如果是红黑树，则判断TreeNode是否已存在，如果存在则直接返回oldnode并更新；不存在则直接插入红黑树，++size，超出threshold容量就扩容 （4）如果是链表，则判断Node是否已存在，如果存在则直接返回oldnode并更新；不存在则直接插入链表尾部，判断链表长度，如果大于8则转为红黑树存储，++size，超出threshold容量就扩容
3.4 get 方法
我们知道HashMap 是通过key找value，获取key的哈希值，调用getNode方法获取对应value。
getNode 的实现比较简单，先判断计算出来的hashCode是否存在哈希表中，然后判断是否在桶的首位，不在则在链表或红黑树中进行遍历。
3.5 remove 方法
类似于put方法，这里就不贴源码，可以在util包下查看源码。
计算key 的hash值，然后去找对应节点，找到后分三种情况进行删除：1. 链表 2. 红黑树 3. 桶的首位
1、继承的父类不同
Hashable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口。
2、线程安全性不同
HashTable是线程安全的，HashTable方法都加入了Synchronized，HashMap是非安全的。
3、是否提供contains方法
HashMap把contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。
4、key和value是否允许null值
其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。
HashMap允许空值，键key最多只能1个null值，value允许多个null，HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
Hashtable中，key和value都不允许出现null值。
5、两个集合遍历方式的内部实现上不同
Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式
6、hash值不同
哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
7、内部实现使用的数组初始化和扩容方式不同
HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
图文并茂，对比很细，加粗部分可作为面试主答点。
5.1 LinkedHashMap 类前注释解读
底层是哈希表+链表，允许为null，线程不同步，插入元素有序
5.2 总结
这里没有对LinkedHashMap具体方法进行解析，因为它继承自HashMap，在很多操作上使用的是HashMap的方法。而HashMap的方法我们上面已经进行了分析。
6.1 TreeMap 类前注释解读
底层是红黑树，实现NavigableMap 接口，可以根据key自然排序，也可以在构造方法上传递Camparator实现Map的排序。不同步
TreeMap 实现NavigableMap 接口，而NavigableMap接口继承着SortedMap接口，致使我们的TreeMap是有序的。
key不能为null。
6.2 构造方法
//comparator 维护的变量为null，使用自然排序 public TreeMap() { comparator = null; } //设置一个维护变量传入 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } //调用putAll将Map转为TreeMap public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } //使用buildFromSorted转TreeMap public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }6.3 put 方法
6.4 get 方法
get 方法由getEntry进行具体实习
getEntry
当 comparator 不为null时，getEntryUsingComparator(Object key) 调用Comparator 自己实现的方法获取相应的值。
6.5 总结
TreeMap底层是红黑树，能够实现该Map集合有序
如果在构造方法中传递了Comparator对象，那么就会以Comparator对象的方法进行比较。否则，则使用Comparable的compareTo(T o)方法来比较。（自然排序）
值得说明的是：如果使用的是compareTo(T o)方法来比较，key一定是不能为null，并且得实现了Comparable接口的。
即使是传入了Comparator对象，不用compareTo(T o)方法来比较，key也是不能为null的。
重头戏来了~~~~
7.1 JDK1.7和JDK1.8 不同
1. JDK1.7 底层实现是：segments+HashEntry数组
ConcurrentHashMap使用分段锁技术，Segment继承了ReentrantLock,每个片段都有了一个锁，叫做“锁分段”
我们知道Map中Hashtable是线程安全的，为什么要用ConCurrentHashMap？
Hashtable 是在每个方法上都加上了Synchronized 完成同步，效率极其低下，而ConcurrentHashMap通过部分加锁和利用CAS算法来实现同步。
2. JDK 1.8底层实现是：哈希表+红黑树
检索操作不用加锁，get方法是非阻塞的，key和value都不允许为空。
取消了1.7的 segments 分段锁机制，采用CAS + volatile 乐观锁机制保证线程同步。
7.2 CAS算法和volatile简单介绍
1. CAS（Compare and swap，比较与交换）
CAS 是一种基于乐观锁的操作。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。
CAS有3个操作数
内存值V
旧的预期值A
要修改的新值B
当且仅当预期值A和内存值V相同时，将内存值V修改为B。CAS是通过无限循环来获取数据的，若果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。
2. volatile 关键字
volatile仅仅用来保证该变量对所有线程的可见性，但不保证原子性
可见性：在多线程环境下，当被volatile修饰的变量修改时，所有的线程都可以知道该变量被修改了
不保证原子性：修改变量(赋值)实质上是分为好几步操作，在这几步操作中是不安全的。
7.2 put 方法
put操作采用CAS+synchronized 实现并发插入或更新操作。
如果没有初始化就先调用initTable（）方法来进行初始化过程如果没有hash冲突就直接CAS插入如果还在进行扩容操作就先进行扩容如果存在hash冲突，就加 synchronized 锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，最后一个如果Hash冲突时会形成Node链表，在链表长度超过8，Node数组超过64时会将链表结构转换为红黑树的结构，break再一次进入循环如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容initTable 方法的实现
当要初始化时会通过CAS操作将sizeCtl置为-1，而sizeCtl由volatile修饰，保证修改对后面线程可见。 这之后如果再有线程执行到此方法时检测到sizeCtl为负数，说明已经有线程在给扩容了，这个线程就会调用Thread.yield()让出一次CPU执行时间。
7.3 get 方法
我们之前说到 get 操作不用加锁，是非阻塞的，因为 Node 节点被重写了，设置了volatile关键字修饰，致使它每次获取的都是最新设置的值。
CopyOnWriteArrayList是线程安全容器(相对于ArrayList)，底层通过复制数组的方式来实现。
CopyOnWriteArrayList在遍历的使用不会抛出ConcurrentModificationException异常，并且遍历的时候就不用额外加锁。
8.1 CopyOnWriteArrayList 基本结构
CopyOnWriteArrayList底层是数组，加锁交由ReentrantLock来完成
//可重入锁对象 final transient ReentrantLock lock = new ReentrantLock(); //CopyOnWriteArrayList底层由数组实现，volatile修饰 private transient volatile Object[] array; //得到数组 final Object[] getArray() { return array; } //设置数组 final void setArray(Object[] a) { array = a; } //初始化数组 public CopyOnWriteArrayList() { setArray(new Object[0]); }8.2 add 方法
public boolean add(E e) { //加锁 final ReentrantLock lock = this.lock; lock.lock(); try { //得到原数组长度和元素 Object[] elements = getArray(); int len = elements.length; //复制一个新数组 Object[] newElements = Arrays.copyOf(elements, len + 1); //将元素添加到新数组 newElements[len] = e; //将volatile Object[] array 的指向替换成新数组 setArray(newElements); return true; } finally { lock.unlock(); } }在添加的时候上锁，并复制一个新数组，添加操作在新数组上完成，将array指向到新数组中，最后解锁。
8.3 set 方法
public E set(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); try { //得到原数组旧值 Object[] elements = getArray(); E oldValue = get(elements, index); //判断新值和旧值是否相等 if (oldValue != element) { int len = elements.length; //复制新数组，在新数组中完成修改 Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; //array引用指向新数组 setArray(newElements); } else { // Not quite a no-op; ensures volatile write semantics setArray(elements); } return oldValue; } finally { lock.unlock(); } }在修改时，复制出一个新数组，修改的操作在新数组中完成，最后将新数组交由array变量指向。
写加锁，读不加锁，读取数据是在原数组，因此保证了多线程下的数据一致性。
类似于读写分离的思想，读和写分别在不同的容器完成，写时进行读操作并不会读到脏数据。
8.4 CopyOnWriteArrayList缺点
占用内存：如果CopyOnWriteArrayList经常要增删改里面的数据，经常要执行add()、set()、remove()进行新数组创建，那是比较耗费内存的。
数据一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
上面标注（面试）的这里就不再阐述。。。
存储结构不同：List 是存储单列的集合，Map是存储key-value键值对的集合
元素是否可重复：List 允许重复元素，Map不允许key重复
是否有序：List集合是有序的（存储有序），Map集合是无序的。
Collection是集合的上级接口，继承它的有Set和List接口
Collections是集合的工具类，提供了一系列的静态方法对集合的搜索、查找、同步等操作
ArrayList和Vector都是使用数组方式存储元素，可以直接按照索引查找元素、访问快、增删慢（相对的，极端情况不考虑）。
LinkedList使用双向链表存储数据、查找慢、增删快（相对的，极端情况不考虑）。
Vector使用了synchronized方法，线程安全，性能上较ArrayList差。LinkedList也是线程不安全的，LinkedList提供了一些方法，使得它可以被当作堆栈或者队列来使用。
需要同时重写该类的hashCode()方法和equals方法。
原因：
插入元素时先计算hashCode值，相等则调用 equals() 方法，两个key相同，替换元素值，两个key不相同，说明 hashCode 值是碰巧相同，则将新增元素放在桶里。
我们一般认为，只要两个对象的成员变量的值是相等的，那么我们就认为这两个对象是相等的，因此要重写equals()f方法，重写了equals()，就必须重写hashCode()方法，因为equals()认定了这两个对象相同，而同一个对象调用hashCode()方法时，是应该返回相同的值的！
