3）Java容器
Java的集合框架核心主要有三种：List、Set和Map。
这里的 Collection、List、Set和Map都是接口（Interface）。 List lst = new ArrayList(); 这是我们平常经常使用的创建一个新的List的语句，在这里， List是接口，ArrayList才是具体的类。
这里的 Collection、List、Set和Map都是接口（Interface）。 List lst = new ArrayList(); 这是我们平常经常使用的创建一个新的List的语句，在这里， List是接口，ArrayList才是具体的类。
常用集合类的继承结构如下：
Collection<--List<--Vector
Collection<--List<--ArrayList
Collection<--List<--LinkedList
Collection<--Set<--HashSet
Collection<--Set<--HashSet<--LinkedHashSet
Collection<--Set<--SortedSet<--TreeSet
Map<--TreeMap
Map<--HashMap
Collection<--List<--Vector
Collection<--List<--ArrayList
Collection<--List<--LinkedList
Collection<--Set<--HashSet
Collection<--Set<--HashSet<--LinkedHashSet
Collection<--Set<--SortedSet<--TreeSet
Map<--TreeMap
Map<--HashMap
下面的表格是各个容器的特性一览表：
|
Collection/Map
|
接口
|
成员重复性
|
元素存放顺序（ Ordered/Sorted ）
|
元素中被调用的方法
|
基于那中数据结构来实现的
|
|
HashSet
|
Set
|
Unique elements
|
No order
|
equals()
hashCode()
|
Hash 表
|
|
LinkedHashSet
|
Set
|
Unique elements
|
Insertion order
|
equals()
hashCode()
|
Hash 表和双向链表
|
|
TreeSet
|
SortedSet
|
Unique elements
|
Sorted
|
equals()
compareTo()
|
平衡树（Balanced tree ）
|
|
ArrayList
|
List
|
Allowed
|
Insertion order
|
equals()
|
数组
|
|
LinkedList
|
List
|
Allowed
|
Insertion order
|
equals()
|
链表
|
|
Vector
|
List
|
Allowed
|
Insertion order
|
equals()
|
数组
|
|
HashMap
|
Map
|
Unique keys
|
No order
|
equals()
hashCode()
|
Hash 表
|
|
LinkedHashMap
|
Map
|
Unique keys
|
Key insertion order/Access order of entries
|
equals()
hashCode()
|
Hash 表和双向链表
|
|
Hashtable
|
Map
|
Unique keys
|
No order
|
equals()
hashCode()
|
Hash 表
|
|
TreeMap
|
SortedMap
|
Unique keys
|
Sorted in key order
|
equals()
compareTo()
|
平衡树（Balanced tree ）
|
下文会对各个容器做分开详述。
(0)collection:（interfere）
java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
- boolean add(Object element)
- boolean remove(Object element)
Collection 接口还支持查询操作：
- int size()
- boolean isEmpty()
- boolean contains(Object element)
- Iterator iterator()
- boolean containsAll(Collection collection)//是否包含某集合的所有元素
- boolean addAll(Collection collection)//并集
- void clear()//清空整个集合
- void removeAll(Collection collection)//从一个集合中去除了另一个集合的所有元素。集合的减法
- void retainAll(Collection collection) //集合的交集
- Object[] toArray()
- Object[] toArray(Object[] a)//a 应该是集合中所有存放的对象的类的父类
Collection 接口的 iterator() 方法返回一个 Iterator。
public class IteratorDemo {
public static void main(String[] args) {
Collection collection = new ArrayList();
collection.add("s1");
collection.add("s2");
collection.add("s3");
Iterator iterator = collection.iterator();//得到一个迭代器
while (iterator.hasNext()) {//遍历
Object element = iterator.next();
System.out.println("iterator = " + element);
}
(1)List(interface)
List是有序的Collection.使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
(1.1)Vector:
基于数组（Array）的List，封装了数组所不具备的一些功能方便我们使用，所以它难以避免数组的限制，同时性能也不可能超越数组。另外很重要的一点就是Vector是线程同步的(sychronized)。
(1.2)ArrayList:
同Vector一样是一个基于数组上的List，但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一点，但是当运行到多线程环境中时，需要自己在管理线程的同步问题。
(1.3)LinkedList:
LinkedList不同于前面两种List，它不是基于数组的，所以不受数组性能的限制。
LinkedList 添加了一些处理列表两端元素的方法，
addFirst()、addLast() 、
(1.1)Vector:
基于数组（Array）的List，封装了数组所不具备的一些功能方便我们使用，所以它难以避免数组的限制，同时性能也不可能超越数组。另外很重要的一点就是Vector是线程同步的(sychronized)。
(1.2)ArrayList:
同Vector一样是一个基于数组上的List，但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一点，但是当运行到多线程环境中时，需要自己在管理线程的同步问题。
(1.3)LinkedList:
LinkedList不同于前面两种List，它不是基于数组的，所以不受数组性能的限制。
LinkedList 添加了一些处理列表两端元素的方法，
addFirst()、addLast() 、
getFirst()、 getLast()、
removeFirst() 、removeLast()
这些方法可以当作堆栈，队列使用
List总结：
所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]
所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]
所有的List中可以有null元素，例如[ tom,null,1 ]
基于Array的List（Vector，ArrayList）适合查询，而LinkedList 适合添加，删除操作
这些方法可以当作堆栈，队列使用
public class ListExample {
public static void main(String args[]) {
LinkedList queue = new LinkedList();
queue.addFirst("Bernadine" );
queue.addFirst("Elizabeth" );
queue.addFirst("Gene" );
queue.addFirst("Elizabeth" );
queue.addFirst("Clara" );
System.out.println(queue);
queue.removeLast();
queue.removeLast();
System.out.println(queue);
}
}
List总结：
所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]
所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]
所有的List中可以有null元素，例如[ tom,null,1 ]
基于Array的List（Vector，ArrayList）适合查询，而LinkedList 适合添加，删除操作
(2) set（interfece）
Set是一种不包含重复的元素的无序Collection。
(2.1) HashSet:HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。value值不用。
(2.2) LinkedHashSet
(2.3)TreeSet:不同于HashSet的根本就是TreeSet是有序
Set总结：
HashSet实现的基础是Map，TreeSet的实现基础是平衡二叉树
Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象
第 0 次随机数产生为： 96
第 1 次随机数产生为： 64
第 2 次随机数产生为： 14
第 3 次随机数产生为： 95
第 4 次随机数产生为： 57
未排序前HashSet ：[64, 96, 95, 57, 14]
未排序前LinkedHashSet ：[96, 64, 14, 95, 57]
排序后 TreeSet ：[14, 57, 64, 95, 96]
从这个例子中，我们可以知道 HashSet的元素存放顺序和我们添加进去时候的顺序没有任何关系，而 LinkedHashSet 则保持元素的添加顺序。 TreeSet则是对我们的 Set中的元素进行排序存放。
(2.1) HashSet:HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。value值不用。
(2.2) LinkedHashSet
(2.3)TreeSet:不同于HashSet的根本就是TreeSet是有序
Set总结：
HashSet实现的基础是Map，TreeSet的实现基础是平衡二叉树
Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象
package c08;
import java.util.*;
public class SetSortExample {
public static void main(String args[]) {
Set set1 = new HashSet();
Set set2 = new LinkedHashSet();
for(int i=0;i<5;i++){
// 产生一个随机数，并将其放入 Set中
int s=(int) (Math.random()*100);
set1.add(new Integer( s));
set2.add(new Integer( s));
System.out.println("第 "+i+" 次随机数产生为： "+s);
}
System.out.println("未排序前 HashSet：" +set1);
System.out.println("未排序前 LinkedHashSet：" +set2);
// 使用TreeSet来对另外的 Set进行重构和排序
Set sortedSet = new TreeSet(set1);
System.out.println("排序后 TreeSet ：" +sortedSet );
}
}
该程序的一次执行结果为：第 0 次随机数产生为： 96
第 1 次随机数产生为： 64
第 2 次随机数产生为： 14
第 3 次随机数产生为： 95
第 4 次随机数产生为： 57
未排序前HashSet ：[64, 96, 95, 57, 14]
未排序前LinkedHashSet ：[96, 64, 14, 95, 57]
排序后 TreeSet ：[14, 57, 64, 95, 96]
从这个例子中，我们可以知道 HashSet的元素存放顺序和我们添加进去时候的顺序没有任何关系，而 LinkedHashSet 则保持元素的添加顺序。 TreeSet则是对我们的 Set中的元素进行排序存放。
(3) map: (interfece)
Map 是一种把键对象和值对象进行关联的容器。对于键对象来说，像Set一样，一个 Map容器中的键对象不允许重复，这是为了保持查找结果的一致性。Map一样容易扩展成多维Map ，无需增加新的概念，只要让Map中的键值对的每个“值”也是一个Map即可。
(3.1)HashMap：
里面最重要的 3个属性：
transient Entry[] table: 用来存放键值对的对象Entry数组，也就是 Hash表
transient int size：当前 Map中存放的键值对的个数
final float loadFactor：负载因子，用来决定什么情况下应该对 Entry进行扩容
int threshold;重构因子，其值为负载因子与数组容积的乘积。当数组存入元素超过该值时，table需要扩容
向HashMap中添加一个条目的过程：
1. 创建一个Entry对象用来存放键值对。
2. 添加该键值对 ---- Entry对象到链表中
3. 最后在size 属性加一，并判断是否需要对当前的 Hash表进行重构（ void resize(int newCapacity) ）
(3.2)LinkedHashMap：
保留键的原有插入顺序。
System.out.println("未排序前HashMap："+map1);
System.out.println("未排序前 LinkedHashMap：" +map2);
// 使用TreeMap来对另外的 Map进行重构和排序
Map sortedMap;
System.out.println("排序后： "+new TreeMap(map1));
System.out.println("排序后： "+new TreeMap(map2));
在实际的使用中我们也经常这样做：使用 HashMap或者 LinkedHashMap 来存放元素，当所有的元素都存放完成后，如果使用需要一个经过排序的 Map的话，我们再使用 TreeMap来重构原来的 Map对象。这样做的好处是：因为 HashMap和 LinkedHashMap 存储数据的速度比直接使用 TreeMap 要快，存取效率要高。当完成了所有的元素的存放后，我们再对整个的 Map中的元素进行排序。这样可以提高整个程序的运行的效率，缩短执行时间。
需要注意的是，TreeMap中是根据键（key）进行排序的，而如果我们要使用TreeMap来进行正常的排序的话，key中存放的对象必须实现Comparable。
需要注意的是，TreeMap中是根据键（key）进行排序的，而如果我们要使用TreeMap来进行正常的排序的话，key中存放的对象必须实现Comparable。
|
Collection/Map
|
接口
|
成员重复性
|
元素存放顺序（ Ordered/Sorted ）
|
元素中被调用的方法
|
基于那中数据结构来实现的
|
|
HashSet
|
Set
|
Unique elements
|
No order
|
equals()
hashCode()
|
Hash 表
|
|
LinkedHashSet
|
Set
|
Unique elements
|
Insertion order
|
equals()
hashCode()
|
Hash 表和双向链表
|
|
TreeSet
|
SortedSet
|
Unique elements
|
Sorted
|
equals()
compareTo()
|
平衡树（Balanced tree ）
|
|
ArrayList
|
List
|
Allowed
|
Insertion order
|
equals()
|
数组
|
|
LinkedList
|
List
|
Allowed
|
Insertion order
|
equals()
|
链表
|
|
Vector
|
List
|
Allowed
|
Insertion order
|
equals()
|
数组
|
|
HashMap
|
Map
|
Unique keys
|
No order
|
equals()
hashCode()
|
Hash 表
|
|
LinkedHashMap
|
Map
|
Unique keys
|
Key insertion order/Access order of entries
|
equals()
hashCode()
|
Hash 表和双向链表
|
|
Hashtable
|
Map
|
Unique keys
|
No order
|
equals()
hashCode()
|
Hash 表
|
|
TreeMap
|
SortedMap
|
Unique keys
|
Sorted in key order
|
equals()
compareTo()
|
平衡树（Balanced tree ）
|
如何选择？
1 、容器类和 Array的区别、择取
* 容器类仅能持有对象引用（指向对象的指针），而不是将对象信息 copy 一份至数列某位置。
* 一旦将对象置入容器内，便损失了该对象的型别信息。
2 * 在各种 Lists 中，最好的做法是以 ArrayList作为缺省选择。当插入、删除频繁时，使用 LinkedList() ；
Vector总是比 ArrayList 慢，所以要尽量避免使用。
* 在各种 Sets 中，HashSet 通常优于TreeSet （插入、查找）。只有当需要产生一个经过排序的序列，才用 TreeSet 。
TreeSet存在的唯一理由：能够维护其内元素的排序状态。
* 在各种 Maps 中
HashMap用于快速查找。
* 当元素个数固定，用 Array ，因为Array 效率是最高的。
结论：最常用的是ArrayList，HashSet ，HashMap，Array 。而且，我们也会发现一个规律，用 TreeXXX都是排序的。
注意：
1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。
2、Set和Collection拥有一模一样的接口。
3、List，可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)...。(add/get)
4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。
5、Map用 put(k,v) / get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。
6、Map中元素，可以将key序列、value序列单独抽取出来。
使用keySet()抽取key序列，将map中的所有keys生成一个Set。
使用values()抽取value序列，将map中的所有values生成一个Collection。
为什么一个生成Set，一个生成Collection？那是因为，key总是独一无二的，value允许重复。
1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。
2、Set和Collection拥有一模一样的接口。
3、List，可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)...。(add/get)
4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。
5、Map用 put(k,v) / get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。
6、Map中元素，可以将key序列、value序列单独抽取出来。
使用keySet()抽取key序列，将map中的所有keys生成一个Set。
使用values()抽取value序列，将map中的所有values生成一个Collection。
为什么一个生成Set，一个生成Collection？那是因为，key总是独一无二的，value允许重复。