深入理解java集合框架

 

      集合框架不用多说，大家都是经常用到的，也许我们只是简单的停留在使用方面，也许我们已经深入分析，并理解其性能差异的原因。

      基本的操作我就不说了，查API都会用，下面我来介绍一下我所理解的集合框架。

 

      java集合框架主要是由2个接口派生而出的：Collection和Map接口。我们经常用到的List和Set接口就是继承了Collection接口并扩充的。Iterator接口也是java集合框架的成员，不过只是用来遍历。

 

1.List接口

      List代表一个元素有序，可重复的集合，集合中每个元素都有对应的顺序索引。在List集合的实现类中，主要有3个实现类：ArrayList，Vector和LinkedList。

      先看看ArrayList和Vector的区别：

        其实ArrayList和Vector本质上没太大的区别，都是实现了List接口，而且底层都是基于java数组来存储元素的。但是他们最显著的区别就是：ArrayList是线程不安全的，Vector是线程安全的，由于Vector不管在什么情况下都要保证线程安全，所以其性能要低于ArrayList。是不是在多线程程序中就要用Vector呢？其实则不然，就算要保证线程安全也不推荐使用Vector，后面介绍Collection工具类保证线程安全。

      再看看ArrayList和LinkedList的区别：

        ArrayList是基于数组的顺序存储的线性表，LinkedList是基于链的链式存储的线性表。因为数组以一块连续内存来保存数组的元素，所以数组在随即访问时性能最好，也就是查询方面性能很好，但是如果添加和删除元素的时候，ArrayList都要对底层数组进行整体的移动，这会使性能很差。而链表在添加和删除元素的时候，只要添加和删除相应的节点就可以了，其他的根本不用管，所以添加和删除的操作很快，但是遍历方面，LinkedList必须一个元素一个元素的搜索，所以在查找方面性能不是很好。

 

      大部分情况下，ArrayList的性能总是优于LinkedList，因此绝大多数情况下都应当考虑用ArrayList。但是在经常要执行添加和删除的操作应该优先选择LinkedList。

 

2.Set接口

      Set代表一个无序，不可重复的集合。当添加元素的时候，根据equals()方法，如果返回true则添加失败，否则添加成功。在Set集合的实现类中，主要有2个实现类：HashSet和TreeSet。HashSet还有个子类LinkedHashSet。

      ①.HashSet 是按hash算法来存储集合中的元素，因此具有很好的存取和查找性能。而且HashSet中允许null元素。

          当向Hash集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到对象的hashCode值，然后根据hashCode值决定该对象在HashSet中的存储位置。这里值得说一下，HashSet和Set有点出入，HashSet判断2个元素是否一样是通过equals()和hashCode()2个方法决定的，当equals()返回true，而且2个元素的hashCode值相等，HashSet才认为这2个元素一样。

          如果需要把某个类对象加入到HashSet中，重写equals()方法和hashCode()方法时，要尽量保证两个对象通过equals()方法比较返回true时，他们的hashCode()方法返回值也相等。如果两个对象通过equals()方法返回true，但是hashCode()方法返回不同hashCode值时，HashSet会将两个对象存在Hash表的不同位置。如果两个对象通过hashCode()方法返回值相同，但是equals()方法返回false，HashSet就会试图把这两个对象保存在同一位置，但是又不行，所以就会在这个位置使用链式结构来存储，虽然能添加成功，但是HashSet是根据元素hashCode值来快速定位的，同意位置有几个元素的话，性能就会降低。

代码1：

public class HashSetTest {
	//分别向集合set中添加2个A对象，2个B对象和2个C对象
	public static void main(String [] args){
		HashSet set = new HashSet();
		A a1 = new A();
		A a2 = new A();
		System.out.println("a1的hashCode值："+a1.hashCode());
		System.out.println("a2的hashCode值："+a2.hashCode());
		B b1 = new B();
		B b2 = new B();
		//b1和b2通过equals()方法的返回值
		System.out.println(b1.equals(b2));
		set.add(a1);
		set.add(a2);
		set.add(b1);
		set.add(b2);
		set.add(new C());
		set.add(new C());
		System.out.println(set);
	}
}
class A {
	//类A只重写equals()方法，而且只返回true
	public boolean equals(Object obj){
		return true;
	}
}
class B {
	//类B只重写hashCode()方法，而且只返回1
	public int hashCode(){
		return 1;
	}
}
class C {
	//类C重写equals()方法返回true，重写hashCode()方法返回2
	public boolean equals(Object obj){
		return true;
	}
	public int hashCode(){
		return 2;
	}
}

 结果：

