首先一张图：了解五花八门的集合继承关系！
太烦了没关系，缩略版如下：

总体上来看，常用的、常问的有三个接口：List有序列表、Set集合、Map键值对集合。

1.List：有序列表（元素可重复）

（1）ArrayList：数组

• 底层结构：Object[]数组
• 初始化：ArrayList的构造函数有三个：
  ①无参：数组初始化为默认的空数组。（添加第一个元素的时候才会初始化为容量为10的数组）
  ②参数为int（即指定大小数组）：如果参数小于10，则创建容量为10的数组，否则创建指定大小的数组。
  ③参数为Collection类型：将参数转化为数组，如果数组为空则指向默认空数组，否则查看数组的类型是否是Object类型，不是的话要复制转换为Object类型。
• 添加新元素：先移动游标，然后判断是否需要扩容，需要则先扩容，在将元素后移将新元素的位置腾出来（尾部添加省略这一步），之后在将新元素放在腾出来的指定位置。
• 扩容：先看扩容的大小，如果扩容的大小小于10，则创建一个新数组容量为10，否则就1.5倍数组扩容。
• 删除元素：删除指定索引的元素，将该索引后的元素前移一位，最后将游标前移；删除指定元素，首先遍历找到该元素的索引，然后通过索引删除该元素。

  （2）LinkedList：双向链表

• 底层结构：双向链表
• 添加新元素：
  ①头部添加：新元素的后继指针指向头指针指向的元素，头指针指向的元素的前驱指针指向新元素，头指针指向新元素。
  ②尾部添加：新元素的前驱指针指向尾指针指向的元素，尾指针指向的元素的后继指针指向新元素，尾指针指向新元素。
• 删除元素：从头指针开始遍历，找到对应元素后将待删除元素的前驱指针指向的元素的后继指针指向待删除元素的后继指针指向的元素，待删除元素的后继指针指向的元素的前驱指针指向待删除元素的前驱指针指向的元素。

  （3）Vector：向量

  与ArrayList相比，多了通过synchronized保证线程安全。

  2.Map:键值对集合（键不可重复）

  （1）HashMap:

• 底层结构：
  JDK1.7：数组+链表
  JDK1.8：数组+链表+红黑树
  （通过红黑树来优化查询速度，当链表上元素个数大于8转化为红黑树，小于8则转化为链表）
• 初始化：构造函数有四个：
  数组的默认初始化大小为16，默认负载因子为0.75。
  ①无参：负载因子初始化为默认值0.75。
  ②参数为int（指定容量）：调用构造函数③（int，int)，负载因子为默认值0.75。
  ③参数为int，int（指定容量，指定负载因子）：判断指定的容量、负载因子的合法性。
  ④参数为Map类型：先判断对于参数的大小，更新数组的元素个数大小，遍历将每个键值对放进hashmap中。
• 添加新元素：先判断对于添加元素后的元素总个数是否需要扩容，如果需要，先扩容，之后进行散列，如果对应位置为null则直接创建新的节点放进去，如果对应位置有元素，则遍历判断，如果有相同key的覆盖，遍历结束如果没有找到相同的key则在链表尾部插入新节点。
  （1.7中使用了头插法插入节点，1.8中使用尾插法，目的是为了避免链表环化问题）。
• 扩容：如果旧数组的大小>0则创建新数组，大小为旧数组的2倍。如果旧数组为空则创建的新数组长度为16。之后如果旧数组不为空则要把旧数组的键值全部重新hash到新数组中。
  计算新位置的时候：如果当前位置上的链表只有一个元素e，则通过e.hash & (newCap-1)计算出新位置直接放过去；
  如果当前位置上的链表不止一个元素，则可能会分成两部分：一部分仍在原位置e.hash & (oldCap-1)，另一部分在hash & (newCap-1) == hash &(oldCap*2-1)即原下标+旧数组长度；(hash & oldCap) == 0的在原位置上，而不满足的是在新位置上。
• 删除元素：先进行hash散列，如果散列的位置上链表只有一个元素则判断是否元素hash相等，key值相等，相等删除该节点；如果不止一个元素则遍历判断后在删除。
• 查找元素：通过key查找元素时，会通过hash散列到对应的链表上，先判断链表头元素的hash、key是否相等，相等则直接返回；如果不相等则遍历链表判断后找到在返回，如果结束仍然没有找到返回null。

  （2）HashTable：

  与HashMap相比，多了通过synchronized保证线程安全。

  （3）LinkedHashMap：

  与HashMap相比，通过头指针、尾指针，并给每个Node<K,V>添加了前后指针，来记录元素的插入顺序。

  （4）TreeMap：

• 底层结构：红黑树
  数据结构之红黑树 暂时没写....

  3.Set：集合（元素不可重复）

  （1）HashSet：基于HashMap实现的，value=null

  （2）LinkedHashSet：基于LinkedHashMap实现的，value=null

  （3）TreeSet：基于TreeMap实现的，value=null