Java集合深入解析（一）——集合的基本概念

从本章开始，我们将深入学习Java中的集合内容。据统计，在实际业务开发中，Java集合的使用频率要远超其他类库中大部分类，可以说，集合类库是Java中最为重要的类库。本章将从集合的基础知识、集合的分类、集合框架及底层原理来深入理解集合。学习本章的集合知识需要建立以下学习目标：

	了解集合的基本概念；
	理解常见集合的特点、基本操作及实际应用；
	了解集合框架及框架体系；
	深入理解集合的底层原理。

下图描述了Java集合的知识体系：

1.集合的由来
在Java的初始版本中，由于缺少对集合的支持，选择性能优越的数组作为存储数据的“容器”。但是数组的缺点在于具有固定的尺寸，然而在绝大部分情况下，我们无法预知程序需要多少个对象，因此尺寸固定的数组的应用场景就具有很大的局限性了。由此，Java集合应运而生。

2.集合的基本概念
2.1.什么是集合？
集合是一个用来存放对象的容器，Java集合类存放于java.util包中。集合通常具有以下几个特点：

	集合存放的是多个对象的引用，对象本身还是放在堆内存中；
	集合只能存放对象的引用。例如，现在存储一个int基本数据类型的数据到集合中，
但编译器会将其自动转换成Integer类型，Java中每一种基本数据类型都有对应的包装类型。
	由于的泛型存在，因此集合可以支持不同类型，不限数量的数据类型。

2.2.集合的基本操作
集合的基本操作一般有添加、查询、遍历和删除。下面以最基本的集合ArrayList、HashSet和HashMap为例，通过实际案例来描述集合的基本操作。
2.2.1.添加元素
ArrayList或HashSet可以通过add()方法来添加一个元素，还可以通过addAll来接收一个集合，即批量添加另一个集合的所有元素：

public class CollectionDemo {

  public static void main(String[] args) {
    add();
  }

  private static void add() {
    // 1.ArrayList添加元素，允许元素按照插入顺序排列且重复
    List list = getList();
    System.out.println("list : " + list);
    List list2 = new ArrayList<>(10);
    // 批量添加集合的所有元素
    list2.addAll(list);
    System.out.println("list2 : " + list2);

    // 2.HashSet添加元素,确保元素的唯一性
    Set set = getSet();
    System.out.println("set : " + set);
    Set set2 = new HashSet<>(16);
    // 批量添加集合的所有元素
    set2.addAll(set);
    System.out.println("set2 : " + set2);

    
    Map map = getMap();
    System.out.println("map : " + map);
    Map map2 = new HashMap<>(16);
    // 批量添加集合的所有元素
    map2.putAll(map);
    System.out.println("map2 : " + map2);
  }

  private static Map getMap() {
    Map map = new HashMap<>(16);
    map.put("a",1);
    map.put("b",2);
    map.put("c",3);
    return map;
  }

  private static Set getSet() {
    Set set = new HashSet<>(16);
    set.add("a");
    set.add("a");
    set.add("b");
    return set;
  }

  private static List getList() {
    List list = new ArrayList<>(10);
    list.add("a");
    list.add("b");
    list.add("c");
    return list;
  }
}
// ~output:
list : [a, b, c]
list2 : [a, b, c]
set : [a, b]
set2 : [a, b]
map : {a=1, b=2, c=3}
map2 : {a=1, b=2, c=3}

除了以上两个用于添加集合元素的常规方法外，Java设计者还提供了Collections.addAll(Collection c, T… elements)方法，通过可变参数批量添加一组元素：

public class CollectionDemo {

  public static void main(String[] args) {
    add();
  }

