Java 集合框架

1.关于容器

容器就是可以容纳其他Java对象的对象，Java Collections Framework(JCF) 提供了通用的容器

优点是：

降低编程难度和学习难度，提高程序性能

增加程序的重用性

提高API之间的互操作性

Java容器中只能放对象，对于基本类型要把其包装成对象(包装类)才能放到容器里

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

2.Collection

Set:无序，唯一

Set继承Collection接口，是一个不允许出现重复元素，并且无序的集合，主要有TreeSet和HashSet。

在判断重复元素时，Set集合会调用hashCode()和equal方法实现。

TreeSet

基于红黑树实现，每一个元素都是树中的一个节点，插入的元素都会进行排序。查找效率不如HashSet，HashSet查找时间复杂度为O(1),

TreeSet查找时间复杂度为O(logN)。

HashSet

哈希表结构，支持快速查找。主要利用HashMap的key来存储元素，计算插入元素的hashCode来获取元素在集合中的位置。失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的

HashSet底层由HashMap实现，插入元素被当作是HashMap的key，根据hashCode值来确定集合中的位置，由于Set集合中并没有下标的概念，所以并没有像List一样提供get（）方法。当获取HashSet中某个元素时，只能通过遍历集合的方式进行equals()比较来实现。

如果你知道是Set，但是不知道是哪个Set，就用HashSet。

LinkedHashSet

具有HashSet的查找效率，且内部使用双向链表维护元素的插入顺序

List:有序，可重复

ArrayList

基于动态数组实现，支持随机访问。

查询快，增删慢；线程不安全，效率高

如果你知道是List，但是不知道是哪个List，就用ArrayList。

Vector

和ArrayList类似，但他是线程安全的，效率低

LinkedList

基于双向链表实现，只能顺序访问，但是可以快速地在链表中插入和删除元素。不仅如此，LinkedList还可以用作栈，队列和双向队列。

查询慢，增删快；线程不安全，效率高

3.Map

Map接口有三个比较重要的实现类，分别是HashMap、TreeMap和HashTable

TreeMap

基于红黑树实现，有序

HashMap

基于哈希表实现，线程不安全，效率高。如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap

HashMap允许null值（key和value都允许）

现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁

HashTable

和HashMap类似，但他是线程安全的，Hashtable不允许null值

问题分析

(一) TreeSet，LinkedHashSet和HashSet的区别

相同点：都实现Set接口，三者都不是线程安全的，如果要使用线程安全可以使用Collection.synchronizedSet()

不同点：HashSet插入数据最快，其次是LinkedHashSet，最慢的是TreeSet因为内部实现排序

​ HashSet不保证有序，LinkedHashSet保证FIFO即按插入顺序排序，TreeSet按照内部规则排序，也可自定义排序规则

​ HashSet和LinkedHashSet允许存在null数据，但TreeSet中插入null数据时会报NullPointerException