Java集合框架之Collection集合

http://www.leocook.org/category/#java

Java的集合框架分两大系Collection系和Map系，之所以要分开是因为Collection内存储的是线性集合，而 Map的元素是以键值对（Key-Value）的形式存的。其实Map和Collection内部实现是存在联系的，学完就懂了。本文主要介绍的 Collection中常用的集合的用法以及之间的区别。

一、引言
Java集合框架和IO框架一样， 看似很庞杂的 体系框架，但是当你逐一 深入每个集合的用法后，就能明显的看出他们之间的区别和联系。最后拎出一个框架图，就一目了然了。由于Java的集合框架分两大系Collection系 和Map系，之所以要分开是因为Collection内存储的是线性集合，而Map的元素是以键值对（Key-Value）的形式存的。其实Map和 Collection内部实现是存在联系的，学完就懂了。本文主要介绍的Collection中常用的集合的用法以及之间的区别。

二、Collection集合框架介绍
下 面这张图，是Collection框架的类图，中间省略的几个无关紧要的类，整体还算详细。斜体加粗表示接口（规范的类图应该是加上

Java集合框架之Collection集合

Collection接口是根接口，Iterable接口可以简单理解成标记接口，它约定了所有线性集合（数组、队列、栈都属于线性集合，Map是二维集合不能直接遍历）都必须可以遍历，同时也定义了hasNext()、next()、和remove()三个遍历方法， 后 边还会详细讲到。从根接口派生出两个子接口Set和List，分别作为Set集合和List集合的根接口。最后是五个常用的集合类HashSet、 TreeSet、LinkedList、ArrayList、Vector。不过从类图中发现每个集合接口都有一个抽象的实现类，而且每个最终集合类同时 继承了抽象类和实现了集合接口。 例如：ArrayList extends AbstractList implements List， AbstractList本身就已经实现了List接口，这里再写implements List是为了使整个集合框架结构更清晰，很多集合框架图为了看着方便都省略了实现接口这条虚线，但是我觉得需要解释。

Set和List具体有什么区别呢，我们先来看下面这张Collection、List和Set的类图。List接口的类图中只列出特有的方法，从 Collection中继承的方法没有重复列举。为什么没有Set接口？Set接口中的方法和Collection完全一样，没有增加任何新的方法，就不 再重复画图了。Set再重复定义一遍Collection接口中的方法，一是为了作为类库要添加属于Set的特有方法约定，虽然方法定义相同，但是具体方 法实现是不同的，例如Set的add方法不能添加重复元素，List则可以；二是为了让集合框架结构更清晰。

Java集合框架之Collection集合

主要区别：

1、List必须是有序集合，Set可以有序也可以无序，这里的有序无序是指集合内部的存储顺序是否和元素的添加顺序相同。其实Set接口注释中并没有特 别说明Set就应该是无序的，但也没有像List接口一样开始就声明“An ordered collection ”，但是在Set集合的iterator()方法注释中有这样一句话：The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee).结论就是Set的实现类也可以有序。

2、List允许有重复元素，更确切地讲，List允许满足e1.equals(e2)的元素对e1、e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。而Set集合不允许有重复元素，如果允许有null值，最多只能有一个null值。

3、List能对元素精准定位，可以根据元素下标对任意位置的元素实现增删改查。索引下标和数组一样从0开始。例如List接口中定义了 add(int index, E element)、get(int index)、set(int index, E element)等可以访问指定位置元素的方法。Set只能对集合遍历而不能进行随机访问元素。

把List都放在前面说，好像List要比Set优秀似得，并非如此，各有优势，下面详细对5个集合类详细比较 。

三、Collection集合类的实现原理和具体区别
1、ArrayList

ArrayList是比较常用的一个集合，之所以叫数组列表是因为其底层是用数组实现的，数组我们熟悉啊，那就先来看一下数组有什么特点吧。如果是对象数 组，元素可以为null，元素可以重复N次，可以用元素下标访问任意位置（不要越界），而这些现在都成了ArrayList的特点。数组还有一个大特点就 是查询速度很快，这里说一下数组的寻址方式。当创建一个数组时，会在内存中分配一段地址连续的空间，数组名就是这块内存空间的首地址。比如int[] arr=new int[10]; 假设首地址是22005，int[3]就是访问第4个元素，其地址是22005+4*sizeof(int)，int大小为4，那么结果就是 22005+4*4=22021，直接去222021这个位置区拿数据就行了。很明显，数组是直接寻址，查找速度相当快。但是如果根据内容查找，就只能遍 历数组了，ArrayList有些个方法indexOf(Object o)、lastIndexOf(Object o)、remove(Object o)都是遍历数组查找元素的，如果数据量很大的话，经测试，性能有所下降。简单点理解就是，ArrayList就是数组的一个封装类，能用数组的地方都能 用它。最后说一下，ArrayList内部数组的增长策略是oldLength>>1，每次增长原来的一半的说法并不准确。

2、LinkedList
LinkedList内部是一个双向链表，学过数据结构的都知道双向链表，删除添加很方便，直接修改前后两个元素的指针就搞定了。 所以LinkedList中提供了很多方便双向增删元素的方法，下面看一下其类图，只列举了LinkedList中特有的方法。

Java集合框架之Collection集合

可以看到有很多类似xxxFrist()和xxxLash()的方法，这真是充分发挥了双向链表的作用。有了这些方法就可以将链接列表用作堆栈、 队列或双端队列。例如操作堆栈用pop()弹出最上面的元素，push()压入栈。其实这些方法只是用户接口，仅仅是换了换方法名字，其中道理看下源码便 知。