  private static void add() {
    // 1.ArrayList添加元素，允许元素按照插入顺序排列且重复
    List list = getList();
    List list2 = new ArrayList<>(10);
    // 批量添加集合的所有元素
    list2.addAll(list);
    System.out.println("list2 : " + list2);

    // 2.HashSet添加元素,确保元素的唯一性
    Set set = getSet();
    Set set2 = new HashSet<>(16);
    // 批量添加集合的所有元素
    set2.addAll(set);
    System.out.println("set2 : " + set2);
    List list3 = new ArrayList<>(10);
    list3.add("d");
    list3.add("e");
    Collections.addAll(list3, list2.toArray(new String[list2.size()]));
    System.out.println("list3 : " + list3);

    Set set3 = new HashSet<>(10);
    set3.add("d2");
    set3.add("e2");
    Collections.addAll(set3, set2.toArray(new String[set2.size()]));
    System.out.println("set3 : " + set3);
  }

  private static Set getSet() {
    Set set = new HashSet<>(16);
    set.add("a");
    set.add("a");
    set.add("b");
    return set;
  }

  private static List getList() {
    List list = new ArrayList<>(10);
    list.add("a");
    list.add("b");
    list.add("c");
    return list;
  }
}
//~output:
list2 : [a, b, c]
set2 : [a, b]
list3 : [d, e, a, b, c]
set3 : [a, b, e2, d2]

2.2.2.查询元素
2.2.2.1.随机访问与顺序访问

随机访问：随意访问该数据结构中的任意一个节点。例如，数组在内存中是按顺序存储
的，可以通过下标直接定位到某一个元素存放的位置。
顺序访问：从第一个元素开始逐个地读取该数据结构的元素。例如，链表只 能顺序访问：
要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。

2.2.2.2.RandomAccess接口
RandomAccess接口属于标记接口，因此内部不存在任何方法:

在Java集合中，通过实现RandomAccess标记接口来标记该集合自身支持随机访问，以便在一些框或算法中，就可以根据是否实现了RandomAccess接口做出更好的决策方式（方法实现）。例如，在ArrayList中，集合的for循环访问数据比使用iterator访问来的高效快速，我们可以通过代码验证这个结论：

public class CollectionDemo {

  public static void main(String[] args) {
    testLoop();
  }

  private static void testLoop(){
    List list = new ArrayList<>(10);
    for(int i = 0;i<10000000;i++){
      list.add(i);
    }
    long startTime = System.currentTimeMillis();
    for(int i = 0;i<10000000;i++){
      Integer integer = list.get(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("随机访问遍历耗时：" + (endTime - startTime));

    startTime = System.currentTimeMillis();
    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
      Integer next = iterator.next();
    }
    endTime = System.currentTimeMillis();
    System.out.println("迭代器遍历耗时：" + (endTime - startTime));
  }
}
//~output:
随机访问遍历耗时：55
迭代器遍历耗时：66

在此基础上，Java设计者就让ArrayList实现了RandomAccess标记接口，以便在Collections等类中通过判断集合是否实现了RandomAccess接口，尽可能定制最优算法处理策略：

