Linkedlist
1.extneds AbstractSequentialList, implements List<E>, Deque<E>, Cloneable, java.io.Serializable ,element,peek
2.双向链表，header链表头，size大小
3.按下标访问元素—get(i)/set(i,e) 遍历链表将指针移动到位(如果i>数组大小的一半，会从末尾移起)，
get set 优化后的线程时间O(n),add,remove，只需要改变指针
4.相对于arraylist需要更耗内存，创建Entry对象
ArrayDeque
1.基于动态数组实现的，双端，双端指针
HashMap
1.继承abstractMap,实现Map,Serializable,Cloneable，序列化通过，writeObject,readObject 方法实现
2.先线性安全，默认容量和加载因子16，0.75，数组resize为原来的两倍，伴随着rehash操作，支持键值null，key为null,存储在第一个bucket中
3.链表法解决哈希冲突，
4.通过modcount成员变量支持fail-fast规则,迭代器抛出ConcurrentModificationException异常
5.get put, put 根据k的hashcode值确定 数组下标，再根据k.hashcode,k比较，是否相同，相同则返回旧值，否则新增，再判断是否超过阈值，超过容量变为两倍
6.indexFor(hash, table.length)按位与 数组长度&
hashCode是native方法，对每一个不同的java环境来说，同一个key所计算的hashCode是不相同的，所以反序列化后table的index会发生变化，无法还原
HashMap的bullet存在null数据，如果对这部分数据进行序列化则造成不必要的资源浪费。
transient使用小结
- transient关键字只能修饰变量，变量如果是用户自定义类变量，则该类需要实现Serializable接口。
- 被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。
总结
- 当父类继承Serializable接口时，所有子类都可以被序列化。
- 子类实现了Serializable接口，父类没有，父类中的属性不能被序列化（不报错，数据不会丢失），但是在子类中的属性仍能正确序列化
- 如果序列化的属性是对象，则这个对象也必须实现Serializable接口，否则会报错。
- 在反序列化时，如果对象的属性有修改或删减，则修改的部分属性会丢失，但不会报错。
- 在反序列化时，如果serialVersionUID被序列化，则反序列化时会失败
- static,transient修饰后的变量不能被序列化
与hashTable区别
- HashMap非线程安全的，并可以支持键值为null，而Hashtable非线程安全的，key和value都不能为null
- Hashtable和HashMap默认的容量和resize方式不同。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
- hashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器。
HashMap可以通过下面的语句进行同步：Map m = Collections.synchronizeMap(hashMap);
LinkedHashMap
1.继承HashMap,实现Map接口
2.通过hash表加双向链表实现，依靠着双向链表实现迭代顺序为插入顺序或者访问顺序，倒序；LRU缓存，先线性安全
package collections;
import java.util.Map;
public class LRUCache {
private int capacity;
private Map<Integer, Integer> cache;
public LRUCache(final int capacity) {
this.capacity = capacity;
this.cache = new java.util.LinkedHashMap<Integer, Integer> (capacity, 0.75f, true) {
// 定义put后的移除规则，大于容量就删除eldest
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
if (cache.containsKey(key)) {
return cache.get(key);
} else
return -;
}
public void set(int key, int value) {
cache.put(key, value);
}
}
Collections.sort()
加强型归并排序