Java Collections Framework - Java集合框架之概要

一、概述 在Java语言中，Java语言的设计者对常用的数据结构和算法做了一些规范（接口）和实现（具体实现接口的类）。所有抽象出来的数据结构和操作（算法）统称为Java集合框架（Java Collection Framework）。 Java程序员在具体应用时，不必考虑数据结构和算法实现细节，只需要用这些类创建出来一些对象，然后直接应用就可以了。这样就大大提高了编程效率。

二，List和Set Java集合框架的基本接口/类层次结构： 

java.util.Collection [I] 

+--java.util.List [I] 

   +--java.util.ArrayList [C] 

   +--java.util.LinkedList [C] 

   +--java.util.Vector [C] 

      +--java.util.Stack 

+--java.util.Set [I] 

   +--java.util.HashSet [C] 

   +--java.util.SortedSet [I] 

      +--java.util.TreeSet [C] 

java.util.Map 

+--java.util.SortedMap [I] 

   +--java.util.TreeMap [C] 

+--java.util.Hashtable [C] 

+--java.util.HashMap [C] 

+--java.util.LinkedHashMap [C] 

+--java.util.WeakHashMap [C] 

[I]：接口 

[C]：类 

Collection是集合接口         |————Set子接口:无序，不允许重复。         |————List子接口:有序，可以有重复元素。   区别：Collections是集合类   Set和List对比： Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。 List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

  同时， List 还提供一个 listIterator() 方法，返回一个 ListIterator 接口对象，和 Iterator 接口相比， ListIterator 添加元素的添加，删除，和设定等方法，还能向前或向后遍历。  

Set和List具体子类： Set  |————HashSet：以哈希表的形式存放元素，插入删除速度很快。   List  |————ArrayList：动态数组  |————LinkedList：链表、队列、堆栈。   Array和java.util.Vector Vector是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。 三，对集合操作的工具类  Java提供了java.util.Collections，以及java.util.Arrays类简化对集合的操作 

java.util.Collections主要提供一些static方法用来操作或创建Collection，Map等集合。 

java.util.Arrays主要提供static方法对数组进行操作。 

四、集合框架之外的Map接口

Map将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射一个值。

Map接口是Dictionary（字典）抽象类的替代品。

Map 接口提供三种collection 视图，允许以键集、值集合或键-值映射关系集的形式查看某个映射的内容。映射的顺序 定义为迭代器在映射的 collection 视图中返回其元素的顺序。某些映射实现可明确保证其顺序，如 TreeMap 类；某些映射实现则不保证顺序，如 HashMap 类。

有两个常见的已实现的子类：

HashMap：基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

TreeMap：它实现SortedMap 接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序 进行排序（参见 Comparable），或者按照创建时所提供的比较器进行排序。

Hashtable：此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。

五、线程安全类

在集合框架中，有些类是线程安全的，这些都是JDK1.1中的出现的。在JDK1.2之后，就出现许许多多非线程安全的类。

下面是这些线程安全的同步的类：

Vector：就比ArrayList多了个同步化机制（线程安全）。

Statck：堆栈类，先进后出。

Hashtable：就比HashMap多了个线程安全。

Enumeration：枚举，相当于迭代器。

除了这些之外，其他的都是非线程安全的类和接口。

线程安全的类其方法是同步的，每次只能一个访问。是重量级对象，效率较低。对于非线程安全的类和接口，在多线程中需要程序员自己处理线程安全问题。

六，

1. Hash表

Hash表是一种数据结构，用来查找对象。Hash表为每个对象计算出一个整数，称为Hash Code(哈希码)。Hash表是个链接式列表的阵列。每个列表称为一个buckets(哈希表元)。对象位置的计算　index = HashCode % buckets (HashCode为对象哈希码，buckets为哈希表元总数)。

当你添加元素时，有时你会遇到已经填充了元素的哈希表元，这种情况称为Hash Collisions(哈希冲突)。这时，你必须判断该元素是否已经存在于该哈希表中。

如果哈希码是合理地随机分布的，并且哈希表元的数量足够大，那么哈希冲突的数量就会减少。同时，你也可以通过设定一个初始的哈希表元数量来更好地控制哈 希表的运行。初始哈希表元的数量为　buckets = size * 150% + 1 (size为预期元素的数量)。

如果哈希 表中的元素放得太满，就必须进行rehashing(再哈希)。再哈希使哈希表元数增倍，并将原有的对象重新导入新的哈希表元中，而原始的哈希表元被删 除。load factor(加载因子)决定何时要对哈希表进行再哈希。在Java编程语言中，加载因子默认值为0.75，默认哈希表元为101。

2. Comparable接口和Comparator接口

在“集合框架”中有两种比较接口：Comparable接口和Comparator接口。像String和Integer等Java内建类实现 Comparable接口以提供一定排序方式，但这样只能实现该接口一次。对于那些没有实现Comparable接口的类、或者自定义的类，您可以通过 Comparator接口来定义您自己的比较方式。

3. Comparable接口

在java.lang包中，Comparable接口适用于一个类有自然顺序的时候。假定对象集合是同一类型，该接口允许您把集合排序成自然顺序。

(1) int compareTo(Object o): 比较当前实例对象与对象o，如果位于对象o之前，返回负值，如果两个对象在排序中位置相同，则返回0，如果位于对象o后面，则返回正值

在 Java 2 SDK版本1.4中有二十四个类实现Comparable接口。下表展示了8种基本类型的自然排序。虽然一些类共享同一种自然排序，但只有相互可比的类才能排序。

类	排序
BigDecimal,BigInteger,Byte, Double, Float,Integer,Long,Short	按数字大小排序
Character	按 Unicode 值的数字大小排序
String	按字符串中字符 Unicode 值排序

利用Comparable接口创建您自己的类的排序顺序，只是实现compareTo()方法的问题。通常就是依赖几个数据成员的自然排序。同时类也应该覆盖equals()和hashCode()以确保两个相等的对象返回同一个哈希码。

4. Comparator接口

若一个类不能用于实现java.lang.Comparable，或者您不喜欢缺省的Comparable行为并想提供自己的排序顺序(可能多种排序方式)，你可以实现Comparator接口，从而定义一个比较器。

(1)int compare(Object o1, Object o2): 对两个对象o1和o2进行比较，如果o1位于o2的前面，则返回负值，如果在排序顺序中认为o1和o2是相同的，返回0，如果o1位于o2的后面，则返回正值

“与Comparable相似，0返回值不表示元素相等。一个0返回值只是表示两个对象排在同一位置。由Comparator用户决定如何处理。如果两个不相等的元素比较的结果为零，您首先应该确信那就是您要的结果，然后记录行为。”

(2)boolean equals(Object obj): 指示对象obj是否和比较器相等。

“该方法覆写Object的equals()方法，检查的是Comparator实现的等同性，不是处于比较状态下的对象。”