在日常开发中，我们时刻需要和数据打交道，而如何处理这些数据就成为编程中的重要内容了。在Java中我们可以使用“容器”来容纳和管理数据。顾名思义，生活中我们有锅碗瓢盆等容器来容纳物体，而程序中的“容器”也有类似的功能，我们可以使用它来容纳和处理数据。

在之前第八篇中讲了数组，但是数组并不能满足人们对于“管理和组织数据的需求”。所以引入容器这一概念，也称作集合。容器很好的解决了数组不灵活，不可以随时扩容的问题。下图为容器接口层次结构图，转自谷歌图片：

泛型

泛型的概念

为了更好的使用理解容器，首先需要了解下泛型的概念。

泛型是JDK1.5之后增加的，用于建立类型安全的集合。在使用了泛型的集合中，遍历时不必进行强制类型转换。

泛型的本质就是“数据类型的参数化”。可以把“泛型”理解为数据类型的一个占位符，即告诉编译器，再调用泛型时必须传入实际类型。

将容器比作垃圾桶，平常我们使用的垃圾桶中可以随便装任意的垃圾，而在使用泛型之后，我们就有了垃圾分类的功能，相同的类型才会放在同一种的垃圾桶中。

泛型的使用

在类的声明处可以增加泛型列表，如<T,E,V>可以使用任意的字符表示泛型，但是通常采用这3个字母。

声明泛型：

public class MyCollection<E>{  //E:表示泛型
    Object[] objs=new Object[5];
    public E get(int index) {  //E:表示泛型
        return (E) objs[index];
    }
    public void set(E e,int index){  //E:表示泛型
        objs[index] = e;
    }
}

泛型E像一个占位符一样表示未知的某个数据类型，在真正调用的时候将传入这个数据类型。

泛型的应用：

public class TestGenerics{
    public static void main(String[] args){
        //这里的“String”就是实际传入的数据类型
        MyCollection<String> mc=new MyCollection<String>();
        mc.set("123",0);
        mc.set("456",1);
        String str=mc.get(1);  //加了泛型，直接返回String类型，无需强制转换
        System.out.println(str);
    }
}

容器中的泛型

容器的相关类都定义了泛型，在开发工作中，使用容器类时都要使用泛型。这样，在容器中存储和读取数据时避免了大量的类型判断，更加便捷。

容器中使用泛型的例子：

public class Test {
    public static void main(String[] args){
        List<String> list=new ArrayList<String>();
        Set<Student> students=new HashSet<Student>();
        Map<Integer,String> map=new HashMap<Integer,String>();
        Iterator<Student> iterator=students.iterator();
    }
}

Collection接口

Collection表示一组对象，它是集中或收集的意思。Collection接口的两个子接口分别是List和Set。

下表示API中Collection接口中定义的方法：

因为List、Set是Collection的子接口，所以List、Set的实现类都有上面的方法。

List接口

List接口的概念

List是指有序、可重复的容器**。List接抠中包含了Collection接口中的所有方法，并且List接口增加了和索引相关的方法。

• 有序：List中的每个元素都有索引标记，可以根据元素的索引标记(在List中的位置)来访问元素，从而精确控制这些元素。
• 可重复：List允许加入重复的元素。即List允许e1.equals(e2)的元素重复的加入容器。

List接口中定义的方法

除了Collection接口中的方法，List还增加了跟顺序相关的方法，如下表：

ArrayList和LinkedList的特点和底层实现

ArrayList

• 特点：查询效率高，增删效率低，线程不安全。

• 底层实现：ArrayList底层使用Object数组来存储元素数据，所有的方法都是围绕这个核心的Object数组来开展的。

数组的长度是有限的，而ArrayList可以存放任意数量的对象，长度不受限制。

本质上，ArrayList是通过定义新的更大数组，并将旧数组中的内容复制到新数组来实现扩容的。ArrayList的Object数组默认初始化长度为10，如果存储满了这个数组，需要存储第11个对象时就会定义一个长度更大的新数组，并将原数组中的内容和新元素一起加入到新数组中。

LinkedList

• 特点：查询效率低，增删效率高，线程不安全
• 底层实现：LinkedList底层使用双向链表来实现存储，双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。

双链表的包含的三部分内容：

class Node{
    Node previous;
    Object element;
    Node next;
}

Vector向量

Vector底层是一个长度可以动态增长的对象数组，它的相关方法都进行了线程同步，所以线程安全，效率低。

List接口下选用哪个实现类？

1. 需要线程安全时，用Vector。
2. 不存在线程安全问题，并且查找较多时，用ArrayList(一般使用它)。
3. 不存在线程安全问题，但增加或删除元素较多时，用LinkedList。

Map接口

Map接口存储了键(key)-值(value)对信息。Map类中存储的“键值对”通过键来标识，所以“键对象”不能重复。

Map接口的实现类有HashMap、TreeMap、HashTable和Properties等。

下表为Map接口中常用的方法：

