Java容器

Java容器

1  容器

1.1  容器概念

    百度百科的解释是用来包装或装载物品的贮存器(如箱、罐、坛)或者成形或柔软不成形的包覆材料。这里说的容器是看得见、摸得着的实物。

1.2  Java容器的概念

    Java容器是用来存储和组织其他对象的对象。在写程序的时候，常常需要对大量的对象引用进行管理。为了实现有效的归类管理，我们常常将同类的引用放置在同一数据容器中。由于数据容器中存放了随时可能需要使用到的对象引用，所以一般的数据容器要都要能能提供方便的查询、遍历、修改等基本接口功能。

1.3  编程容器产生背景

    早期的OOP语言都通过数组的方式来实现对引用集的集中管理和维护。但是数组方式下，数组大小需要提前被确定，并不允许修改大小，导致其作为一种灵活的数据容器的能力的功能大为下降，编程容器的概念就在这时期应运而生，解决对象的管理问题。

2  Java容器

    Java中提供了丰富的数据容器以满足程序员多样化的需求。容器按接口可以分为两大类：Collection和Map。

2.1  类继承关系

    Java.util中的容器又被称为Java Collections framework。虽然被称为框架，但是其主要目的是提供一组接口尽量简单而且相同、并且尽量高效、以便于开发人员按照场景选用，而不是自己重复实现的类。

    Collection及其继承关系如下图：

    注释：

        1  Collection接口并不是一个根接口，它的超级接口是Iterator，需要提供其遍历、移除元素(可选操作)的能力。

        2  Collection接口定义了基本的容器操作方法。

        3  remove()和contains()判断元素是否相等的依据是类似的。

            对于remove(Object o)，若Collection中包含的元素e，满足(o==null ? e==null : o.equals(e))，移除其中的一个；

            对于contains(Object o)，若Collection中包含至少一个或多个元素e，满足(o==null ? e==null : o.equals(e))，则返回true。

        4  AbstractCollection抽象类实现了一部分Collection接口的方法，主要是基于iterator实现的，如remove()、toArray()，以及利用本身的属性size实现的size()。如果读一下源码，可以发现虽然AbstractCollection利用add()实现了addAll()，但是add()本身的实现是直接抛UnsupportedOperationException异常的。实际上add()是一种“可选操作”，目的是延迟到需要时再实现。

2.2  List

    List从通用的Collection接口衍生，List中的元素是有序的，因而我们可以按序访问List中的元素，以及访问指定位置上的元素。对于“按顺序遍历访问元素”的需求，使用List的超级接口Iterator即可以做到，这也是对应抽象类AbstractList中的实现；而访问特定位置的元素（也即按索引访问）、元素的增加和删除涉及到了List中各个元素的连接关系，并没有在AbstractList中提供。

2.2.1  ArrayList

    ArrayList是最常用的List的实现，其包装了一个用于存放元素的数组，并用size属性来标识该容器里的元素个数，而非这个被包装数组的大小。如果对数组有所了解，很容易理解ArrayList的元素是怎么编排的，各个数组的元素如何随机访问（通过索引）、元素之间如何跳转（索引增减）。阅读源码可以发现，这个数组用transient关键字修饰，表示其不会被序列化。当然，ArrayList的元素最终还是会被序列化的，要不然，这个最常用的List之一，不能持久化、不能网络传输，简直不可想象。在序列化/反序列化时，会调用ArrayList的writeObject()/readObject()方法，将该ArrayList中的元素（即0...size-1下标对应的元素）写入流/从流读出。这样做的好处是，只保存/传输有实际意义的元素，最大限度的节约了存储、传输和处理的开销。

ArrayList其实就相当于顺式存储，它包装了一个数组 Object[]，当实例化一个ArrayList时，一个数组也被实例化，当向ArrayList中添加对象时，数组的大小也相应的改变。