	若集合实现了RandomAccess标记接口，则直接通过随机访问（即
get(index)）的方式遍历集合；
	若集合未实现RandomAccess标记接口，例如LinkedList，则通过迭代
器的方式遍历集合。

随机访问：

迭代器访问：


注意：随机访问是集合自身所具有的特点和行为，并不能错误地认为集合实现了RandomAccess接口才具备了随机访问的能力，而应该理解为若某个集合本身具备随机访问的能力，那么该集合应当去实现RandomAccess接口，以便在Collections等算法类中尽可能定制最优算法处理策略（若集合实现了RandomAccess接口，都会调用性能最优的随机访问方法）。换句话说，RandomAccess接口作用在于用来标记该集合具备随机访问的能力（特指实现了某个随机访问的方法），而不是提供了随机访问的能力。例如，在Java集合中，ArrayList的底层由数组实现，因此它支持随机访问，所以该集合才实现了RandomAccess接口：

而LinkedList的底层由链表实现，因此它不支持随机访问，只支持顺序访问，所以该集合没有实现RandomAccess接口：

HashSet与ArrayList是两种完全不同的集合，前者基于散列表实现，它可以确保保存的元素不重复，但无法保证元素的顺序，因而没有维护元素的下标，因为这样做几乎是没有意义的；而ArrayList是基于数组实现，它允许元素按照插入顺序排列且重复，由于ArrayList是基于数组实现的，因此它可以通过下标获取元素，即支持随机访问。由于HashSet没有维护元素的下标，因此它不支持随机访问，但可以通过ArrayList的构造器转换为List，这样就支持随机访问了：

Set set3 = new HashSet<>(10);
set3.add("d2");
set3.add("e2");
List list4 = new ArrayList<>(set3);

假如你只想获取Set集合的第一个元素或者说Set集合中只有一个元素时，那么可以这样做：

Set set3 = new HashSet<>(10);
String next = set3.iterator().next();
System.out.println("next :" + next);

但是在通过iterator().next()方法获取Set集合的第一个元素时，要确保Set集合中至少存在一个元素，否则会抛出一个java.util.NoSuchElementException异常，同样地，List在获取元素时也要保证这一点，防止发生java.lang.IndexOutOfBoundsException异常。
HashMap是一种散列表，它的元素是一个键值对，键和值构成映射关系，因此散列表的作用在于将某个对象与另一个对象关联起来。我们可以通过键来查找值：

Map map = getMap();
Integer value = map.get("a");

另外，需要特别注意一点：若HashMap的值为集合类型，通过put维护键值对时，应该避免使用containsKey()方法。我们通过一个简单的例子来看看这样做有什么弊端：

Map> map2 = new HashMap<>();
List valueList;
if(map2.containsKey("a")) {
  valueList = map2.get("a");
} else {
  valueList = new ArrayList<>(10);
}
valueList.add(1);

在上面的案例中，程序首先通过containsKey()方法判断map2中是否存在键对象”a”，若存在则再通过get(“a”)获取值对象。实际上，大可不必这样，原因在于HashMap的get()方法和containsKey()方法本质上都是调用getNode()方法实现的：

因此这就重复执行了两次getNode()方法。优化后的代码如下所示：

Map> map2 = new HashMap<>();
List valueList = map2.get("a");
if(valueList == null) {
  valueList = new ArrayList<>(10);
}
valueList.add(1);

我们看到，优化后的代码性能得到了提升，并且也清爽、简洁了许多。

2.2.3.集合的遍历
ArrayList支持三种最基本的遍历方式，我们通过一个案例来了解这几种遍历方式：

List list = getList();
// 1.通过标准for循环语句遍历
for (int i = 0; i < list.size(); i++) {
  String element = list.get(i);
  System.out.println(element);
}
// 2.通过Foreach语句遍历
for (String element : list) {
  System.out.println(element);
}
// 3.通过迭代器进行遍历
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
  String element = iterator.next();
  System.out.println(element);
}

需要注意地是，Foreach语句经编译器优化处理后，会得到一个迭代器遍历，因此理论上它的性能甚至不如迭代器遍历：

所以，以上三种遍历方式的性能从好到坏的顺序为：标准for > 迭代器遍历 > Foreach，不过Foreach的价值在于简单、方便，并且从实际测试效果来看，它们之间的性能差异其实非常微妙，可以忽略不计，基于这个原因，Foreach语句反而成了最受欢迎的集合遍历方式。
Set集合除了不支持标准的for语句外，迭代器和Foreach都是遍历Set集合常用方式，并且用法与ArrayList相同。
Map包含多种遍历方式，实践证明，下面的方式是遍历Map的最佳方式：

Map map = getMap();
for(Map.Entry entry : map.entrySet()) {
  String key = entry.getKey();
  Integer value = entry.getValue();
}

在上面的代码中，entrySet()方法返回的类型是一个以键值对为元素的Set集合，即在HashMap中实现的EntrySet集合类型：

可见，EntrySet与HashSet是同级别的Set类型集合。因此，for(Map.Entry entry : map.entrySet())语句实际上是专门用来遍历Map的Foreach语句。