HashMap和HashTable

HashMap采用散列算法来实现，它是Map接口最常用的实现类。由于底层采用哈希表来存储数据，因此要求键不能重复，如果发生重复，新的键值对会替换旧的键值对。HashMap在查找、删除、修改方面的效率都非常高。

HashTable和HashMap用法几乎一样，底层实现也几乎一样，知识HashTable的方法添加了synchronized关键字以确保线程同步检查，效率较低，总结就是如下：

• HashMap： 线程不安全，效率高。允许key或value为null。
• HashTable： 线程安全，效率低。不允许key或value为null。

HashMap的底层实现

HashMap底层实现采用了哈希表。数据结构中由数组和链表来实现对数据的存储，它们的特点如下：

• 数组：占用空间连续；寻址容易，查询速度快。但是，增加和删除效率非常低。
• 链表：占用空间不连续；寻址困难，查询速度慢。但是，增加和删除效率非常高。

而哈希表的本质就是“数组+链表”，所以它就吸取了两者的优点，查询快，效率又高。

1.HashMap基本结构

哈希表的基本结构就是“数组+链表”。在HashMap中我们可以找到两个核心内容。

其一就是Entry[] table是HashMap的核心数组结构，被称为“位桶数组”。在源码中我们可以发现一个Entry对象存储了如下四部分内容：

• hash：键对象的hash值
• key：键对象
• value：值对象
• next：下一个节点

显而易见，每一个Entry对象是一个单向链表结构，Entry对象结构，如图所示：

Entry[]数组的结构(也是HashMap的结构)，如图所示：

2.存储数据的过程put(key,value)

• （1）首先应该获得key对象的hashcode：调用key对象的hashcode()方法继承与Object的方法，获得hashcode。

• （2）根据hashcode计算出hash值，该hash值应在[0,数组长度-1]区间中。

  hashcode是一个整数，根据既定的算法将转化后的hash值尽量的均匀地分布在[0,数组长度-1]区间中，以减少hash冲突，如下两种算法：

  • hash值=hashcode/hashcode

    采用这个算法后，hash值就一直为1，这时候，键值对对象全部存储到数组索引位置为1的位置，每一个存储的对象都会发生hash冲突，HashMap就由此退化成了一个“单向链表”。

  • hash值=hashcode%数组长度

    这种算法可以让hash值均匀分布在[0,数组长度-1]区间中。早期的HashTable就是采用这种算法。由于这种算法采用了除法，所以效率低下。JDK在后续更新中改进了算法，首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：hash值=hashcode&(数组长度-1)。

• （3）生成Entry对象：如上所述，一个Entry对象包含了四部分，我们现在已经有了hash值、key对象、value对象，还有最后一部分指向下一个Entry对象。下一个Entry对象next所对应的值就为null。

• （4）将Entry对象放到table数组中：如果本Entry对象对应的数组索引位置还没有Entry对象，则直接将该Entry对象存储进数组索引位置的第一位；如果对应索引位置已有Entry对象，则将已有Entry对象的next指向该Entry对象，形成单向链表。

综上所述，HashMap对应的就是一个存储链表的数组，根据hash值找到数组的索引位置，根据链表来存储Entry对象。JDK8中，当链表长度大于【8】时，链表就转换为红黑树，这样又大大的提高了查找的效率。

3.读取数据过程get(key)

• （1）获取key的hashcode，通过hash()散列算法得到hash值，进而找到数组的索引位置。

• （2）在链表上逐个比较key对象。调用equals()方法，将key对象的链表上所有节点的key对象进行比较，直到碰到返回true的节点对象为止。

• （3）返回equals()为true的节点对象的value对象。

4.扩容问题

HashMap的位桶数组初始大小为16，即数组区间在[0,15]中。在实际使用中，其大小显然是可变的。如果位桶数组中的元素个数达到0.75*数组的length时，就调整数组大小至原来的2倍。

扩容会消耗性能。扩容的本质就是定义一个更大的新数组，将原数组中的内容逐个复制到新数组中。

TreeMap的使用和底层实现

TreeMap是红黑二叉树的典型实现。观摩TreeMap的源码，我们可以发现其中有一行核心代码：

private transient Entry<K,V> root = null;

其中，root用来存储整个树的根节点，继续查看Entry(TreeMap的内部类)的代码，如下所示：

static final class Entry<K,V> implements Map.Entry<K,V>{
    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null;
    Entry<K,V> parent;
    boolean color = BLACK;
}

从中可以发现，Entry中存储了key、value、左节点、右节点、父节点以及节点颜色。TreeMap的put()/remove()方法中大量的使用了红黑树的理论。限于本人水平有限，需要了解红黑树等相关概念的可以参考数据结构的相关书籍。

TreeMap和HashMap的使用区别

TreeMap和HashMap同样实现了的Map接口，因此用法对于使用者来说没有区别。HashMap效率高于TreeMap；所以除非在需要Map中Key按照自然顺序排序时才选用TreeMap，其余我们都可采用HashMap。