a1的hashCode值：29094346
a2的hashCode值：33492446
false
[Collection.B@1, Collection.B@1, Collection.C@2, Collection.A@1ff0dde, Collection.A@1bbf1ca]
      显然A的hashCode值不一样，所以HashSet中添加了2个A对象，B的equals()方法返回false，所以添加了2个B对象，但是C的equals()方法返回true，hashCode值也一样，总为2，所以只添加了一个C对象。

 

      ②.LinkedHashSet 是HashSet的子类，也是根据元素的hashCode值来决定元素的存储位置，但它也用链表维护元素的次序，使得LinkedHashSet遍历起来会按添加顺序来访问集合里的元素。

          LinkedHashSet因为需要维护元素的插入顺序，所以性能相对于HashSet要略低，但是在迭代访问set里的全部元素时有很好的性能，以为它以链表维护内部顺序。

代码2：

public class LinkedHashSetTest {
	public static void main(String [] args){
		LinkedHashSet set = new LinkedHashSet();
		set.add("面向对象");
		set.add("数据结构");
		set.add("操作系统");
		set.add("数据库");
		set.add("计算机组成原理");
		System.out.println(set);
	}
}

 结果：

[面向对象, 数据结构, 操作系统, 数据库, 计算机组成原理]
      可见是按添加顺序进行输出的。

 

      ③.TreeSet 可以确保集合处于排序状态。TreeSet是采用红黑树的数据结构来存储集合元素的(没学过红黑树的同学不要紧，我也只是在数据结构书上看见过这个词，后面花点时间学学就好了)，它支持自然排序和定制排序方法。

          自然排序，就是TreeSet根据元素的compareTo(Object obj)方法来比较元素之间的大小关系，然后按升序排列。因为在实现compareTo(Object obj)方法时，都要将被比较对象强制转型成相同类型，所以TreeSet中只能添加同一类型的元素，否则就会报ClassCastException类转型异常。

          对于TreeSet而言，判断两个元素是否一样，是通过调用元素compareTo(Object obj)方法，如果返回0，则认为2个对象一样，否则不一样。因此在添加自定义对象的时候，要尽量保证compareTo(Object obj)方法和equals()方法有一直的结果，否则会引发Set规则的冲突。

          定制排序，就是自定义顺序进行排序，这里需要用到Comparator接口，接口中有个compare()方法，通过比较来确定排列顺序。如果需要实现定制排序，在创建集合对象时就要提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排列逻辑。

代码3：

public class TreeSetTest {
	public static void main(String [] args){
		TreeSet set = new TreeSet();
		//向set中添加5个Integer对象
		set.add(5);
		set.add(-3);
		set.add(10);
		set.add(0);
		set.add(-9);
		//打印集合
		System.out.println(set);
	}
}

 结果：

[-9, -3, 0, 5, 10]
      可以看出只要添加进去就已经排好序了。

 

      如果向HashSet或者TreeSet中添加可变对象，后面程序又修改了该对象，就有可能导致该对象和集合中其他对象相等，从而导致HashSet和TreeSet无法准确访问该对象了。因此为了让程序更加健壮，应该HashSet和TreeSet集合中只放入不可变对象。

      HashSet性能总是比TreeSet好，特别是添加和查询元素方面，因为TreeSet需要红黑树算法来维护集合元素中的顺序，只有当需要一个排序的Set时才使用TreeSet。而在遍历方面，因为有链表，所以LinkedHashSet要快于HashSet。

当然HashSet，LinkedHashSet和TreeSet都不是线程安全的，后面介绍Collection工具类保证线程安全。

 