java”>
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public E peekFirst() {
final Node f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node l = last;
return (l == null) ? null : l.item;
}
public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}
可以看到方法调来调去最后就是在访问链表头尾的元素。这也给我们一个提示，好的代码方法命名真的很重要！这些方法都是在LinkedList中单独定义 的，所以想用这些方法，就不能用多态的方式去创建对象,如List list=new LinkedList();这样只能调用List中定义的方法。链表还有一个很坑的特点就是，如果要找一个元素每次都要遍历一下链表，查找速度略慢。另外 Linkedlist使用了一个特殊的迭代器listIterator，也是其特有的，这个迭代器的特殊之处就是可以从双向迭代，即可从前往后迭代也可从 后往前迭代，其实现还是要依赖于双向链表，使用比较方便，应该记住。

3、Vector

Vector是从JDK1.0就有了，它是集合框架在JDK1.2出现后才加入到集合框架的，所以这个Vector很古老了，其功能和 ArrayList基本一样，内部也是数组实现。唯一不同就是Vector是线程同步，Arraylist线程不同步。这里不再赘述了，此类已基本弃用！

4、HashSet

Set集合的特点就是无重复元素，那么HashSet是怎么实现元素的唯一性呢？通过比较hashcode和equals，如果hashcode相同，才会继续比较equals，如果hashcode不同，不再比较equals，上个例子说明：

package com.heima.collection;
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
A a1=new A(“hector”,22);
A a3=new A(“paul”,33);
A a4=new A(“zeus”,100);
A a5=new A(“zeus”,100);
HashSet set=new HashSet();
set.add(a1);
set.add(a3);
set.add(a4);
set.add(a5);
for(Iterator it=set.iterator();it.hasNext();){
System.out.println(it.next());
}

}
}
class A{
private int age;
private String name;
public A() {
super();
}
@Override
public String toString() {
return “[age=” + age + “, name=” + name + “]”;
}
public A(String name, int age) {
super();
this.name = name;
this.age = age;
}
public int getAge() {
return age;
}
public String getName() {
return name;
}
public void setAge(int age) {
this.age = age;
}
public void setName(String name) {
this.name = name;
}
@Override
public int hashCode() {
System.out.println(“hashcode…”+this.getName());
return 60;
}
@Override
public boolean equals(Object obj) {
//name和age都相等，为true
A a=(A)obj;
return this.getName().equals(this.getName())&&a.getAge()==this.getAge();
}

}
运行结果：

Java集合框架之Collection集合

这里重写了hashcode()和equals()，故意让hashcode返回固定值60，通过运行结果可以看到当 hashcode相等时会继续判断equals，equals为true就视为重复元素，false则添加，如果不重写hashcode你会发现不会调用 equals方法。因为hasdcode和equals方法都是继承自超类Object，Object中默认hashcode是根据对象的内存地址计算 的，equals用“==”比较，所以不同对象的hashcode一定不同，equals也不会为true。但是java中有约定： 如果两个对象相等(equal),那么必须拥有相同的哈希码(hash code)，所以一般都会同时重写equals和hashcode，这个以后慢慢再说。

HashSet还有一个特点就是无序，HashSet内部是一个哈希表（又称散列表），每一个输入都会经过哈希函数得到一个固定长度的哈希值hash(Key)=hashcode，元素的存储位置是根据这个哈希值而定的，所以才会显得无序。

4、TreeSet

前面说过Set集合也可以有序，TreeSet就是那个有序的集合类，从总体框架图中可以看到TreeSet并没有直接实现Set接口而是实现了 其子接口Sorted，该接口进一步提供了关于元素总体排序的Set，这些元素使用其自然顺序进行排序，或者根据通常在创建有序 set 时提供的Comparator进行排序。就是是的TreeSet中的元素必须提供排序规则。对TreeSet元素排序有两种方法，一是元素本身具有排序规 则就是实现Comparable接口，而是给TreeSet提供一个Comparator比较器。

public class CompareDemo {
public static void main(String[] args) {
Student stu1=new Student(“hector”,29);
Student stu2=new Student(“guoke”,23);
Student stu3=new Student(“paul”,40);
Student stu4=new Student(“aple”,23);
Student[] stu={stu1,stu2,stu3,stu4};
TreeSet tree=new TreeSet();
tree.add(stu1);
tree.add(stu2);
tree.add(stu3);
tree.add(stu4);
Iterator it=tree.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}
//实现Comparable接口
class Student implements Comparable{
public int age;
public String name;
public Student() {
super();
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
//实现compareTo方法，定义比较规则，先按age排序，age相同按name排序
//该方法是内部自动调用
@Override
public int compareTo(Object o) {
int res=this.age-((Student)o).age;
if(res==0)
return this.name.compareTo(((Student)o).name);
return res;
}
@Override
public String toString() {
return “Student [age=” + age + “, name=” + name + “]”+”\n”;
}
}
这是第一种实现方法，Student 类实现了Comparable接口，这就使得Student自己有了排序规则。第二种就是给TreeSet提供一个比较器：

class StuComparator implements Comparator{
@Override
public int compare(Student o1, Student o2) {
int res=o1.age-o2.age;
if(res==0)
return o1.name.compareTo(o2.name);
return res;
}
}
创建TreeSet时把比较器传过去就行TreeSet tree=new TreeSet(new StuComarator());同样可以实现排序效果，如果两种方式同时存在，以这种方式为主！另外注意一点，如果这两种方式都没有，程序会出现异常 ClassCastException。

第二种方式更灵活，可以让TreeSet的一个实例定义自己的排序规则，不管存储什么对象都使用同一种排序方式，而且很方面程序的扩展，为首选方式。

第二个特点就是没有重复元素了，TreeSet底层是一个红黑树（又称自平衡二叉树），这个数据结构略微复杂，在TreeMap中详细说明。

四、集合特点比较
Java集合框架之Collection集合