Set接口

Set接口继承于Collection接口，Set接口中没有新增方法，所以在前面List中使用到的方法，在Set中仍然可以适用。

Set的主要特点是无序、不可重复。无序指的是Set中的元素没有索引，只能通过遍历的方式查找；不可重复指不允许加入重复的元素。即新元素如果和Set中的任意一个元素通过equals()方法返回true，那么它就无法加入到Set中，同理Set中仅能存在一个null元素；

Set常用的实现类有HashSet和TreeSet，一般常用HashSet。

HashSet的底层实现

HashSet底层其实是用HashMap实现的，本质上就是简化版都得HashMap，因此查询效率和增删效率都比较高。

//HashSet部分源码
public class HashSet<E> extends AbstractSet<E> 
    implements Set<E>, Cloneable,java.io.Serializable{
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

观摩HashSet源码，其中的map属性就是HashSet的核心。在其add()方法中，可以发现增加元素其实就是在map中put一个键值对，键对象就是这个元素，值对象就是PRESENT的Object对象。在Set中加入元素，本质上就是把这个元素作为key加入到内部的map中。

由于map中的key都是不可重复的，因此Set自然具备不可重复的特性。

TreeSet的底层实现

TreeSet的底层用TreeMap实现，本质上就是一个简化版的TreeMap，通过key来存储Set的元素。TreeMap内部需要对存储的元素进行排序，因此，对应的类需要实现Comparable接口。这样才能根据compareTo()方法来比较对象的大小，并进行内部的排序。

• 使用TreeSet使用的注意事项

1. 由于TreeSet底层是一种二叉查找树(红黑树)，需要对元素做内部排序。如果要放入TreeSet中的类没有实现Comparable接口，则会抛出java.lang.ClassCastException的异常。
2. TreeSet中不能放入null元素。

Iterator接口

Iterator接口可以让开发者实现对容器中对象的遍历

迭代器

所有实现Collection接口的容器类都有一个Iterator方法用以返回一个实现了Iterator接口的对象。

Iterator对象称为迭代器，可用于方便地实现对容器内元素的遍历。

Iterator接口定义了如下方法：

• boolean hasNext()：判断游标当前位置的下一个位置是否还有元素没有被遍历。
• Object next()：返回游标当前位置的下一个元素并将游标移动到下一个位置。
• void remove()：删除游标当前位置的元素，在执行完next后该操作只能执行一次。

迭代器遍历常用容器

迭代器提供了统一的遍历容器的方式。

迭代器遍历List

public static void testIteratorList() {
    List<String> list=new ArrayList<String>();
    list.add("aa");
    list.add("bb");
    list.add("cc");
    for (Iterator<String> iter=list.iterator();iter.hasNext();) {
        String temp=iter.next();  //把迭代器返回,返回泛型定义的类型
        //iter.next()方法把标示指向下一个.
        System.out.println(temp);
    }
}

迭代器遍历Set

public static void testIteratorSet() {
    Set<String> set=new HashSet<String>();
    set.add("AA");
    set.add("BB");
    set.add("CC");
    for(Iterator<String> iter=set.iterator();iter.hasNext();) {
        String temp=iter.next();
        System.out.println(temp);
    }
}

迭代器遍历Map

public static void testIteratorMap() {
    Map<Integer, String> map=new HashMap<Integer, String>();
    map.put(1, "123");
    map.put(2, "456");
    map.put(3, "789");

    //第一种遍历Map的方式
    Set<Entry<Integer, String>> setEntry=map.entrySet();  
    for (Iterator<Entry<Integer, String>> iterEntry=setEntry.iterator();iterEntry.hasNext();) {
        Entry<Integer, String> temp=iterEntry.next();
        System.out.println(temp);
    }
    System.out.println("#######################");
    //第二种遍历Map的方式
    Set<Integer> setKey=map.keySet();
    for (Iterator<Integer> iterKey=setKey.iterator();iterKey.hasNext();) {
        Integer temp=iterKey.next();
        System.out.println(temp+"---"+map.get(temp));
    }
}

Collections工具类

java.util.Collections类提供了对List、Set、Map进行排序、填充、查找元素的辅助方法：

• void sort(List)：对List容器类的元素按照升序排序。
• void shuffle(List)：对List容器内的元素进行随机排序。
• void reverse(List)：对List容器内的元素进行逆序排序。
• void fill(List,Object)：用一个特定的对象重写整个List容器(将List全部中的对象全部替换成这个Object对象)。
• int binarySearch(List,Object)：对于顺序的List容器，采用折半查找法来查找特定的对象(可以先用sort()方法排序该List容器)

结语

对于容器的理解，限于本人水平有限仅至于此，以上的内容基本完全满足了日常开发工作所需。如果想更深入了解容器的用法可以参阅官方的JDK文档；想更深入了解容器的底层实现原理，可以观摩容器的源码。本篇内容至此结束，感谢各位阅读。