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

参考链接： Java Collections框架

一、概述

  在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实现的等同性，不是处于比较状态下的对象。”