2.2.4.删除元素
对于List而言，删除单个元素的方法为remove(Object o)和remove(int index);List还提供了删除一组元素的方法—removeAll(Collection c))，如果想删除整个list的元素，那么可以调用clear()方法。例如：

List list2 = new ArrayList<>(10);
list2.add("a");
list2.add("b");
list2.add("c");
list2.add("d");
list2.add("e");
list2.add("e");
List list3 = new ArrayList<>(10);
list3.add("b");
list3.add("c1");
list3.add("d2");
list3.add("e");
list2.removeAll(list3);
System.out.println(list2);
list2.clear();
System.out.println(list2);
List list4 = new ArrayList<>(10);
list4.add("a");
list4.add("b");
list4.add("b");
list4.remove("b");
System.out.println(list4);
//~output:
[a, c, d]
[]
[a, b]

需要注意地是，remove(Object o)无法删除重复元素，只能删除重复元素中的第一个，我们可从源码中得出这一结论：

而removeAll()则可以删除当前集合中所有重复的元素：

List list4 = new ArrayList<>(10);
list4.add("a");
list4.add("b");
list4.add("b");
List list5 = new ArrayList<>(10);
list5.add("b");
list4.removeAll(list5);
System.out.println(list4);
//~output:a

Set集合除了不支持删除方法remove(int index)外，其他删除操作基本与List类似。
对于Map而言，可以根据键来完成对键值对元素的删除：remove(Object key)。
不过，要考虑一种特殊的情况：在for循环语句或forEach语句中删除元素时，List和Set要避免使用remove()方法，在for循环语句中可能会抛出IndexOutOfBoundsException异常，并且可能无法删除目标元素，例如：

List list6 = new ArrayList<>(10);
list6.add("a");
list6.add("b");
list6.add("c");
list6.add("d");
list6.add("e");
for(int i = 0;i
  list6.remove(i);
}
System.out.println("list6 : " + list6);
//~output：
list6 : [b, d]

原因在于List在删除元素时，成员变量size也会随之减小，而当for循环的变量i大于等于size时，将抛出一个IndexOutOfBoundsException异常，即便没有发生该异常，随着size的减小，变量i却在增加，因此必然会导致元素删除错误：

而在forEach语句中删除集合的元素则可能会抛出一个

java.util.ConcurrentModificationException异常：
List list6 = new ArrayList<>(10);
list6.add("a");
list6.add("b");
list6.add("c");
list6.add("d");
list6.add("e");
for(String str : list6) {
  list6.remove(str);
}
//~output:
Exception in thread "main" java.util.ConcurrentModificationException

原因在于forEach语句的底层是基于迭代器实现，而在迭代器中不允许执行新增、删除等操作迭代器通过维护一个expectedModCount成员变量来约束这一行为：

而在迭代器外部的add()、remove()方法中，程序每调用一次add()、remove()方法都会修改modCount（即Modification Count，修改次数）成员变量值：

因此在迭代器遍历集合时，若调用迭代器外部的add()、remove()方法都会导致List的modCount成员变量值与内部迭代器的expectedModCount成员变量值不一致，因此当迭代器通过next()方法获取元素时，首先会检查成员变量modCount与成员变量expectedModCount的值是否相等：若不相等，则抛出java.util.ConcurrentModificationException异常，通过该异常来约束迭代器在遍历过程中的行为—即只允许调用迭代器自身的remove()方法，不允许调用迭代器外部的方法来修改list：


注意到，在迭代器接口中，包含了如下几个方法：

	boolean hasNext()：判断集合中是否还存在下一个元素；
	E next()：获得集合中的下一个元素；
	void remove()：删除集合中的元素。

可见，迭代器的作用主要有两个：遍历元素和删除元素。因此，我们可借助迭代器来实现循环中的元素删除：

List list = new ArrayList<>(10);
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
  iterator.next();
  iterator.remove();
}
System.out.println("list : " + list);
//~output:list:[]

