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); } } }