Java集合框架

java.集合

Java的集合类主要是两个接口派生而成：Collection接口和Map接口。它们两个都是根接口，这两个接口又包含了一些子接口和实现类。这两者有什么不同呢？很简单，Map这一派的弟子都是双元素的，而Collection这一派的弟子都是单元素的。

Collection接口

下面是Collection接口的继承树：

Set接口和List接口是Collection接口派生的两个子接口，它们分别代表了有序集合和无序集合。这里的有序值得说明一番：所谓有序，指的是哪个元素先进去的，那么哪个元素就先出来，就是这样，不会乱套的。List接口是有序的，而Set接口是无序的。它们两者的不同还在于：List接口允许集合里有重复元素的存在，而Set接口下不允许重复元素存在。一般情况下把Queue算在了List门下。

Set集合

HashSet TreeSet EnumSet三个实现类。三个小家伙各有特色。

HashSet类：

不能保证元素的排列顺序，元素输入输出顺序可能不一样；
HashSet不是同步的，如果需要多线程操作，必须通过代码来保证其同步；
集合元素值可以为null；

关于hashCode()方法，之前也专门提及到。下面是专门给出的重写hashCode()方法的基本规则：

1.在程序运行过程中，同一个对象多次调用hashCode()方法应该返回相同的值；
2.当两个对象通过equals()方法比较返回true时候，这两个对象的hashCode()方法也应该返回相等的值；（老子都判定这两个对象是相等的了，小的竟然敢来说不是相等？找死！ 最好的办法是：在老子判定这两个对象是否相等的时候，先问一下小的：你认为他们是否相等啊？ 在小的给出肯定回答的时候，老子再来进一步判定这两个对象是否相等）也就是equals()方法比较的过程必须有hashCode()方法的一份子。

HashSet类还有一个小弟：LinkedHashSet。小弟自然是跟着老大混的，它也是根据元素的hashCode值来决定元素的存储位置，但它同时还使用链表维护元素的次序：HashSet不是不保证元素的排列顺序么（输入输出顺序不一致），那么小弟就很会做人啊，老大做的不够的，小的补上，保证输入输出顺序一致！（怎么输入，就怎么输出！先入先出哦）

TreeSet：

TreeSet可以确保元素处于排序状态。屌不屌！我也和HashSet一样，不保证元素的排列顺序（输入输出顺序不一样），但是，在我这里，小要有小的样子，老要有老的样子，一切按照规矩来！
怎么实现的呢？各有各的招啊，HashSet使用hash算法来决定元素的存储位置，而TreeSet采用红黑树的结构来存储元素。有自然排序、定制排序两种。默认的自然排序是按照升序排列。

说到排序，必须得有个比较的方法，你说你大，你就是大呀，咱两比比才知道谁大谁小呀。既然TreeSet类敢向外宣称一切都要有规矩，那么它自然已经定下来怎么个比较法的啦，每个集合元素中都有compareTo(Object obj)方法，TreeSet就是通过这个来比较元素之间的大小关系的。

当然，你也可以自己重写这个compareTo(Object obj)方法，不同元素，你爱怎么定义就怎么定义。默认的自然排序不是按照升序排序的么，你就来一个按照降序排序，不也可以么。对吧！

EnumSet

EnumSet这个小家伙我不怎么熟悉啊，感觉像是个少数民族姑娘似的。对的，EnumSet是一个专门针对枚举类设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值。

算啦算啦，跳过吧，小姑娘，有缘我们再来相遇。

各个Set实现类的性能比较

HashSet和TreeSet是Set的两个典型实现，到底如何选择HashSet和TreeSet呢？HashSet的性能总是比TreeSet的性能要好，因为TreeSet需要额外的红黑树算法来维护元素集合的次序。只有当一个需要排序的Set时候，才应该使用TreeSet，否则都应该使用HashSet.

必须指出，这三个实现类都是线程不安全的哦。如果有多个线程同时访问一个Set集合，那么就应该手动修改该Set集合，以保持Set集合的同步性。一般情况下，通过使用Collections工具类中的synchronizedSortedSet方法来包装这个Set集合。

List集合