3.Map接口

      Map用来保存具有映射关系的数据，因此Map集合里保存了两组值，一组是key，一组是value，key是不允许重复的，即两个元素通过equals()方法来判断，value是允许重复的。key和value是一对一关系，通过key总是能找到唯一的value。在Map中，主要有3个实现类：HashMap，Hashtable，TreeMap。HashMap还有个子类LinkedHashMap。有没有觉得和Set集合惊人的相似。没错，java是先实现了Map，然后通过包装一个所有value都为null的Map就实现了Set集合。

      其实Map就是对key进行的操作，而key的集合就是Set，我们都知道Map中有个方法keySet()得到key的Set集合，下面就对比Set介绍一下Map，具体的方法就不介绍了，查下API都会。

      ①.HashMap和Hashtable 的关系就像ArrayList和Vector的关系。Hashtable是线程安全的，而HashMap不是，所以HashMap的性能要优于Hashtable，Hashtable不允许出现为null的key，而HashMap允许出现一对。

          HashMap和Hashtable对key的要求与HashSet对集合元素的要求完全一样，key是通过equals()和hashCode()方法来判断一致性，这些就不再做解释了。

      ②.LinkedHashMap 是HashMap的子类，和LinkedHashSet一样，也是使用了链表来维护key-value对的次序，这里也不多做解释。

      ③.TreeMap 也是和TreeSet一样，也是采用的红黑树的数据结构来存储key-value对，而且对key进行排序，这个和TreeSet一样，不多解释。

 

      HashMap性能比Hashtable好，因为Hashtable需要线程同步。TreeMap通常比HashMap和Hashtable要慢，特别是在插入，删除key-value对的情况下，因为TreeMap采用红黑树来管理key-value对。LinkedHashMap要比HashMap慢，因为LinkedHashMap要维护链表来保持Map中的key-value的添加顺序。这些性能比较起来发现和Set集合的是一样的。

 

Iterator接口

      Iterator接口也是java集合框架的成员，只不过Collection和Map用于装对象，而Iterator(迭代器)是用来遍历Collection集合中的元素的。List集合中的元素都有索引，可以根据索引来遍历，当然也能用Iterator来遍历，不过优先选择get(int index)方法遍历，因为用索引可以随机访问而Iterator是一个一个来遍历的，很慢。但是Set就不一样了，Set集合中的元素木有索引，只能用Iterator来遍历。

      Iterator仅仅用来遍历，Iterator迭代变量不是集合元素本身，而是集合元素的赋值，因此修改迭代变量是不可能改变集合元素本身，是不是想到了值传递啊。在用Iterator遍历的时候，Collection集合中的元素不能被改变，否则会抛出ConcurrentModificationException异常。

      当然也可以使用foreach循环遍历集合元素，这种情况和Iterator迭代遍历差不多。

代码4：

public class ForeachIteratorTest {
	public static void main(String [] args){
		//创建一个集合
		Collection books = new HashSet();
		books.add("数学");
		books.add("语文");
		books.add("英语");
		//这是迭代器遍历
//		Iterator it = books.iterator();
//		while(it.hasNext()){
//			String book = (String) it.next();
//			if(book.equals("语文")){
//				book = "计算机";
//			}
//		}
                //这是foreach循环遍历
		for(Object obj:books){
			String book = (String) obj;
			if(book.equals("语文")){
				book = "计算机";
			}
		}
		System.out.println(books);
	}
}

结果：

[语文, 英语, 数学]
      用Iterator和foreach遍历都是一样的结果。

操作集合的工具：Collections

      Collections提供了很多操作集合的方法，其中有排序操作，查找替换操作和同步控制操作等操作。排序和查找替换我就不多介绍了。前面提到了ArrayList，LinkedList，HashSet，TreeSet，HashMap，TreeSet等等都不是线程安全，而Collections提供了多个synchronizedXxx()方法，将指定集合包装成线程同步的集合，解决多线程并发访问集合使线程安全的问题。

Collection c = Collections.synchronizedCollection(new ArrayList());
List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());
Map map = Collections.synchronizedMap(new HashMap());

 这是4种方法，这样可以直接获取线程安全的List，Set和Map了。

 

      没事多看看源代码吧！