2.2.1.1  ArrayList有以下特点

    A  快速随即访问，你可以随即访问每个元素而不用考虑性能问题，通过调用get(i)方法来访问下标为i的数组元素。

    B  向其中添加对象速度慢，当你创建数组时并不能确定其容量，所以当改变这个数组时就必须在内存中做很多事情。

    C  操作其中对象的速度慢，当你要向数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。

    D  ArrayList是线程不安全的，可以使用synchronized关键字。

       List list = Collections.synchronizedList(new ArrayList(...));

    E  ArrayList的clone()是浅拷贝，元素的引用和拷贝前相同。

2.2.2  Vector

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

2.2.3  Stack

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

2.3  Set

    Set接口模仿了数学概念上的set，各个元素不要求重复。除了这一点，几乎和Collection本身是一样的。

    Set接口有一个直接子接口SortedSet，该接口要求Set中所有元素有序。和通过Iterable接口依次访问所有元素的“有序”不同，这个“有序”要求Set包括一个比较器，可以判断两个元素的大于、小于或等于关系。此外，该接口提供了访问第一个元素、访问最后一个元素、访问一定范围内元素的方法。SortedSet的子接口NavigableSet进一步扩展了这个系列的方法，提供了诸如返回大于/小于元素E的第一个元素的方法。

由于Set的操作与底层的实现关联性很强，AbstractSet中实现的方法有限，在Java1.6中只有equals()、hashCode()、removeAll()进行了实现。

2.3.1  Set特点

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

      Set容器类主要有HashSet和TreeSet等。

2.3.2  HashSet

    HashSet之所以命名中包含了“Hash”，是因为其底层是用HashMap实现的。Map有个特点，各个Key是唯一的，这和Set的元素唯一很类似。对HashSet的元素E进行的操作，实际上是对其包装的HashMap中对应的的操作，其中PRESENT是一个private static final的Object。因此，HashSet的原理，放到HashMap那一块来研究。

HashSet有一个很特别的构造方法：HashSet(int initialCapacity, float loadFactor, boolean dummy)。这个方法第三个参数的唯一作用是，与其他两个参数的构造方法相区分。使用这个构造方法，在底层使用的是HashMap的子类LinkedHashMap。而LinkedHashSet，正是使用了这个构造方法，在内部创建并封装了一个LinkedHashMap而非一般的HashMap。

HashSet的包装的HashMap也使用transient关键字修饰，采用了和ArrayList一样的序列化策略。

2.3.3  TreeSet

    TreeSet是SortedSet的一个实现，也是其子接口NavigableSet的实现。与HashSet/LinkedHashSet类似，TreeSet底层封装了一个NavigableMap，同样使用transient修饰，以及序列化策略。

2.4  Queue

    Queue和List有两个区别：前者有“队头”的概念，取元素、移除元素、均为对“队头”的操作（通常但不总是FIFO，即先进先出），而后者只有在插入时需要保证在尾部进行；前者对元素的一些同一种操作提供了两种方法，在特定情况下抛异常/返回特殊值——add()/offer()、remove()/poll()、element()/peek()。不难想到，在所谓的两种方法中，抛异常的方法完全可以通过包装不抛异常的方法来实现，这也是AbstractQueue所做的。

Deque接口继承了Queue，但是和AbstractQueue没有关系。Deque同时提供了在队头和队尾进行插入和删除的操作。

2.4.1  PriorityQueue

    PriorityQueue用于存放含有优先级的元素，插入的对象必须可以比较。该类内部同样封装了一个数组。与其抽象父类AbstractQueue不同，PriorityQueue的offer()方法在插入null时会抛空指针异常——null是无法与其他元素比较通常意义下的优先级的；此外，add()方法是直接包装了offer()，没有附加的行为。

由于其内部的数据结构是数组的缘故，很多操作都需要先把元素通过indexOf()转化成对应的数组下标，再进行进一步的操作，如remove()、removeEq()、contains()等。其实这个数组保持优先级队列的方式，是采用堆(Heap)的方式，具体可以参考任意一本算法书籍，比如《算法导论》等，这里就不展开解释了。和堆的特性有关，在寻找指定元素时，必须从头至尾遍历，而不能使用二分查找。