在遍历Map的过程中，若尝试删除键值对元素，也会遇到同样的问题：

Map map3 = new HashMap<>(16);
map3.put("a", 1);
map3.put("b", 2);
map3.put("c", 3);
for(Map.Entry entry : map3.entrySet()) {
  String key = entry.getKey();
  map3.remove(key);
}
或
for(Map.Entry entry : map3.entrySet()) {
  String key = entry.getKey();
  map3.put("d", 4);
}
//~output: Exception in thread "main" java.util.ConcurrentModificationException

在使用上述方式遍历Map时，虚拟机会将其转换为一个迭代器来执行，如下图所示：

为什么会转换为一个迭代器呢？在上面我们已经证明for(Map.Entry entry : map.entrySet()){}这种语句实际上是专门用来遍历Map的Foreach语句，该语句会被虚拟机自动转换为一个EntryIterator迭代器（注：一种实现在HashMap内部的迭代器）来执行：

final Node removeNode(int hash, Object key, Object value,
						   boolean matchValue, boolean movable) {
	Node[] tab; Node p; int n, index;
	//...
	if (node != null && (!matchValue || (v = node.value) == value ||
						 (value != null && value.equals(v)))) {
		if (node instanceof TreeNode)
			((TreeNode)node).removeTreeNode(this, tab, movable);
		else if (node == p)
			tab[index] = node.next;
		else
			p.next = node.next;
		++modCount;
		--size;
		afterNodeRemoval(node);
		return node;
	}
	// ...
}

可以看到，在遍历Map时，若在循环内部调用了迭代器外部的put()、remove()等方法，那么将会抛出一个ConcurrentModificationException异常，抛出异常的原理与List类似，这里不再赘述。
如何解决Map在遍历时不能删除键值对元素的问题呢？实际上，处理办法与List类似，将Map的Foreach语句转换为一个迭代器来处理即可：

Iterator> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
  Map.Entry entry = iterator.next(); // 1
  iterator.remove(); // 2
}
System.out.println(map);
//~output:{}

注意：代码1和代码2的顺序1不能交换，否则会抛出特定的异常，也就是说，迭代器的remove()方法依赖于next()方法，所以必须让next()方法优先执行。

2.2.5.其他实用操作
2.2.5.1.listIterator()
在List集合中，可以通过listIterator()获得一个ListIterator迭代器，它是一个比Iterator更加强大的迭代器，属于Iterator的子类：

ListIterator与Iterator区别在于：ListIterator不仅继承了Iterator的全部方法，还实现了自己的方法。例如，Iterator只能通过next()方法单向移动获取元素，而ListIterator可以分别通过previous()和next()方法完成双向移动和元素的获取；此外，ListIterator还解决了Iterator不能添加元素的问题。例如：

public class CollectionDemo2 {

  public static void main(String[] args) {
    List list = getList();
    ListIterator listIterator = list.listIterator();
    int count = 0;
    // 向后移动游标
    while (listIterator.hasNext()) {
      int i = listIterator.previousIndex();
      System.out.println("previous:" + (i >= 0 ? list.get(i) : null));
      String curr = listIterator.next();
      System.out.println("curr:" + curr);
    }
// 一个迭代器对象只能循环一次，重新创建一个迭代器,并通过迭代器向list中添加新的元素    
listIterator = list.listIterator();
    while (listIterator.hasNext()) {
      listIterator.next();
      listIterator.add("e" + (++count));
    }
    // 此时游标位于迭代器的末尾，可以向前移动游标
    while (listIterator.hasPrevious()) {
      String previous = listIterator.previous();
      System.out.println(previous);
    }
    // 将集合list的元素反向插入到新的List集合中
    List newList = new ArrayList<>(10);
    int size = list.size();
    while (listIterator.hasNext()) {
      int i = listIterator.nextIndex();
      int newIndex = size - 1 - i;
      String newE = list.get(newIndex);
      newList.add(newE);
      listIterator.next();
    }
    System.out.println("list : " + list);
    System.out.println("newList : " + newList);
  }

