Collection接口

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。

如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：

Iterator it = collection.iterator(); //获得一个迭代子
while(it.hasNext()) {

Objectobj = it.next(); //得到下一个元素
}

由Collection接口派生的两个接口是List和Set。

 

List接口

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

实际上有两种List：一种是基本的ArrayList其优点在于随机访问元素，另一种是更强大的LinkedList它并不是为快速随机访问设计的，而是具有一套更通用的方法。

和下面要提到的Set不同，List允许有相同的元素。

除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。

实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

LinkedList类

LinkedList实现了List接口，允许null元素。对顺序访问进行了优化，向List中间插入与删除的开销并不大。随机访问则相对较慢。还具有下列方法：addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()这些方法(没有在任何接口或基类中定义过)，这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(newLinkedList(…));

ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速率很慢。

size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

 

Vector类

Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和
ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

Stack类

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

 

Map接口

请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

方法put(Object key, Object value)添加一个”值”(想要得东西)和与”值”相关的”键”(key)(使用它来查找)。方法get(Object key)返回与给定”键”相关联的”值”。可以用containsKey()和containsValue()测试Map中是否包含某个”键”或”值”。

Hashtable类

Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。

添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作使用Java的hashCode来实现，时间开销为常数。

Hashtable通过initial capacity（初始容量）和load
factor（加载因子）两个参数调整性能。通常缺省的load factor为0.75较好地实现了时间和空间的均衡。增大loadfactor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。

使用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：

Hashtable numbers = new Hashtable();

numbers.put(“one”, new Integer(1));

numbers.put(“two”, new Integer(2));

numbers.put(“three”, new Integer(3));

要取出一个数，比如2，用相应的key：

Integer n = (Integer)numbers.get(“two”);

System.out.println(“two = ” + n);

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。

如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。

Hashtable是同步的，线程安全。

HashMap类

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null
value和null key。但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者loadfactor过低。

TreeMap类

基于红黑树数据结果的实现。查看”键”或”键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。

WeakHashMap类

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

Set接口

Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)
= false，因此Set最多有一个null元素。

很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。

请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

HashSet类

HashSet是基于HashMap实现的，HashSet底层采用HashMap来保存所有元素。为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。hashCode和equal()是HashMap用的，因为无需排序所以只需要关注定位和唯一性即可。hashCode用来计算hash值，hash值是用来确定hash表索引，hash表中的一个索引存放的是一张链表，所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry。

put时，如果hash表中没定定位到，就在链表前加一个Entry，如果定位到了，则更换Entry中的value(值)并返回旧value(值)。

覆写key的hashCode()和equal()时一定要注意，不要把它们和可变属性关联上，否则属性变了之后hashCode会变，equal也会为false，这样在Map中就找不到它了而且这样的对象因为找不到它所以得不到释放，这样就变成了一个无效引用(相当于内存泄漏)。

LinkedHashSet类

HashSet类的子类，具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

TreeSet类

TreeSet是依靠TreeMap来实现的，TreeSet集合类是一个有序集合，它的元素按照升序排序，默认是自然顺序排列，也就是说，TreeSet中的对象元素需要实现Comparable接口。TreeSet与HashSet类一样没有get()方法来获取列表中的元素，所以也只能通过迭代器方法来获取。

由于TreeMap需要排序，所以需要一个Comparable为键值进行大小比较，当然也是用Comparator定位的，Comparator可以在创建TreeMap时指定，这时排序时使用Comparator.compare，如果创建时没有指定Comparator那么就会使用key.compareTo()方法，这就要求key必须实现Comparable接口。

TreeMap是使用Tree数据结构实现的，所以使用compare接口就可以完成定位了。

Queue接口

Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法了，而不能直接访问LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

队列是一种数据结构。它有两个基本操作：在队列尾部加人一个元素，和从队列头部移除一个元素。就是说，队列以一种先进先出的方式管理数据，如果你试图向一个已经满了的阻塞队列中添加一个元素或者是从一个空的阻塞队列中移除一个元索，将导致线程阻塞。

在多线程进行合作时，阻塞队列是很有用的工具。工作者线程可以定期地把中间结果存到阻塞队列中而其他工作者线线程把中间结果取出并在将来修改它们。队列会自动平衡负载。如果第一个线程集运行得比第二个慢，则第二个线程集在等待结果时就会阻塞。如果第一个线程集运行得快，那么它将等待第二个线程集赶上来。

队列的方法

阻塞队列的操作可以根据它们的响应方式分为以下三类：add、remove和element操作在你试图为一个已满的队列增加元素或从空队列取得元素时 抛出异常。当然，在多线程程序中，队列在任何时间都可能变成满的或空的，所以你可能想使用offer、poll、peek方法。这些方法在无法完成任务时 只是给出一个出错示而不会抛出异常。注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的。

offer，add区别：一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。这时新的offer方法就可以起作用了。它不是对调用add()方法抛出一个unchecked异常，而只是得到由offer()返回的false。

poll，remove区别：remove()和poll()方法都是从队列中删除第一个元素（head）。remove()的行为与Collection接口的版本相似，但是新的poll()方法在用空集合调用时不是抛出异常，只是返回null。因此新的方法更适合容易出现异常条件的情况。

peek，element区别：element()和peek()用于在队列的头部查询元素。与remove()方法类似，在队列为空时，element()抛出一个异常，而peek()返回null。

注意：Queue队列是不能直接实例化的。原先在java编程中，Queue的实现都是用LinkedList。如：Queue qe = new LinkedList();

注意：此实现不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程结构上修改了该列表，则它必须保证外部同步。(结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改)。这一般通过对自然封装该列表的对象进行同步操作来完成。

ArrayBlockingQueue类