List集合的最大特点是：有序、可重复。可以通过索引来查找，于是乎有了很多与索引(index)相关的操作：

它有很多个小弟：Vector、ArrayList、LinkedList以及Queue(如果把它也算进来的话)。

让我们来分析分析这些小弟有什么不同啊：

Vector

Vector类是一个元老级别的集合了，当年JDK1.0的时候老子横闯天下风光无限的时候，你们这些小家伙还不知道在哪里呢。确实很屌是不是，家有一老就是家有一宝啊。但是，这个老家伙呢也有很多老家伙的确定：各种方法的名称很长，使用起来不方便；同时老家伙是比较严谨的，它是线程安全的。但是线程安全的问题大家也知道，速度就慢下来了。有得有失嘛

ArrayList

现在可是快发展时代了，总不能一直依靠着Vector吧，List集合里面于是乎有了ArrayList这个小弟。他和Vector可谓是师出同门啊，但是长江后浪推前浪，他比Vector更加适应这个社会：它的名字很短，方便使用，同时它不是线程安全的，于是乎它很快。更多的情况下，它们两者并没有很大不同，都是顺序存储结构嘛。

问：Vector和ArrayList是如何实现动态空间分布的？这个想要问的是如何实现动态增长的吧。实际上ArrayList和Vector都是基于数组实现的List类，所以ArrayList和Vector类封装了一个动态的、允许再分配的Object[]数组。当向ArrayList和Vector添加元素的时候超过了该数组的长度时，他们的initialCapacity会自动增加。默认的数组长度为10.（Vector增长原来的一倍，ArrayList增加原来的0.5倍）

LinkedList

LinkedList是另外一个派系的小弟，它集各家所长，可以作为List集合来用（实现了List接口），可以当做双端队列来用（实现了Deque接口），于是乎可以作为队列也可以作为栈咯。

更重要的一点是：LinkedList内部是以链表的形式来保存集合中的元素。

关于ArrayList与LinkedList的区别，可以查看更详细的资料。你应该做了笔记的对吧，嘻嘻~

Queue集合

|-PriorityQueue
|-Deque
--- |-ArrayDeque
--- |-LinkedList

各种List的性能分析

ArrayList和LinkedList是线性表的两种典型实现：基于数组的线性表以及基于链表的线性表。
关于使用List结合的建议：
1.如果需要遍历List集合元素，对于ArrayList Vector这一类数组性质的集合，应该使用随机访问方法（get）来遍历集合元素，这样性能更好。对于LinkedList集合，应该采用迭代器来遍历集合元素。

Map

好了，唠叨完了Collection这一家子，让我们来看看Map体系下面的各个小弟到底怎样。Map体系相对而言比较简单：

Map用户保存的是具有映射关系的数据，因此Map集合中存储的总是一对数值，称为键值对< key,value>。Map的key不允许重复，和set集合中不允许元素重复非常类似。其实啊，可以将set集合看成是特殊的Map集合，这样是合理的（实际上在底层实现的时候，通过包装一个所有value都为null的Map集合实现了Set集合类）。你来看，它们的相似性：
Set: HashSet LinkedHashSet SortedSet(接口) TreeSet EnumSet
Map: HashMap LinkedHashMap SortedMap(接口) TreeMap EnumMap

是不是真的很像啊。其实啊，如果将Map里面的key集合单独提取出来，它就是一个Set啊。

Hashtable与HashMap的区别
这个Hashtable啊，它其实和Vector是同一个时代的人，都是JDK1.0时候就有的一员风光无限的老将了(你看看它的名字，都没有完全依照如今的java命名规则来的呢，多早的一代人啊)，以前还没有Map这个接口呢，他就已经存在了。你说它屌不屌。但是

但是来了，它和Vector一样，都有同代人的明显的特性：做事严谨，功夫扎扎实实，线程安全但是速度慢。同样的，它不允许key value 中出现null值。大丈夫怎么可以null呢

哈哈，时代唤英雄啊，和ArrayList一样，HashMap也应时而生，它更好地适应了这个社会，它不是线程安全的，速度快。它允许key value 中出现null值。大丈夫能屈能伸啊~
（key只能有一个null，而value则可以有多个null）