  private static List getList() {
    List list = new ArrayList<>(10);
    list.add("a");
    list.add("b");
    list.add("c");
    return list;
  }
}
//~output:
previous:null
curr:a
previous:a
curr:b
previous:b
curr:c
e3
c
e2
b
e1
a
list : [a, e1, b, e2, c, e3]
newList : [e3, c, e2, b, e1, a]

注意：previous()和next()方法不能同时应用到一个遍历程序中，否则会引发死循环。

2.2.5.2.subList(int fromIndex, int toIndex)
该方法返回原始列表List连续元素的子列表，并且子列表的修改（删除、添加）结果都会反映到父列表中，原因在于subList()方法对应的子列表的add()、remove()等方法实现直接调用了父列表的add()、remove()方法：



例如：

public class CollectionDemo2 {

  public static void main(String[] args) {
    List list = getList();
    List subList = list.subList(1, 3);
    System.out.println("subList : " + subList);
    System.out.println("list : " + list);
    // 在子列表中添加元素后，增加的元素也会反映到父列表list中的特定位置
    subList.add("f");
    System.out.println("subList : " + subList);
    System.out.println("list : " + list);
    subList.remove(0);
    System.out.println("subList : " + subList);
    System.out.println("list : " + list);
  }

  private static List getList() {
    List list = new ArrayList<>(10);
    list.add("a");
    list.add("b");
    list.add("c");
    return list;
  }

}
//~output:
subList : [b, c]
list : [a, b, c]
subList : [b, c, f]
list : [a, b, c, f]
subList : [c, f]
list : [a, c, f]

2.2.5.3.retainAll(Collection c)
该方法用来保留当前集合与另一个集合中相同的元素，是一种获取两个集合间交集的解决办法，并且以当前集合作为交集元素的容器。因此，要注意调用该方法可能会替换当前集合中的元素。例如：

public class CollectionDemo3 {

  public static void main(String[] args) {
    List list = getList();
    List list2 = new ArrayList<>(10);
    list2.add("1");
    list2.add("a");
    list2.add("c");
    list2.add("2");
    // 保留相同元素—交集
    System.out.println("list : " + list);
    list.retainAll(list2);
    System.out.println("通过list求（list和list2）的交集 : " + list);
    System.out.println("list2 : " + list2);
    list2.retainAll(getList());
    System.out.println("通过list2求（list和list2）的交集 : " + list2);  }

  private static List getList() {
    List list = new ArrayList<>(10);
    list.add("a");
    list.add("b");
    list.add("c");
    return list;
  }

}
//~output:
list : [a, b, c]
通过list求（list和list2）的交集 : [a, c]
list2 : [1, a, c, 2]
通过list2求（list和list2）的交集 : [a, c]

3.为什么选择集合而不是数组？
（1）集合都拥有自己的扩容机制，可以自动调整自身大小，而数组在初始化后其大小是固定不变的；
（2）集合具有丰富的特性，不同的集合应用也不同，而数组的特性单一；
例如，Set的元素是唯一的，List允许元素按照插入顺序排列且重复，Map允许你将某些对象和其他对象关联起来组成一个关联映射表。
（3）集合更好地体现了面向对象的思想。
数组与集合一样，都能充当对象的容器，但数组支持基本数据类型，而集合支持包装类型，因此集合更好地体现了面向对象的思想。Java本身是一门面向对象的语言，虽然数组存在的价值在于具有优越的性能，并且它天然支持基本数据类型，但正是因为基本数据类型才使得Java语言不再是“纯粹”的面向对象语言，所以在Java后期的版本中支持了自动包装类和泛型后，使得集合也能轻而易举地添加基本数据类型数据对应的包装类型引用。显然，与集合相比，数组除了优越的性能外，其他方面都黯然失色，几乎很少有应用的价值。
以上这些因素使得集合完全取代了数组。