Java 容器：认识容器

容器是 Java 学习里很重的一块。刚开始会觉得难，用熟了就顺。容器类主要由两个接口派生：Collection 和 Map。

先把两个容易混的名字分开：Collection 是容器层次的根接口；Collections 是一个工具类，提供处理容器的静态方法。

一、Collection vs Collections

JDK 不提供 Collection 的直接实现，只提供更具体的子接口实现（Set、List）。那 Collection 接口本身有什么用？所有通用容器都遵守它：实现类提供两个「标准」构造——无参构造，以及一个参数类型为 Collection 的构造，用来复制出一份元素相同的新集合。因为大家都认这个接口，容器之间才能互相拷贝。

二、Collection 的类层次结构

下面是 Collection 一侧的层次图：

Set

不含重复元素（含可变对象）的 Collection，无序。不包含满足 a.equals(b) 的元素对，最多一个 null。实现：EnumSet、HashSet、TreeSet 等。

List

有序 Collection（序列），元素可以重复。通常允许 e1.equals(e2) 的一对元素；若允许 null，通常允许多个 null。实现：ArrayList、LinkedList、Vector、Stack 等。

Queue

一类是双端队列，头尾都能插入和移除：ArrayDeque、LinkedBlockingDeque、LinkedList。另一类是阻塞队列，满了再插会抛异常：ArrayBlockingQueue、PriorityBlockingQueue、LinkedBlockingQueue。接口本身未必声明阻塞方法，实现类会扩展。

三、Map 的类层次结构

Map 一侧的层次图：

Map 是键值对集合：不能有重复键，每个键最多映射到一个值。该接口取代了 Dictionary 抽象类。实现：HashMap、TreeMap、Hashtable、Properties、EnumMap。

四、容器接口小结

五、代码样例

HashMap、HashSet、LinkedList、ArrayList、TreeMap、TreeSet 放在一起跑：

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.TreeMap;

import java.util.TreeSet;



@SuppressWarnings("unchecked")

public class CollectionAll

{



    public static void main(String[] args)

    {

        printLists();



        printSets();



        printMaps();

    }



    private static void printLists()

    {

        List<String> a1 = new ArrayList<String>();

        a1.add("List");

        a1.add("Set");

        a1.add("Queue");

        a1.add("Map");

        System.out.println("ArrayList Elements:");

        System.out.print("\t" + a1 + "\n");



        List<String> l1 = new LinkedList<String>();

        l1.add("List");

        l1.add("Set");

        l1.add("Queue");

        l1.add("Map");

        System.out.println("LinkedList Elements:");

        System.out.print("\t" + l1 + "\n");

    }

    @SuppressWarnings("rawtypes")

    private static void printSets()

    {

        Set h1 = new HashSet<String>();

        h1.add("List");

        h1.add("Set");

        h1.add("Queue");

        h1.add("Map");

        System.out.println("HashSet Elements:");

        System.out.print("\t" + h1 + "\n");



        Set t1 = new TreeSet<String>();

        t1.add("List");

        t1.add("Set");

        t1.add("Queue");

        t1.add("Map");

        System.out.println("TreeSet Elements:");

        System.out.print("\t" + t1 + "\n");

    }



    private static void printMaps()

    {

        Map<String, String> h1 = new HashMap<String, String>();

        h1.put("List", "ArrayList");

        h1.put("Set", "HashSet");

        h1.put("Queue", "PriorityQueue");

        h1.put("Map", "HashMap");

        System.out.println("HashMap Elements:");

        System.out.print("\t" + h1 + "\n");



        Map<String, String> t1 = new TreeMap<String,String>();

        t1.put("List", "ArrayList");

        t1.put("Set", "HashSet");

        t1.put("Queue", "PriorityQueue");

        t1.put("Map", "HashMap");

        System.out.println("TreeMap Elements:");

        System.out.print("\t" + t1 + "\n");



    }

}

控制台大致如下（HashSet / HashMap 无序，TreeSet / TreeMap 按键有序）：

ArrayList Elements:
[List, Set, Queue, Map]
LinkedList Elements:
[List, Set, Queue, Map]
HashSet Elements:
[Map, Queue, Set, List]
TreeSet Elements:
[List, Map, Queue, Set]
HashMap Elements:
{Map=HashMap, Queue=PriorityQueue, Set=HashSet, List=ArrayList}
TreeMap Elements:
{List=ArrayList, Map=HashMap, Queue=PriorityQueue, Set=HashSet}

六、常见实现的对比

出处：http://blog.csdn.net/softwave/article/details/4166598。

Vector 和 ArrayList

• Vector 线程同步、安全；ArrayList 异步、不安全。不考虑线程安全时 ArrayList 更快。
• 空间不够时 Vector 按当前长度 100% 扩，ArrayList 按 50% 扩。数据量很大时 Vector 扩容次数可能更少。
• 按指定位置查找两者都是 O(1)。移动指定位置的数据是 O(n−i)，这时更该考虑 LinkedList：移动 O(1)，按位置查找 O(i)。

ArrayList 和 Vector 都用数组存数据，数组容量大于实际元素以便插入。按序号索引快，插入要搬内存所以慢。Vector 用了 synchronized，性能差一截。LinkedList 用双向链表，按序号要遍历，插入只改前后指针，插入更快。

ArrayList 和 LinkedList

• ArrayList 基于动态数组，LinkedList 基于链表。
• 随机访问 get / set，ArrayList 更好，LinkedList 要移动指针。
• 新增删除 add / remove，LinkedList 通常更占优，ArrayList 要搬数据。

只插删一条时，ArrayList 有时反而更快；批量随机插删时 LinkedList 会明显领先，因为 ArrayList 每插一条都要移动插入点之后的所有数据。

HashMap 与 TreeMap

• HashMap 靠 hashCode 快速查找，迭代顺序不固定；TreeMap 保持固定顺序（自然序或比较器），需要有序结果就用它。
• 集合框架提供两种常规 Map：HashMap 和 TreeMap（TreeMap 实现 SortedMap）。
• 插入、删除、定位元素，HashMap 最好；按自然序或自定义顺序遍历键，用 TreeMap。HashMap 要求键类正确实现 hashCode() 和 equals()。TreeMap 没有调优选项，树总保持平衡。

Hashtable 与 HashMap

• 历史：Hashtable 基于旧的 Dictionary；HashMap 是 Java 1.2 引进的 Map 实现。
• 同步：Hashtable 线程安全；HashMap 不是。
• 空值：只有 HashMap 允许 null 作为 key 或 value。

一句话总结：Collection 管单列，Map 管键值；选实现时先问：要不要同步、要不要有序、主要是查还是插。