集合框架
这是从博客找的一张集合框架图片，从上向下可以看到Map和Collection处于类的顶端，并且支持Iterator（迭代器）。迭代器主要用途是遍历集合中的元素，比较有趣的是遍历好手for each语句也是转换成对iterator.next()和iterator.hashNext()方法的调用，算是对Iterator语句的一种封装。迭代器和foreach中进行remove/add操作好像比较迷，暂时还没搞懂。
集合框架
Collection
Collection有两个子类，分别是List和Set。List约定是有序且可重复，Set约定是无序且不允许重复。
List
主要说一下ArrayList，下图是ArrayList源码注释首段。大致上翻一下，值得注意的是段首的Resizable-array讲出了ArrayList的本质上是可调整大小的数组。ArrayList本身实现了List的接口,实现所有可选list操作，也允许null存在。除此之外，ArrayList还提供了可以改变内部存储元素的size的方法。它和Vector很相似，但本身存在线程不安全性。
ArrayList源码首段
看完源码很容易有一个问题，数组本身是不可扩容的，ArrayList是如何实现扩容的？
在你使用add()方法时，会先调用ensureCapacityInternal(size + 1)方法确定添加元素后的minCapacity值。得到minCapacity值后会进行判断现有的size和的minCapacity之间的大小关系。如果现有size不能确保加入新元素。就会进行扩容操作，具体是新建一个数组，使其size变为原本的1.5倍，再于minCapacity进行比较并取高值作为新数组容量。最后将原数组拷贝进入新数组。（旧数组就在薛定谔被删除状态）
Set
Set的约定就是不允许有重复元素且无序，判断重复使用的是equals约定。
* 如何实现set的约定呢？
按照顺序判断新加入的元素是否contains原数组，如果不，就add，否则返回。假设一组足够大的完全不重复的数组样本，判断次数就是等差数列求和，难度与样本数量是正向二次关系。
* 那么如何高效实现set的约定呢？
在此之前，我们先聊一下HashCode。
HashCode
如果说equals约定是JAVA中第一重要的约定，第二重要的就一定是HashCode。
Object是所有class的源头，其中有就有HashCode方法，即返回当前对象的一个int型的HashCode值。约定如下：
* 同一个对象必须返回同一个HashCode
* 两个对象equals返回true ，必须相同的HashCode
* 两个对象不等，也可能返回同一个HashCode
也就解释了override，equals时会连带有Hashcode方法重载。因为其本身是int型，具有最大值，而Object可能不止21亿多，所以本质是从对象到HashCode的单向映射。
再说回HashCode高效实现Set的约定的方法，首先想象有很多的hash桶，每个hash桶有自己的HashCode。对object处理前先实现HashCode方法，根据HashCode匹配hash桶，新加入的元素不需要每个对象都要比较，先去根据HashCode找hash桶，再在桶内比较。
结论就是hash桶的数量和元素总量及分布决定了HashCode算法的效率倍数，即桶数目越多，元素样本越大，分布越均匀，效率越高。
基于这个原因我们可以使用HashSet对ArrayList进行去重操作。需要注意的是，HashSet本身是无序的，如果对顺序有需求可以使用LinkedHashSet,它的顺序是元素插入顺序。
Map
MAP是从key键映射到值的映射，一个map不包含重复的key，每个键最多映射一个value。按照我的理解，和高中数学中常见X/Y坐标系中的函数很像，除了圆锥曲线，一般x作为定义域，y作为值域，一个y肯定是存在一个x映射，每个x最多只能映射一个y，不同x映射y可能相同。即x为key，y为value。
HashMap是最常用，最高效的Map实现,下图是其源码首段，试着解读有利于加深对HashMap的理解。
这是Map接口基于Hash表的实现，此实现提供所有可选的地图操作，允许存在null value和null key。HashMap和Hashtable大致相似，不同点在于HashMap允许null存在和线程不安全性。它无法保证Map其中的有序性，并且随着时间推移，现有顺序也不保证恒定不变。
HashMap源码首段
源码中提到HashMap是无序的，其key对应的HashSet也是无序的，两者其实背后是同一组数据，也就是说对其中一个的修改就是对两个的修改。如果对顺序有需求的话，可以使用TreeMap，本身具有有序性。
另外一点就是HashMap和ArrayList都提到线程不安全性。ArrayList是线程非安全的，因为ArrayList中所有的方法都不是同步的，在并发下一定会出现安全问题。HashMap也是类似，在多线程同时使用put操作时很可能造成数据丢失，在多线程扩容resize过程中也可能条件竞争，形成死循环的链表，多线程下可使用ConcurrentHashMap。
HashMap的扩容
上面提到的resize，是用来实现HashMap的扩容。当新的元素不断加入时，Map的饱和度会慢慢升高。Key映射位置发生冲突的几率会逐渐提高。达到一定负载是，HashMap需要扩展它的长度，也就是resize。
1. 创建一个新的Entry空数组，长度是原数组的2倍
2. 遍历原Entry数组，把所有的Entry重新Hash到新数组
在Java7之前，假设不论是被攻击还是巧合，不同对象拥有相同的HashCode的数据会导致少数hash桶被绝大多数元素使用，无法高效应用其他绝大部分hash桶，会丧失hash算法带来的速度优势，类似于降维成list。
而同一Hash桶中的数据结构是链表，这种情况下会大大增加运算时间和负载。在Java7之后这种碰撞由链表结构变为红黑树，其优势就是把链表的线性运算时间变为对数时间。
最后，Collection作为Java数据类型中重要的一环，其本身的方法很强大。并且有更强大的Guava可供使用，拥有更多更全面的类库，当需要一个Collection相关的方法时，不妨去其中搜索。
