【ArrayList LinkedList Vector】
Vector对于ArrayList，因为同步而引起的性能差别并不明显；
LinkedList是循环双向链表，无论是否为空，总包含一个header表项：
|——————————————————————>
header ——> ele1 ——-> ele2 ——> ele3
<----- <----- <----
<—————————————————————-|
增加元素到表尾，ArrayList 优于 LinkedList：
ArrayList的扩容最终调用System.arraycopy()方法；
数组是连续的，ArrayList只有在扩容时才会低效一些；
而链表，虽然无须扩容，但新建对象和大量赋值操作会低效；
插入元素到任意位置，LinkedList优于ArrayList：
因为Array的连续性，每次插入操作都需要是数组重排；
LinkedList在任意位置插入和尾部插入是一样的；
删除任意位置元素，ArrayList尾部删除、LinkedList在头部删除和尾部删除这三个都是高效的，其他的都是低效的：
ArrayList任意位置删除需要重排数组；
LinkedList删除元素并不是从头到尾找，而是头尾分别找(循环双向链表)，所以只有中间元素的删除是低效的；
迭代器本质的遍历对于ArrayList和LinkedList来说效率是一样好的：
for-each本质就是迭代器实现，但如果不直接显式用迭代器，编译器将for-each转换为迭代器的时候总是不够聪明，导致for-each比迭代器性能略差；
随机访问遍历，ArrayList获得最高表现，LinkedList获得最低表现；
【HashMap Hashtable】链表root元素组成的数组
Hashtable和HashMap的性能几乎一样，差异有：
Hashtable是同步的，HashMap不是线程安全的；
Hashtable不允许key或value是null，HashMap允许；
Hashtable和HashMap的hash算法和hash值到内存的索引算法不同；
HashMap的底层存储就是个数组，hash值索引到内存地址就是索引到数组下标：
Object.hashCode是native方法；
通过将hash值和数组长度按位取与直接得到数组下标；
HashMap实际上是一个链表数组，每个数组元素又是个链表的root节点，hashCode冲突的项成链表存储：
Entry 1 | key
Entry 2 ——-> | value
… | next
Entry n | hash
Entry被存储在数组里，重复hashCode的Entry之间又是链表链接；
HashMap的高效源自对数组随机访问的高效，如果hashCode冲突越大，则HashMap越趋于几个链表，随机访问的性能低下；
判断hash冲突的条件：
e.hash == hash && (e.key == key || key.equals(e.key))
HashMap的容量参数有两个：数组长度和负载因子；
【负载因子】 = 元素个数 / 内部数组的总大小， 默认是0.75；如果元素个数超过了负载因子规定的阈值，则数组就会扩容；
存储同量的元素，负载因子越大，数组空间占用越小，hash冲突越明显；
【LinkedHashMap】此有序非彼有序：元素最后访问顺序和元素插入顺序
所谓的HashMap无序，是说元素插入HashMap之后，由于HashCode的无序映射，使得元素遍历结果的顺序和插入的顺序不一样，从这个有序的意义上说，ArrayList, Vector, LinkedList都是有序的；
而LinkedHashMap仅仅是实现了上述的有序，并不是TreeMap的自动排序；
LinkedHashMap有两种次序：元素最后访问顺序和元素插入顺序：
public LinkedHashMap(int capacity, float loadFactor, boolean accessOrder);
accessOrder == true: 元素最后访问顺序；
accessOrder == false: 元素插入顺序；
元素最后访问顺序对于缓存池淘汰元素很有意义，但要慎用，以防ConcurrentModificationException，因为LinkedHashMap.get()会引起元素重排序：
m = new LinkedHashMap<string, string="">(16, 0.75f, true);
m.put(“1”, “aa”);
m.put(“2”, “bb”);
m.put(“3”, “cc”);
Iterator iter = m.keySet().iterator();
while(iter.hasNext()) {
System.out.println(m.get(iter.next()));
}
【ConcurrentModificationException】 不能在迭代器模式中修改被迭代的集合，包括add(), remove(),和LinkedHashMap.get();
【TreeMap】 自动排序、按key范围筛选的SortedMap
TreeMap实现了SortedMap接口；
TreeMap的性能低于HashMap；
TreeMap是根据元素的固有顺序(Comparator和Comparable)而自动排序的，所以必须：
1， 构造 public TreeMap(Comparator<? super K> comparator);
或者
2, 使用实现了Comparable的key；
TreeMap基于红黑树实现，查找、插入、删除的复杂度是logN；
TreeMap不止自动排序这么简单，还能做范围筛选：
SortedMap<k,v> subMap(K fromKey, K toKey)
返回此映射的部分视图，其键值从 fromKey（包括）到 toKey（不包括）。
SortedMap<k,v> headMap(K toKey)
返回此映射的部分视图，其键严格小于 toKey。
SortedMap<k,v> tailMap(K fromKey)
返回映射的部分视图，其键大于或等于 fromKey。
【WeakHashMap】 缓存是可有也可无的
类结构：
Object —-> Reference
---> FinalReference default
---> SoftReference public
---> WeakReference public
---> PhantomReference public
局部变量是分配在栈上的，但局部变量指向的对象是分配在堆上的；
强引用的特点：
1， 可以直接访问目标对象；
2， 强引用所指向的对象一直都不会被GC，会导致OOM；(引用可达GC root的情况下)
3， 可能导致内存泄漏；
软引用：只在堆满的情况下被GC，不然可以一直存活；(引用可达GC root的情况下)；所以软引用适合用做缓存；
弱引用：只要系统GC了，就会被GC；弱应用也适合做缓存；
虚引用： 相当于没引用，作用在于跟踪垃圾回收过程；替代finalize进行资源清理；
Soft和Weak引用之所以适合做缓存，是因为它们所指的对象会分别在堆满和系统GC时就被回收，从而避免OOM；
缓存本来就是可有可无的对象，缓存中的数据丢了，还有候选方法，但如果缓存数据太大，内存就消耗太大；
HashMap常用做缓存，但内部实现是强引用，如果put的数据过多，势必造成内存负担；
WeakHashMap应用而生；
WeakHashMap并不是让系统随便GC自己所持有的key-value，这些key不是它私有的，它是通过WeakReference来引用的，但系统其他地方对这些key的引用可能是强引用；
假如WeakHashMap的key在系统内被强引用了，WeakHashMap就退化为HashMap；
XXXSet: 对XXXMap的封装
【HashSet】内部实现委托给一个HashMap对象；
【LinkedHashSet】内部实现委托给一个LinkedHashMap对象；
【TreeSet】内部实现委托给一个TreeMap对象；
特性和性能都一样。
【集合访问性能优化】
1，分离循环中重复调用的代码：
for(…; i < list.size();i++)中，size()方法被无辜多次调用；
2， 省略相同的方法调用；
3， 减少方法的调用：直接访问属性，而不是调用方法；
4， 判断是否继承了【RandomAccess】而区分使用遍历方法：
if(list instanceOf RandomAccess)
o = list.get(i);
else
o = iter.next();
ArrayList, Vector都是继承了RandomAccess的；
RandomAccess只是个标志接口，不要让链表实现的集合实现RandomAccess，会误导客户代码；
【Iterable】: 实现这个接口允许对象成为 “foreach” 语句的目标
此接口定义的一个方法：
Iterator<T> iterator()
返回一个在一组 T 类型的元素上进行迭代的迭代器。
所以说，几乎所有的集合类都得实现这个接口；
如果是自定义的Stack、Queue，最好都实现这个接口，因为抛开队列和堆栈本身的应用场景，这些数据结构本质都是集合，很多场景下，只要求按某种方式处理集合中的每个元素，就要求这种迭代式访问了。
foreach语句被编译成字节码之后，其实就是被转换成了一个迭代器的循环代码；
所以说，一个集合要使用foreach，必须实现Iterator，反过来，foreach也确实是被当做迭代器处理的；