源码阅读JDK8:java.util

AbstractList

1. 定义：public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

2. set、add、remove等修改方法直接抛异常不支持该方法，要想实现一个不可修改的集合，只需要继承这个类，并且实现get(int)、size()方法；要想实现一个可以修改的集合，必须重写set()方法，如果集合是可动态调整大小的，还必须重写add()，remove()方法；

AbstractMap

1. 定义：public abstract class AbstractMap<K,V> implements Map<K,V>，定义了Map的基本实现；

2. 只有一个抽象方法：entrySet，put方法不支持；

AbstractSet

1. 定义：public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>，没有抽象方法；

ArrayList

1. 继承AbstractList，实现List接口，内部使用数组Object[] elementData来存放数据，默认容量是10；

2. 扩容方法：ensureCapacity，每次扩1.5倍，add时通过ensureCapacityInternal方法扩容，实现一样；

3. clone通过Arrays.copyOf实现，remove、add(int index, E element)、sort等方法都利用了数组操作的方法；

4. transient Object[] elementData不能反序列化是出于性能考虑，因为数据中有空元素（数组容量大于实际元素个数），直接序列化会把空元素也序列化，所以实现了writeObject方法只把非空元素序列化；

5. modCount属性记录了list的变更次数（add、remove等），Interator迭代时通过判断modCount和过程中的modCount是否相等来判断是否修改了，使用一个简单的机制来规避风险；

LinkedList

1. 继承AbstractList，实现List接口，内部使用链表存放数据，内部维护Node类，存放每个节点的上一个和下一个节点；

2. add元素是放在链表末尾，删除、查询元素需要遍历整个链表；

HashMap

1. 继承AbstractMap，实现Map，初始化大小16，增长因子0.75，大小超过阈值（容量*增长因子）时将进行扩容，HashMap要求容量必须是2的幂；

2. JDK7的HashMap采用数组+链表实现，JDK8采用数组+链表+红黑树实现，当链表节点大于8转换为红黑树，小于6转换为链表，链表是为了解决哈希冲突，红黑树是为了提高性能；

3. resize扩容：容量大于当前容量*0.75时容量翻倍，使用新容量重新定义一个新的容器，将原来容器中的元素放入其中；

4. put：调用putVal，根据(n - 1) & hash算出所在桶，再放入对应的链表或红黑树中；

5. get：根据(n - 1) & hash找到第一个桶，再判断是链表还是树，再分别查找；

6. 内部也有modCount参数，和ArrayList的一样；

HashTable

1. 继承Dictionary，实现Map，初始大小为11，增长因子0.75；

2. get put方法都有synchronized修饰，是线程安全的；

HashSet

1. 继承AbstractSet，实现Set接口，内部使用Hashmap实现，相关方法都是调用HashMap相关方法实现，实现较简单；

LinkedHashMap

1. 继承HashMap，复用了HashMap的很多方法，并且未改变HashMap的存储逻辑，只是加了指针，把元素串联了起来，即LinkedHashMap=HashMap+双向链表；

2. 通过覆写了HashMap put中调用的子方法，每次插入元素是将元素放入自己维护的链表末尾来保证有序；（HashMap中的链表只是桶上的，只能保证桶内有序，不能保证所有有序）

LinkedHashSet

1. 继承HashSet，通过HashSet的构造方法返回LinkedHashMap来实现；

TreeMap

1. 基于红黑树实现，有序（基于key和Comparable排序），遍历速度较快；

TreeSet

1. 继承AbstractSet，基于TreeMap实现；

Vector

1. 继承AbstractList，实现List，基于数组实现，方法都加了同步，线程安全，实现原理类似ArrayList；

Queue

1. 接口，继承集合类；

Stack

1. 继承Vector，即使用数组实现，实现很简单；

SortedMap

1. 接口，继承Map；

WeakHashMap

1. 继承AbstractMap，实现Map，数据结构来说WeakHashMap与HashMap原理差不多，都是拉链法来解决哈希冲突；

2. Entry继承了弱引用Entry<K,V> extends WeakReference<Object>，每次resize等情况会清理引用；

SortedSet

1. 接口，继承Set；

Iterator

1. 接口，提供hasNext、next方法，不支持remove（throws unsupport）方法，需要实现类自己实现；

Comparator

1. 接口，主要提供compare方法，通过返回正数、0、负数分别表示大于、等于、小于；

Timer

1. 内部采用wait/notify机制来实现定时调度；

UUID

1. 内部使用SecureRandom生成随机字节再做一些转换；