Collection集合接口

Collection集合接口

 

集合对象：用于管理其他若干对象（非引用地址）的对象

1.1 List接口: 有顺序的，元素可以重复（两有）
遍历：方式一：for循环按下标取各元素，方式二：迭代
排序：Comparable Comparator Collections.sort()
实现类：

ArrayList：底层用数组实现的List
特点：查询效率高，增删效率低 轻量级 线程不安全
LinkedList：底层用双向循环链表 实现的List
特点：查询效率低，增删效率高
Vector: 底层用数组实现List接口的另一个类
特点：重量级，占据更多的系统开销 线程安全

ArrayList与Vector的区别：

ArrayList不支持线程同步，高效，不考虑线程并发时用；

Vector支持线程同步，效率较低，在考虑线程并发时用，保证线程安全

1.2 Set接口：无顺序的，元素不可重复（值不相同）
遍历：调自身迭代方法iterator(),返回一个Iterator对象,其中iterator()方法是由内部类实现的。
排序：SortedSet接口
实现类：

HashSet：采用哈希算法（底层实际上是HashMap）来实现Set接口
唯一性保证：根据hashcode

SortedSet：对一个Set排序
TreeSet：在元素添加的同时，进行排序。也要给出排序规则
唯一性保证：默认调用java.lang.Comparable接口中的compareTo方法，返回为0，就可以认定两个对象中有一个是重复对象。

1.3 Map：<key,value> key：唯一，不可重复 value：可重复
遍历：先迭代遍历key的集合，再根据key得到value
实现类：

HashMap:轻量级 线程不安全 允许key或者value是null，可同时为空
Hashtable：重量级 线程安全 不允许key或者value是null
Properties：Hashtable的子类，key和value都是String

SortedMap接口：元素自动对key排序
TreeMap：

1.4 五个最常用的集合类之间的区别和联系
1．ArrayList: 元素单个，效率高，多用于查询
2．Vector: 元素单个，线程安全，多用于查询
3．LinkedList:元素单个，多用于插入和删除
4．HashMap: 元素成对，元素可为空
5．HashTable: 元素成对，线程安全，元素不可为空

ArrayList底层是Object数组，所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点。
LinkedList底层是双向循环链表。在此链表上每一个数据节点都由三部分组成：前指针（指向前面的节点的位置），数据，后指针（指向后面的节点的位置）。最后一个节点的后指针指向第一个节点的前指针，形成一个循环。双向循环链表的查询效率低但是增删效率高。因此LinkedList经常用在增删操作较多而查询操作很少的情况下：队列(FIFO)和堆栈(LIFO)。
注：1、ArrayList和LinkedList在用法上没有区别，但功能上还是有区别的。
2、使用栈时不提供方法让不是最后一个元素的元素获得出栈的机会。

面试经验（知识点）：
java.util.stack（stack即为堆栈）的父类为Vector。可是stack的父类是最不应该为Vector的。因为Vector的底层是数组，且Vector有get方法（意味着它可能访问到并不属于最后一个位置元素的其他元素，很不安全）。
对于堆栈和队列只能用push/pop方法。
实现栈一定要用LinkedList。在JAVA1.5中，collection有queue来实现队列。

HashSet实现类：
HashSet中元素是无序的（无序指数据的添加顺序和排列顺序不同），且元素不可重复。
HashSet底层用的是数组。
当向数组中利用add(Object o)添加对象的时候，系统先找对象的hashCode：
int hc=o.hashCode(); 返回的hashCode为整数值。
Int I=hc%n;（n为数组的长度），取得余数后，利用余数向数组中相应的位置添加数据，以n为6为例，如果I=0则放在数组a[0]位置，如果I=1,则放在数组a[1]位置。如果1位置已经有元素，则调用equals()比较，如果返回值为true，则说明数据重复。如果equals()返回的值为false，则再找其他的位置进行比较。这样就导致两个相同的对象有可能重复地添加到数组不同位置中，因为他们的hashCode不同。如果我们能够使两个相同的对象具有相同hashcode，才能在equals()返回为真。
因为String类是自动覆盖的，所以当比较String类的对象的时候，就不会出现有两个相同的string对象的情况。
结论：如将自定义类用hashSet来添加对象，一定要覆盖hashcode()和equals()，覆盖的原则是保证当两个对象hashcode返回相同的整数，而且equals()返回值为True。如果没有设定equals()，就会造成返回hashCode虽然结果相同，但在程序执行的过程中会多次地调用equals()，从而影响程序执行的效率。

使用hashSet的优点：
hashSet的底层是数组，其查询效率非常高。而且在增加和删除的时候由于运用的hashCode的比较开确定添加元素的位置，所以不存在元素的偏移，所以效率也非常高。因为hashSet查询和删除和增加元素的效率都非常高。
但是hashSet增删的高效率是通过花费大量的空间换来的：因为空间越大，取余数相同的情况就越小。HashSet这种算法会建立许多无用的空间。
使用hashSet类时要注意，如果发生冲突，就会出现遍历整个数组的情况，这样就使得效率非常的低。

1.5 比较
Collections工具类（工具类——全是static 方法）
TreeSet,TreeMap过滤重复都是通过实现Comparable接口或实现一个比较器来实现的

package com.wesley.collection;
import java.util.*;
	/**
	 * TreeSet实现比较器接口排序
	 * */
public class CompareTreeSet implements Comparable {
	int num;
	String name;
	public CompareTreeSet(int num, String name) {
		this.num = num;
		this.name = name;
	}
	public int compareTo(Object obj) {
		if (obj instanceof CompareTreeSet) {
			CompareTreeSet cts = (CompareTreeSet) obj;
			if (this.num < cts.num)
				return -1;
			else if (this.num == cts.num) {
				return this.name.compareTo(cts.name);
			} else {
				return 1;
			}
		}
		return 0;
	}
	public static void main(String[] args) {
		CompareTreeSet ct1 = new CompareTreeSet(1, "zhangsan");
		CompareTreeSet ct2 = new CompareTreeSet(1, "wangwu");
		Set set = new TreeSet();
		set.add(ct1);
		set.add(ct2);
		Iterator it=set.iterator();
		while(it.hasNext()){
			CompareTreeSet ct=(CompareTreeSet) it.next();
			System.out.println(ct.num+"  "+ct.name);
		}
	}
}

package com.wesley.collection;
import java.util.*;
	/**
 	* TreeSet利用比较器排序
 	*/
public class ComparatorTreeSet {
	int num;
	String name;
	public ComparatorTreeSet(int num, String name) {
		this.num = num;
		this.name = name;
	}
	public static void main(String[] args) {
		ComparatorTreeSet ct1 = new ComparatorTreeSet(2, "zhangsan");
		ComparatorTreeSet ct2 = new ComparatorTreeSet(2, "wangwu");
		ComparatorTreeSet ct3 = new ComparatorTreeSet(1, "wangwu");
		Set set = new TreeSet(new Comparator(){
			public int compare(Object obj0, Object obj1) {
				ComparatorTreeSet c1=(ComparatorTreeSet)obj0;
				ComparatorTreeSet c2=(ComparatorTreeSet)obj1;
				if (c1.num < c2.num)
					return -1;
				else if (c1.num == c2.num) {
					return c1.name.compareTo(c2.name);
				} else {
					return 1;
				}
			}
		});
		set.add(ct1);
		set.add(ct2);
		set.add(ct3);
		Iterator it=set.iterator();
		while(it.hasNext()){
			ComparatorTreeSet ct=(ComparatorTreeSet) it.next();
			System.out.println(ct.num+"  "+ct.name);
		}
	}
}