Collection

Collection接口是所有集合的根接口。它的两个重要子接口分别为List，Set。

List 列表

List接口的实现类集合的元素均是有序、可重复的。

ArrayList

特点：

线程不安全
允许元素为null。
底层数据结构为Object[]数组，初始容量为10，加载因子为1，扩容增量为0.5倍。
增删操作慢，查找快。
支持快速随机访问。

LinkedList

特点：

线程不安全
允许元素为null。
底层数据结构为双向链表，无初始容量，只需在链表尾部添加新结点即可。
不支持快速随机访问。
增删操作快，查找慢。

Vector

特点：

允许元素为null。
线程安全，每个方法都加了synchronized修饰符。
底层数据结构为Object[]数组，初始容量为10，加载因子为1，默认扩容增量为1倍

ArrayList与Vector的区别：

Vector所有类的方法都是同步的，可多个线程安全的访问同一个Vector对象，但单线程访问将会在同步操作花费大量时间。
ArrayList不是同步的，所以不需要保证线程安全时可优先使用ArrayList。

Set 集合

Set 接口的实现类集合的元素均是不允许重复的。

键一样，值不一样会被后来的值覆盖。键不一样，值一样是可以的。

HashSet

特点：

无序
线程不安全
允许null元素
底层实现为HashMap<E,Object>，加载因子为0.75,初始容量为16,扩容增量为1倍。

TreeSet

特点：

有序
线程不安全
不允许元素为null
底层实现为TreeMap<·E,Object>，TreeMap底层数据结构为红黑树。

Map

Map是一个双列集合，是所有Map集合的父接口

HashMap

特点：

允许元素为null
线程不安全
底层实现为Map.Node<K,V>，数据结构为拉链表，即链表+数据。
默认加载因子为0.75，可自己设置加载因子。默认初始容量为16, 长度始终保持2的n次方，扩容增量：1倍

HashMap底层实现：

// HashMap中的属性table 数据结构为拉链表（数组+链表）
transient Node<K,V>[] table; 

// HashMap中的静态内部类Node<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

可以看到table属性是Node<K,V>类型的对象，Node <K,V>又是一个链表的数据结构，故 table数组的

每个元素都是一个链表的头结点，请看图示。当链表中的个数超过8个时，会转换为红黑树，以减少搜索时间。

HashTable

特点：

不允许元素为null
线程安全，使用synchronized修饰了方法。
底层实现为HashTable.Entry<?,?>[]，数据结构为链表
默认加载因子为0.75，可自己设置加载因子。默认初始容量为11, 扩容增量：1倍 + 1

TreeMap

特点：

允许元素为Null
线程不安全
底层实现为TreeMap.Entry<K,V>，数据结构为红黑树。