2.4.2  LinkedList

    LinkedList既是List，也是Queue(Deque)相当于一个双向的链表结构，用链式存储，它是通过节点直接彼此连接来实现的。每一个节点都包含前一个节点和后一个节点的引用及其节点存储的值。当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可，当删除记录时也一样。

2.4.2.1  LinkedList有以下有特点

    A  操作其中对象的速度快，只需要改变连接，新的节点可以在内存中的任何地方。

    B  不能随即访问，虽然存在get()方法，但是这个方法是通过遍历接点来定位的，所以速度慢。

    C  对首部和尾部的插入都支持，但继承自Collection接口的add()方法是在尾部进行插入。

    D  LinkedList是线程不安全的，可以使用synchronized关键字。

        List list = Collections.synchronizedList(new LinkedList(...));

    E  LinkedList的clone()是浅拷贝，元素的引用和拷贝前相同。
3  Map

    Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口 从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

    Map及其继承关系如下图：

3.1  Map的常用方法

3.1.1  添加，删除操作

    Object put(Object key, Object value)  // 向集合中加入元素

    Object remove(Object key)  // 删除与KEY相关的元素

    void putAll(Map t)        // 将来自特定映像的所有元素添加给该映像  

    void clear()     // 从映像中删除所有映射

3.1.2  查询操作

    Object get(Object key)  // 获得与关键字key相关的值 。

    注意：Map集合中的键对象不允许重复，也就说，任意两个键对象通过equals()方法比较的结果都是false，但是可以将任意多个键独享映射到同一个值对象上。

3.1.3  功能方法

    put(Object key, Object value)  // 添加一个“值”(想要得东西)和与“值”相关联的“键”(key)(使用它来查找)。get(Object key) 返回与给定“键”相关联的“值”。

可以用containsKey()和containsValue()测试Map中是否包含某个“键”或“值”。

3.2  Map的分类

    标准的Java类库中包含了几种不同的Map：HashMap, TreeMap, LinkedHashMap, WeakHashMap, IdentityHashMap。它们都有同样的基本接口Map，但是行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。

    执行效率是Map的一个大问题。看看get()要做哪些事，就会明白为什么在ArrayList中搜索“键”是相当慢的。而这正是HashMap提高速度的地方。HashMap使用了特殊的值，称为“散列码”(hash code)，来取代对键的缓慢搜索。“散列码”是“相对唯一”用以代表对象的int值，它是通过将该对象的某些信息进行转换而生成的。所有Java对象都能产生散列码，因为hashCode()是定义在基类Object中的方法。HashMap就是使用对象的hashCode()进行快速查询的。此方法能够显着提高性能。

3.2.1  HashMap

    HashMap是Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor，以调整容器的性能。

3.2.2  LinkedHashMap

    LinkedHashMap类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。

3.2.3  TreeMap

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

3.2.4  WeakHashMap

    WeakHashMap 是弱键(weak key)Map，Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。

3.2.5  IdentifyHashMap

    IdentifyHashMap是使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。

3.3  Map接口和AbstractMap抽象类

    Map接口除了增加映射、根据key获取value、判断映射中的key或value是否存在、删除映射的基本方法外，还包含了返回包含所有key的Set、包含所有value的collection的方法。由于key不能重复，返回的Collection自然具有Set的属性，很适合用Set返回。而value则不行。

    与其他Collection接口不同，Map接口中有一个子接口：Entry。Entry代表了一个映射，包含了key和value两部分，同时，一个Enry的key没有提供修改方法，而value允许修改。需要说明的是，如果用一个可变对象作为Map的key，若变化后equals()与之前的行为不同，那么映射的行为是不确定的（JDK1.6文档）。

    对于抽象类AbstractMap，大部分实现的方法借助了将所有entry组成的set返回的抽象方法entrySet()：size()、isEmpty()（使用size()）、containsValue()、containsKey()、get()、clear()、keySet()、values()等。而remove()、removeAll()、retainAll()、clear()、toString()则借助了抽象方法iterator()。

