ArrayList
ArrayList是实现List接口的动态数组。动态就是大小可变。默认大小10，当元素增加时，会检查容量是否需要增长，容量的增长会带来数组元素的重新拷贝。因此如果知道业务量的话，可以事先为ArrayList设置初始容量。
-
ArrayList是不同步的，线程不安全的
List list = Collections.synchronizedList(new ArrayList(…));
PS：HashMap也是不同步的，也可以使用Collections的synchronizedMap保持同步 底层用数组实现。
- 当直接添加元素时，会调用方法ensureCapacity(minCapacity+1)判断当前数量是否大于容量，是的话进行扩容，每次扩容容量变为原来的1.5倍
- 当在指定位置添加元素时，会右移index后面的所有元素，空出index的位置以供插入
- 当添加一个集合时，会扩充容量，并将新数组元素与旧数组元素合并构造成一个新的数组
- 删除指定位置的元素时，会将index后面的元素都向前移将所有元素紧凑，并将最后一位置空。
- 删除首次出现的指定元素，如果元素存在的话。分两种情况，一种是空元素，遍历并判断列表中第一次出现的空元素，并移除。另一种是非空元素，遍历列表，然后判断列表中的元素如果等于指定元素的话，则移除。移除的原理跟删除指定位置元素的原理一样，都是将index后面的元素向前移，并将最后一位置空。
- removeRange(int fromIndex, int toIndex)：移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。
将toIndex后面的所有元素移动到fromIndex后面，然后将空出的位置全部置空。 - 移除所有元素。是先获得集合的iterator，然后遍历移除
查找是先检查index的有效性，然后通过下标直接从数组里获取
LinkedList
LinkedList实现List接口，基于链表实现，允许所有元素包括null。
- LinkedList有两个基本属性size，header
- LinkedList内部有Entry类，包括元素节点Element E,下一个元素 Entry next,上一个元素Entry previous.是经典的双向链表的定义方式
- 构造空列表时，没有元素，仅将header的前一节点，后一节点指向自身
- 在指定位置添加元素（n>=1）时
先获取指定位置的entry successor，然后再获得这个entry的前一节点predecessor，这是为了修改相邻节点的指向
然后对要添加的元素集合(n>=1)进行遍历，先new一个新的节点，值是集合index下的元素的值，然后传入predecessor、successor，这个时候已经确定了新的节点的指向，一个指向predecessor，一个指向successor
然后将前一个节点predecessor的下一个节点next指向新的节点，这时，新的节点和它前一个节点的指向关系就确定了
接着，将新结点赋给predecessor游标，将插入元素的位置后移，保证后面节点的顺序是正确的
遍历结束后，将successor的前一节点的指向指向predecessor
到此，添加元素的节点的前驱后继都放置完毕 - 添加一个元素到末尾时，其实是添加到header的前面，因为其实LinkedList是双向的循环链表
添加时，将新结点的前驱指向header的前驱，后继指向header，然后在调整新结点前后节点的引用 - 移除首次出现的元素，如果存在的话。都是从header的下一个节点开始遍历的。LinkedList元素允许为空，故遍历时先判断Object是否为空，空看哪个值为空，不为空看是否equals.然后调用remove方法
- remove移除指定节点元素Entry时，将Entry前节点的后继指向Entry的后节点，将Entry后节点的前驱指向Entry的前节点。然后将节点的element，previous，next归空
Vector
继承AbstractList类，实现List接口。大小是可以增加或减小的。是同步的
- 初始容量10；capacityIncrement，向量的大小大于容量时自动增加的量，创建时指定
- 添加元素时，确认是否需要扩容。当添加后的长度大于容量时，进行扩容。若capacityIncrement<=0则扩容一倍，否则扩大capacityIncrement。最大值为2的32次方-1
然后将元素添加在末尾table[elementCount++] - 移除指定位置元素时。调用System.arraycopy将index后面所有元素向前移动一格，之后将最后的位置置空
- Vector实现4种遍历。随机访问get，迭代器iterator，for，Enumeration
Stack
继承Vector类，实现类都在Vector。仅有一个构造方法，5个实现方法empty(),peek(),pop(),push(E item),search(Object o) (查找o在栈中的位置，由栈顶往栈底数，基数1)
HashMap
继承AbstractMap，实现Map接口，以key-value的形式存在
- 有两个重要的属性：初始容量、加载因子。默认初始容量是16，加载因子0.75。当达到极限容量(初始容量*加载因子)，就会扩容。最大容量为2的30次方
- 对于使用链表发的散列表来说，查找一个元素的平均时间是O(1+a)
底层的实现是数组，数组的每一项都是一条链 - put元素的时候，先判断key是否为null，是的话调用putForNullKey方法，不是的话计算key的hash值，根据hash值确定在数组中索引的位置。如果该元素有位置，则判断是否存在相同的key，相同的话用新值覆盖旧值，不同的话将该元素保存在链头（最先保存的元素是在链尾）。如果该元素没有位置，则直接保存
- 底层数组的长度总是2的n次方，这是因为底层对容量进行扩容是用左移的操作<<=1，并且能提高效率，并且2的n次方不容易发生碰撞
计算出hash值后，为保证索引位置的均匀分布，是采用取模的操作。h&(length-1),这样提高了速度 - 当添加新的对象Entry的时候，如果bucketIndex处有对象，则将添加的新Entry对象指向原有的Entry对象，形成一条新的链。如果原来bucketIndex处没有对象，也就是e=null，则新Entry指向了null。这是非常优雅的设计
- 当扩容的时候，就是在临界点=初始容量*加载因子的时候，需要重新计算这些数据在新的table中的位置并进行复制处理，因此是一个非常耗时的操作，故如果知道初始的业务量，可以先设置一个初始值。
- HashMap的迭代器(Iterator)是fail-fast迭代器，是快速失败的。在进行迭代操作时，若有其他线程对其进行结构上的改变，会抛出ConcurrentModificationException异常
HashTable
继承Dictionary类，实现Map接口
- 默认容量11，加载因子0.75
- 利用一个与实例有关的随机值hashSeed，与hashCode进行异或运算，计算出hash值，解决hash冲突
- 添加元素的原理与HashMap一致
put添加Entry元素的时候，会检查是否达到阀值，是的话进行扩容操作，新容量=旧容量*2+1 (oldCapacity<<1+1).
然后重新计算hash值，重新确定元素在新数组中的索引位置，并将原来的元素拷贝到新的数组中 - 获取元素时就是计算key的hash值，确定索引位置，然后迭代该位置上的链表，匹配找到对应key的value
- HashTable的key和value都不可以为空，而HashMap的key可以为空，并且可以存在多个value为null
- Hashtable的enumerator迭代器不是fail-fast的
- HashTable是同步的，HashMap不是
HashSet
继承AbstractSet类，实现Set接口
- 基于HashMap实现，大多数方法又HashMap实现，初始容量16，加载因子0.75
- iterator调用HashMap的KeySet返回了所有的Key
- 用key存储值，value都是PRESENT，一个Object类型的固定值.static final