所有集合类都在java.util.*包下，由collection接口继承而来的有list,set，由map继承而来的有hashmap和treemap。简化框架图如下
collection接口方法：
List接口表示有序集合，集合中的每个元素都有对应的索引，通过索引来访问相应位置上的元素。
A.构造：由数组实现，默认初始容量为10，也可以用带参构造函数构造：ArrayList(int initialCapacity)。如果知道Arraylist的初始容量，最好构造初始容量，免得不断扩容影响性能。
B.扩容：每次扩容按1.5倍空间扩容，将原来的数组复制到1.5倍空间的数组，再把新元素添加到新空间中，由add(int)方法实现。
C.非线程安全，非同步，随机访问速度快。
A.实现：由双向链表实现
B.插入删除速度快，随机访问较ArrayList慢。
A.实现：和ArrayList相似，但是线程安全。即set,add,remove方法加了Synchronize同步关键字。
B.扩容时容量增长一倍
A.继承自Vector。
B.常用方法：push,pop,peek()返回栈顶元素。
集合元素不重复，可以有一个null值
A.底层由HashMap实现，元素值存储再key中，value值由一个统一的对象表示。
B.无序是指输入的顺序和输出的顺序不同，元素存储的位置是固定的。
基于LinkedHashMap实现，有序，非同步
有序，分为定制排序（自定义比较器）和自然排序（默认）。
A.实现：基于哈希表实现，key的哈希地址通过哈希转换函数得到数组中的索引，如果有冲突，则用单链表将哈希地址相同的元素串起来。有三种构造函数，分别可以定义初始容量（默认16）和负载因子（默认0.75）。它的底层数组长度为2的n次方（当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快），当数组元素大于threshold时，自动扩大一倍。
B.特点是适合快速查询。
C.常用方法：put(key,value),get(key)
自平衡的排序二叉树
1.红黑树的五个原则：
（1）节点要么为红，要么为黑
（2）根节点为黑
（3）叶子节点为黑
（4）红节点的子节点必须为黑节点（即路径上不能连续出现2个相同的红节点）
（5）从根节点到每个叶子节点的所有路径包含相同的黑节点
2.红黑树的插入主要解决的是红红结点问题（变色和左旋，右旋），删除解决的是黑黑结点问题。
A.底层实现基于红黑树，如put,delete()等方法。
A.跟hashMap差不多，都是基于哈希表实现。继承Dictionary实现Map接口。
B.不允许存在Null值（key和value）
C.同步，线程安全。
参考：
1.《集合框架综述》cnblogs.com/xiaoxi/p/6089984.html
2.《ArrayList扩容原理》https://www.cnblogs.com/SunArmy/p/9844022.html
3.《【Java提高十八】Map接口集合详解》https://mp.weixin.qq.com/s/AxvonTngTQjVVTU_Dtnx4w（讲的很详细，有源码分析）