values()返回值value的是一个匿名内部类实现的AbstractCollection。value在第一次访问时创建，在后续所有访问中返回。虽然不进行元素的同步，其引用几乎总是不变的，但返回值的行为会随着Map中的元素变化。

    对于Map.Entry，AbstractMap中实现了两个键值对类型：SimpleEntry和SimpleImmutableEntry。后者与前者的区别是，不允许setValue()，调用该方法抛出UnsupportedOperationException异常。

4  总结

4.1  List总结

    A  如果涉及到堆栈，队列等操作，应该考虑用List。

    B  对于需要快速插入，删除元素，应该使用LinkedList。

    C  如果需要快速随机访问元素，应该使用ArrayList。

4.1.1  数据增长

    从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度。

    A  Vector缺省情况下自动增长原来一倍的数组长度。

    B  ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。

    注意：所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

4.1.2  单线程和多线程

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

    A  Vector这个类中的一些方法保证了Vector中的对象是线程安全的。

    B  ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的。

    注意：因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。

4.1.3  时间复杂度

    在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。

如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长，这个时间时间O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。

因为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他的集合操作类。比如，LinkedList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的O(1)，但它在索引一个元素的使用缺比较慢O(i)，其中i是索引的位置。使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkedList也会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。

    注释：在《Practical Java》一书中Peter Haggar建议使用一个简单的数组（Array）来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组(Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。

4.1.4  使用List接口

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

4.2  Set总结

    HashSet总是比TreeSet 性能要好。而后者存在的理由就是它可以维持元素的排序状态。所以，如果需要一个排好序的Set时，才应该用TreeSet。

    HashSet/LinkedHashSet的底层实际是HashMap/LinkedHashMap。HashMap和一般的散列表实现方式相同，用数组存放相同哈希值的元素所组成队列的首元素，队列的元素是Entry，包括了key、value、hash值、next等属性。寻找指定key时，先做哈希，根据哈希值找到数组中对应的队列头，遍历队列找出key及对应的value。

4.3  map总结

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

4.3.1  HashMap、LinkedHashMap和WeakHashMap

    由于HashMap允许null作为key，这个key没办法做哈希值的计算，只能遍历哈希值数组，找到首元素的key为null的队列。这个实现可以参考私有方法getForNullKey()。

    LinkedHashMap与HashMap的关系并不像LinkedList和ArrayList那样。从结构上来看，LinkedHashMap仅仅是把所有的Entry组成了一个双向链表。这样，在迭代遍历时，可以使用插入顺序或LRU顺序访问所有元素（通过设置accessOrder标记位）。

    WeakHashMap和HashMap很类似，其内部包含了一个ReferenceQueue，并且它的Entry是继承自WeakReference的。通过这种方式，在clear()、resize()、size()、getTable()时，都会调用expungeStaleEntries()方法，垃圾回收掉不再使用的映射关系。

4.3.2  SortedMap和TreeMap

    SortedMap中的所有元素都是排过序的。这个“排序”不同于LinkedHashMap中将所有元素组织成一个链表，而是指任意任意两个元素都可以比较大小关系，并根据这个比较规则Comparator进行排序。更准确的说，是键的大小关系。建立在有序的基础上，SortedMap接口中包含了返回部分Map的方法subMap(K fromKey, K toKey)、headMap(K toKey)、tailMap(K fromKey)以及首尾key的方法firstKey()、lastKey()。

    TreeMap实际上使用了红黑树，保存了树的根。TreeMap的元素插入、删除其实是红黑树节点的插入和删除。在元素有序的前提下，找到特定的key（以及对应的value）同样是使用了红黑树的查找方法。TreeMap是SortedMap的一个实现，其Compartor可以为null，这种情况下比较元素大小时调用元素自身的compareTo()方法。

参考链接：

http://www.cnblogs.com/wuyuegb2312/p/4458468.html

http://blog.csdn.net/dandanzmc/article/details/23447827

http://www.cnblogs.com/airwindow/archive/2012/06/24/2560196.html