Java 集合总结
集合类关系图
1. List
ArrayList和LinkedList
ArrayList：:类似数组的形式进行存储，因此它的随机访问速度极快。不适合于在 线性表 中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。
ArrayList是 线程 不安全的，默认长度为10，扩展方式为旧容量* 3 / 2 + 1;
LinkedList：适合于在 链表 中间需要频繁进行插入和删除操作。 随机访问速度较慢。查找一个元素需要从头开始一个一个的找。LinkedList和ArrayList一样也不是 线程安全 的。LinkedList实现了接口Dueue，所以LinkedList可以被当做堆栈来使用。
2. Set
Set接口区别于List接口的特点在于:
Set中的元素实现了不重复，有点象集合的概念，无序，不允许有重复的元素,最多允许有一个null元素对象。
Set中元素虽然没有顺序，但是元素在set中的位置是有由该元素的 hashCode 决定的，其具体位置其实是固定的。
常见实现类有HashSet,LinedHashSet和TreeSet
1. HashSet
HashSet是Set接口的最常见的实现类了。其底层是基于Hash算法进行存储相关元素的。底层是基于hastMap实现。
2. LinkedHashSet
LinkedHashSet 继承于hastSet,实现set 接口。默认容量为16. 其底层是基于LinkedHashMap来实现的, 和HashSet主要区别在于LinkedHashSet中存储的元素是在哈希算法的基础上增加了链式表的结构。
3. TreeSet
TreeSet是一种排序二叉树。存入Set集合中的值，会按照值的大小进行相关的排序操作。底层算法是基于 红黑树 来实现的。
TreeSet和HashSet的主要区别在于TreeSet中的元素会按照相关的值进行排序。
TreeSet和HashSet的区别和联系
1. HashSet是通过 HashMap 实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key
2. Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.
3. hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.
a. hashCode是用来计算hash值的,hash值是用来确定 hash表 索引的.
b. hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象
才可以真正定位到键值对应的Entry.
c. put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value
4. 由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.
a. Comparator可以在创建TreeMap时指定
b. 如果创建时没有确定,那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口.
c. TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了.
3. Map
Map接口实现的是一组Key-Value的键值对的组合。 Map中的每个成员方法由一个关键字（key）和一个值（value）构成。Map接口不直接继承于Collection接口。
1. HashMap
HashMap实现了Map、CloneMap、Serializable三个接口，并且继承自AbstractMap类。默认初始容量为16;
HashMap基于hash数组实现，若key的hash值相同则使用链表方式进行保存。
类内还存在一个内部类Entry，用于链表的存储。
2. LinkedHashMap
LinkedHashMap继承自HashMap并且实现了Map接口。和HashMap一样，LinkedHashMap允许key和value均为null。
线程不安全的，如多线程中使用，那么需要使用Collections.synchronizedMap方法进行外部同步。
3. Hashtable
Hashtable实现Map接口，继承自古老的Dictionary类，实现一个key-value的键值映射表。Hashtable不允许键和值为null。
HashMap与Hashtable的区别：
1. Hashtable是基于陈旧的Dictionary实现的，而HashMap是基于Java1.2引进的Map接口实现的；
2. Hashtable是线程安全的，而HashMap是非线程安全的，我们可以使用外部同步的方法解决这个问题。
3. HashMap可以允许你在列表中放一个key值为null的元素，并且可以有任意多value为null，而Hashtable不允许键或者值为null。