一个由数组支持的有界队列。基于数组的阻塞循环队列，先进先出原则对元素进行排序。

LinkedBlockingQueue类

一个由链接节点支持的可选有界队列。基于链表的队列，先进先出排序元素。

PriorityBlockingQueue类

一个由优先级堆支持的无界优先级队列。PriorityBlockingQueue是对PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞队列上put时是不会受阻的。但是由于资源被耗尽，所以试图执行添加操作可能会导致OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元素要具有比较能力。

DelayQueue

一个由优先级堆支持的、基于时间的调度队列。（基于PriorityQueue来实现的）是一个存放Delayed元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的Delayed元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的getDelay(TimeUnit.NANOSECONDS)方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用null元素。

SynchronousQueue

一个利用BlockingQueue接口的简单聚集（rendezvous）机制。SynchronousQueue 类是最简单的。它没有内部容量。它就像线程之间的手递手机制。在队列中加入一个元素的生产者会等待另一个线程的消费者。当这个消费者出现时，这个元素就直接在消费者和生产者之间传递，永远不会加入到阻塞队列中。

总结

Java中的List/Set和Map的区别？

List按对象进入的顺序保存对象，不做排序和编辑操作。

Set对每个对象只接受一次，并使用自己内部的排序方法(通常，你只关心某个元素是否属于Set而不关心它的顺序–否则使用List)。

Map同样对每个元素保存一份，但这是基于”键”(key)的，Map也有内置的排序，因而不关心元素添加的顺序。如果添加元素的顺序对程序设计很重要，应该使用LinkedHashSet或者LinkedHashMap。

如何选用集合类？

1、要求线程安全，使用Vector、Hashtable

2、不要求线程安全，使用ArrayList, LinkedList, HashMap

3、要求key和value键值，则使用HashMap,
Hashtable

4、数据量很大，又要线程安全，则使用Vector

如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。

要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。

尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

相互区别

Vector和ArrayList

1、vector是线程同步的，这个类中的一些方法保证了Vector中的对象是线程安全的。而arraylist是线程异步的，是不安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。

2、 如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长

度的100%,而arraylist增长率为目前数组长度的50%。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

3、如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)，n为总长度，这个时候就应该考虑到使用linkedlist，因为它移动一个指定位置的数据所花费的时间为0(1)，而查询一个指定位置的数据时花费的时间为0(i)。

ArrayList和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

ArrayList和linkedlist

1、ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2、对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。

3、对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList.因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

Hashtable和Hashmap

1、历史原因：Hashtable是基于陈旧的Dictionary类的，HashMap是Java1.2引进的Map接口的一个实现。

2、同步性：Hashtable是线程安全的，也就是说是同步的，这个类中的一些方法保证了Hashtable中的对象是线程安全的。而HashMap则是线程异步的，因此HashMap中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用HashMap是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销，从而提高效率。

3、HashMap可以让你将空值作为一个表的条目的key或value，但是Hashtable是不能放入空值的(null)。

HashMap和TreeMap

1、HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

2、在Map中插入、删除和定位元素，HashMap是最好的选择。但如果你要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和equals()的实现。这个TreeMap没有调优选项，因为该树总处于平衡状态。

HashSet与TreeSet

HashSet是基于hash算法实现的，性能优于TreeSet。通常使用HashSet，在我们需要对其中元素排序的时候才使用TreeSet。

Iterator(迭代器)的用法

不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。

Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。

例如，如果没有使用Iterator，遍历一个数组的方法是使用索引：for(inti=0;i<array.size();i++)
{..get(i)…}

而访问一个链表(LinkedList)又必须使用while循环：while((e=e.next())!=null){…e.data()…}

以上两种方法客户端都必须事先知道集合的内部结构，访问代码和集合本身是紧耦合，无法将访问逻辑从集合类和客户端代码中分离出来，每一种集合对应一种遍历方法，客户端代码无法复用。

更恐怖的是，如果以后需要把ArrayList更换为LinkedList，则原来的客户端代码必须全部重写。

为解决以上问题，Iterator模式总是用同一种逻辑来遍历集合：

for(Iteratorit=c.iterater(); it.hasNext();) { …}

奥秘在于客户端自身不维护遍历集合的”指针”，所有的内部状态（如当前元素位置，是否有下一个元素）都由Iterator来维护，而这个Iterator由集合类通过工厂方法生成，因此，它知道如何遍历整个集合。

客户端从不直接和集合类打交道，它总是控制Iterator，向它发送”向前”，”向后”，”取当前元素”的命令，就可以间接遍历整个集合。

首先看看java.util.Iterator接口的定义：

public interface Iterator {

boolean hasNext();

Object next();

void remove();

依赖前两个方法就能完成遍历，典型的代码如下：

在JDK1.5中，还对上面的代码在语法上作了简化：

每一种集合类返回的Iterator具体类型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator，Tree可能返回TreeIterator，但是它们都实现了Iterator接口，因此，客户端不关心到底是哪种Iterator，它只需要获得这个Iterator接口即可，这就是面向对象的威力。

要确保遍历过程顺利完成，必须保证遍历过程中不更改集合的内容（Iterator的remove()方法除外），因此，确保遍历可靠的原则是只在一个线程中使用这个集合，或者在多线程中对遍历代码进行同步。

Iterator示例:

1. Collection c=new ArrayList();
2. c.add(“abc”);
3. c.add(“xyz”);
4. for(Iterator it=c.iterator();it.hasNext();){
5. Strings=(String)it.next();
6. System.out.println(s);
7. }

 

如果你把第一行代码的ArrayList换成LinkedList或Vector，剩下的代码不用改动一行就能编译，而且功能不变，这就是针对抽象编程的原则：对具体类的依赖性最小。