如图所示：图中，实线边框的是实现类，折线边框的是抽象类，而点线边框的是接口
List(有序、可重复)
List里存放的对象是有序的，同时也是可以重复的，List关注的是索引，拥有一系列和索引相关的方法，查询速度快。因为往list集合里插入或删除数据时，会伴随着后面数据的移动，所有插入删除数据速度慢。
List 接口有三个实现类（LinkedList：基于链表实现，链表内存是散乱的，每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快，查找慢；ArrayList：基于数组实现，非线程安全的，效率高，便于索引，但不便于插入删除；Vector：基于数组实现，线程安全的，效率低）。
Set(无序、不能重复)
Set里存放的对象是无序，不能重复的，集合中的对象不按特定的方式排序，只是简单地把对象加入集合中。
Set 接口有两个实现类（HashSet：底层是由 HashMap 实现，不允许集合中有重复的值，使用该方式时需要重写 equals()和 hashCode()方法；LinkedHashSet：继承与 HashSet，同时又基于 LinkedHashMap 来进行实现，底层使用的是 LinkedHashMap）。
Map（键值对、键唯一、值不唯一）
Map集合中存储的是键值对，键不能重复，值可以重复。根据键得到值，对map集合遍历时先得到键的set集合，对set集合进行遍历，得到相应的值。
Map 集合（ HashMap： 是最常用的Map，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。因为键对象不可以重复，所以HashMap最多只允许一条记录的键为Null，允许多条记录的值为Null，是非同步的； HashTable： 与HashMap类似，是HashMap的线程安全版，它支持线程的同步，即任一时刻只有一个线程能写Hashtable，因此也导致了Hashtale在写入时会比较慢，它继承自Dictionary类，不同的是它不允许记录的键或者值为null，同时效率较低。；LinkedHashMap： 是 HashMap 的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，在遍历的时候会比HashMap慢，有HashMap的全部特性。；TreeMap： TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序（自然顺序），也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。不允许key值为空，非同步的；）
iterator的形式：
Iterator it = arr.iterator();
while(it.hasNext()){
object o =it.next(); ...
}
for（int i：arr）{...}
for（int i=0;i<arr.size();i++）{...}
ArrayList是实现了基于动态数组的数据结构，LinkedList基于双向链表的数据结构。ArrayList优于LinkedList，因为LinkedList要移动指针。LinkedList不支持高效的随机元素访问，而 ArrayList 支持。LinedList比较占优势，因为ArrayList要移动数据。ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist。当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList 会提供比较好的性能 ; 当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用 LinkedList 了
Collections是个java.util下的类，它包含有各种有关集合操作的静态方法。服务于Java的Collection框架。
Collection是个java.util下的接口，它是各种集合结构的父接口。
从JDK1.0开始，Vector便存在JDK中，Vector是一个线程安全的列表，采用数组实现。其线程安全的实现方式是对所有操作都加上了synchronized关键字，这种方式严重影响效率。
CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况。
/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;//保证了线程的可见性
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1); //copy一份比当前数组长度+1的array数组
else {
newElements = new Object[len + 1]; //将add的参数赋值
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements); //将原数组指向新的数组
} finally {
lock.unlock();
}
}
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1)); //copy一份比当前数组长度-1的array数组
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements); //将原数组指向新的数组
}
return oldValue;
} finally {
lock.unlock();
}
}
/**
* 将原数组指向新的数组
*/
final void setArray(Object[] a) {
array = a;
}
从以上源码我们可以看出，它在执行add方法和remove方法的时候，分别创建了一个当前数组长度+1和-1的数组，将数据copy到新数组中，然后执行修改操作。修改完之后调用setArray方法来指向新的数组。在整个过程中是使用ReentrantLock可重入锁来保证不会有多个线程同时copy一个新的数组，从而造成的混乱。并且使用volatile修饰数组来保证修改后的可见性。读写操作互不影响，所以在整个过程中整个效率是非常高的。
SynchronizedList其实现线程安全的方式是建立了list的包装类，对部分操作加上了synchronized关键字以保证线程安全。但其iterator()操作还不是线程安全的。
public void test(){
ArrayList<String> list = new ArrayList<>();
List<String> sycList = Collections.synchronizedList(list);
sycList.add("a");
sycList.remove("a");
}
synchronizedList遍历为什么还需要加锁？
synchronizedList官方文档中给出的使用方式是以下方式：
List list = Collections.synchronizedList(new ArrayList());
...
synchronized (list) {
Iterator i = list.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
虽然内部方法中大部分都已经加了锁，但是iterator方法却没有加锁处理。那么如果我们在遍历的时候不加锁会导致什么问题呢？
试想我们在遍历的时候，不加锁的情况下，如果此时有其他线程对此集合进行add或者remove操作，那么这个时候就会导致数据丢失或者是脏数据的问题，所以如果我们对数据的要求较高，想要避免这方面问题的话，在遍历的时候也需要加锁进行处理。
CopyOnWriteArrayList和Collections.synchronizedList是实现线程安全的列表的两种方式。两种实现方式分别针对不同情况有不同的性能表现，其中CopyOnWriteArrayList的写操作性能较差，而多线程的读操作性能较好。而Collections.synchronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多，而读操作因为是采用了synchronized关键字的方式，其读操作性能并不如CopyOnWriteArrayList。 因此在不同的应用场景下，应该选择不同的多线程安全实现类。
Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降;
CopyOnWriteArrayList，发生修改时候做copy，新老版本分离，保证读的高性能，适用于以读为主，读操作远远大于写操作的场景中使用，比如缓存;
而Collections.synchronizedList则可以用在CopyOnWriteArrayList不适用，但是有需要同步列表的地方，读写操作都比较均匀的地方。
AbstractMap类；而Hashtable继承自Dictionary类；final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// 1.如果table为空或者长度为0，即没有元素，那么使用resize()方法扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.计算插入存储的数组索引i，此处计算方法同 1.7 中的indexFor()方法
// 如果数组为空，即不存在Hash冲突，则直接插入数组
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3.插入时，如果发生Hash冲突，则依次往下判断
else {
HashMap.Node<K,V> e; K k;
// a.判断table[i]的元素的key是否与需要插入的key一样，若相同则直接用新的value覆盖掉旧的value
// 判断原则equals() - 所以需要当key的对象重写该方法
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// b.继续判断：需要插入的数据结构是红黑树还是链表
// 如果是红黑树，则直接在树中插入 or 更新键值对
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果是链表，则在链表中插入 or 更新键值对
else {
// i .遍历table[i]，判断key是否已存在：采用equals对比当前遍历结点的key与需要插入数据的key
// 如果存在相同的，则直接覆盖
// ii.遍历完毕后任务发现上述情况，则直接在链表尾部插入数据
// 插入完成后判断链表长度是否 > 8：若是，则把链表转换成红黑树
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 对于i 情况的后续操作：发现key已存在，直接用新value覆盖旧value&返回旧value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入成功后，判断实际存在的键值对数量size > 最大容量
// 如果大于则进行扩容
if (++size > threshold)
resize();
// 插入成功时会调用的方法（默认实现为空）
afterNodeInsertion(evict);
return null;
}
根据代码可以总结插入逻辑如下:
插入过程中涉及到几个其他关键的方法 ：
HashMap 中通过将传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。
由于 int 只有 32 位，无符号右移 16 位相当于把高位的一半移到低位：
这样可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。
Java 位运算(移位、位与、或、异或、非）
每次添加时会比较当前元素个数和阈值：
//如果超出阈值，就得扩容
if (++size > threshold)
resize();
resize():
final Node<K,V>[] resize() {
//复制一份当前的数据
Node<K,V>[] oldTab = table;
//保存旧的元素个数、阈值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新的容量为旧的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果旧容量小于等于 16，新的阈值就是旧阈值的两倍
newThr = oldThr << 1; // double threshold
}
//如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新阈值
threshold = newThr;
//创建新链表数组，容量是原来的两倍
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//接下来就得遍历复制了
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//旧的桶置为空
oldTab[j] = null;
//当前 桶只有一个元素，直接赋值给对应位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果旧哈希表中这个位置的桶是树形结构，就要把新哈希表里当前桶也变成树形结构
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //保留旧哈希表桶中链表的顺序
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//do-while 循环赋值给新哈希表
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容过程中几个关键的点：
新初始化哈希表时，容量为默认容量16，阈值为 容量*加载因子
已有哈希表扩容时，容量、阈值均翻倍
如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构
复制给新哈希表中需要重新索引（rehash），这里采用的计算方法是
结合扩容源码可以发现扩容的确开销很大，需要迭代所有的元素，rehash、赋值，还得保留原来的数据结构。
所以在使用的时候，最好在初始化的时候就指定好 HashMap 的长度，尽量避免频繁 resize()。
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表， 所以我们还需要对hashCode作一定的优化。
上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中HashMap()实现了自己的hash()函数。
hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
那怎么解决呢？
hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；为什么数组长度要保证为2的幂次方呢？
那为什么是两次扰动呢？
这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；
| 不同 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 存储结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 初始化方式 | 单独函数：inflateTable() | 直接集成到了扩容函数resize()中 |
| hash值计算方式 | 扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算 | 扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算 |
| 存放数据的规则 | 无冲突时，存放数组；冲突时，存放链表 | 无冲突时，存放数组；冲突 & 链表长度 < 8：存放单链表；冲突 & 链表长度 > 8：树化并存放红黑树 |
| 插入数据方式 | 头插法（先讲原位置的数据移到后1位，再插入数据到该位置） | 尾插法（直接插入到链表尾部/红黑树） |
| 扩容后存储位置的计算方式 | 全部按照原来方法进行计算（即hashCode ->> 扰动函数 ->> (h&length-1)） | 按照扩容后的规律计算（即扩容后的位置=原位置 or 原位置 + 旧容量） |
String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；如果我想要让自己的Object作为K应该怎么办呢？
重写hashCode()和equals()方法
ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。
JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：
ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）
插入元素过程（建议去看看源码）：
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。
例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
解决办法：
1. 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
2. 使用CopyOnWriteArrayList来替换ArrayList
HashSet是如何保证元素的不重复和无序
因为HashSet的底层存储结构是HashMap，并且HashSet中的元素是作为Map的Key存储到Map中，所以HashMap中Key是不重复且无序，所以HashSet中的元素也就是不重复和无序的
HashSet的增删（改查？）原理
HashSet的增删原理很简单，就是map的put和remove，为什么没有改查呢？那是因为HashSet中的元素是无序的，没办法根据索引进行查询和修改
CopyOnWriteArraySet支持并发的原理
CopyOnWriteArraySet之所以叫CopyOnWriteArraySet，是因为它的底层存储结构是CopyOnWriteArrayList，同时也就是保证了它的并发安全性
CopyOnWriteArraySet的增删（改查？）原理
CopyOnWriteArraySet继承了AbstractSet，跟HashSet一样只有增删，没有改查，增删原理也就是调用CopyOnWriteArrayList的增删方法，只不过增的时候需要判断一下List中是否存储该元素