Java 集合框架的体系

一、概述

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


二、集合框架的层次结构


Java中集合类定义主要是在java.util.*包下面，在java中常用的集合在系统中定义了三大接口：
1、Collection接口
List和Set都继承自Collection接口：
（1）Set接口
Set是最简单的一种集合，它的对象不按特定的方式排序，只是把对象加入到集合中，就像是往口袋里放东西。，集中不能有重复的对象。对集中的成员访问和操作都是通过对象的引用来进行的。
java.util.Set接口及其子类，set提供的是一个无序的集合；
常用的实现类有：HashSet、TreeSet 无序，不允许重复。

（2）List接口
List的主要特征是其对象以线性的方式存储，没有特定的顺序，只有一个开头和结尾，但是它与根本没有顺序的Set集合是不同的。List提供的有序访问的方法，可以根据List中对象放入时的次序来查找对象。
java.util.List接口及其子类，List提供的是一个有序的集合；
常用的实现类有：ArrayList、LinkedList、Vector 有序，可以有重复元素。

2、 Map接口
现实生活中，我们常常会看到这样一种集合：IP地址和主机名，身份证证号和个人等，这种一一对应的关系就叫做映射。Java提供了Map接口来存放这种对象关系的对象。

Map中存入的对象是一对一对的，即每个对象和它的名字（键）关联在一起，其中名字我们称之为Key（键），对象称为value,他们在Map中是一一对应的关系。

在Map中，键不能重复，但是值可以重复。
java.util.Map接口及其子类，Map提供了一个映射关系的集合数据结构。
常用的实现类有：HashMap、TreeMap

3、 Dictionary类
常用的子类有：HashTable


三、常用的实现类介绍


1. HashSet ：以哈希表的形式存放元素，插入删除速度很快。
(1) 概述：HashSet底层是用哈希表实现的，可理解为数学中的集合，是无序且不能存放重复元素的。这里的重复是什么概念呢？重复指的A.equals(B)成立。
(2) 支持的操作：增——add（）、删——remove（Object）、查——通过Iterator对象来遍历。因为HashSet是无序的，因此不可以直接通过下标来访问，也没有改变其中某个元素的功能，若要想改变，实际上可以先删除那个需要改变的元素，然后再增加那个需要添加的元素便可。

2. TreeSet
(1) 概述：与HashSet类似，但是TreeSet支持排序，可通过Collections的sort（）方法对TreeSet中的元素进行排序，默认是以正序排列的。若要实现反序排列，则在创建TreeSet时应该外构造器中传入Collections.reverseOrder()方法返回的Comparator对象。

3. LinkedList ：链表、队列、堆栈
(1) 概述：LinkedList底层是用链表实现的，是有序的数据结构，可以存放重复的元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
　　注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
(2) 支持的操作：增——add（）、删——remove（Object / int）、改——set（int，Object）、查——get（int），也可以通过iterator遍历子来遍历查询。

4. ArrayList ：动态数组
(1) 概述：ArrayList底层是用数组实现的，是一个可变数组，是有序的数据结构，可以存放重复的元素。其用法与LinkedList类似。每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

5. Vector ：一种老的动态数组，是线程同步的，效率很低
(1) 概述：Vector非常类似ArrayList，底层也是用数组实现的，但是Vector是同步的，ArrayList与LinkedList是非同步的。此外，每个向量（Vector）会试图通过维护 capacity 和 capacityIncrement 来优化存储管理。capacity 始终至少应与向量的大小相等；这个值通常比后者大些，因为随着将组件添加到向量中，其存储将按 capacityIncrement 的大小增加存储块。应用程序可以在插入大量组件前增加向量的容量；这样就减少了增加的重分配的量。

6. HashMap
（1）概述：HashMap底层是用哈希表实现的Map结构，即数据的存储形式都是以键值对
（key，value）来存储的。其中，key的值不能重复，value则可以。HashMap是无序的。HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。
（2）支持的操作：增——put（key，value），删——remove（key），查——get（key）。此外，entrySet（）方法返回此映射中包含的映射关系的 Set 视图。keySet（）方法返回此映射中包含的键的 Set 视图。values（）方法返回此映射中包含的值的 Collection 视图。

7. TreeMap
(1) 概述：TreeMap的用法与HashMap类似，但TreeMap支持排序。TreeMap是基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

8. HashTable
（1）概述：HashTable与HashMap类似


四、（附）Iterator迭代器（接口）


Iterator是获取集合中元素的过程，实际上帮助获取集合中的元素。
迭代器代替了 Java Collections Framework 中的 Enumeration。迭代器与枚举有两点不同：
迭代器允许调用方利用定义良好的语义在迭代期间从迭代器所指向的集合移除元素。
方法名称得到了改进。
Iterator仅有一个子接口ListIterator，是列表迭代器，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。ListIterator 没有当前元素；它的光标位置 始终位于调用 previous() 所返回的元素和调用 next() 所返回的元素之间。在长度为 n 的列表中，有 n+1 个有效的索引值，从 0 到 n（包含）。


五、使用各实现类时的注意事项：


1. 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

2. 如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。此外，同步的类有：Vector、HashTable，非同步的类有：LinkedList、ArrayList、HashSet、TreeSet、HashMap、TreeMap

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

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

5. 在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。因此，当你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他的集合操作类。比如，LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的——O(1)，但它在索引一个元素时却比较慢——O(i),其中i是索引的位置。最后，在《Practical Java》一书中Peter Haggar建议使用一个简单的数组（Array）来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组(Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。

6. 迭代器：Vector和Hashtable使用Enumeration，ArrayList和HashMap使用Iterator。迭代器(Iterator) 给我们提供了一种通用的方式来访问集合中的元素。Iterator类中包含hasNext()、next()、remove()，对于一些集合类，它们没有提供get()方法，则可以通过迭代器来返回元素

7. 利用ArrayList的toArray()返回一个数组，Arrays.asList()返回一个列表，这两种方法可以看作是数组与列表之间的桥梁。

8. 集合中的remove（Object obj）、indexOf（Object obj）、contains（Object obj）等方法实际上都要用到equals方法，要逐个比较之后才能确定目标对象

9. 所有可以排序的类的对象，都实现了java.lang.Comparable接口

10. 如何选择数据结构？衡量标准：读的效率和改的效率。
（1）Array读快改慢
（2）Linked改快读慢
（3）Hash介于两者之间

11. 对于Map中的put（key，value）方法，将指定的值与此映射中的指定键关联（可选操作）。如果此映射以前包含一个该键的映射关系，则用指定值替换旧值（当且仅当 m.containsKey(k) 返回 true 时，才能说映射 m 包含键 k 的映射关系），这就有点类似于更新value值了，此外，put方法会返回原有的value或者null。