Java基础之刨根问底第6集——集合与List

• 本系列不适合初学者，读者应具备一定的Java基础。

• 本系列依据Java11编写

内容简介：

从本集开始，会进入Java Collections Framework的介绍，这部分所涉及的容器对象是和我们日常编码最相关的。本集作为开篇，刨根问底的内容并没有太多。内容主要包括：

• 1.Java中的集合介绍

  • 1.1.集合与数组

  • 1.2.已过时的接口

  • 1.3.Collection接口的继承结构

• 2.Java中的List浅谈

  • 2.1.ArrayList与LinkedList性能对比

  • 2.2.小结

• 3.下集预告

1.Java中的集合介绍

集合是用于在内存中存储数据的数据结构。

1998年，java在1.2版本中加入了Collections Framework，是jdk中使用最广泛的API。至今经历了两次重大的重写，分别是在java5中添加泛型的时候和在java8中引入lambda表达式的时候。

Java中的Collections Framework由接口和实现两部分组成，每种接口都对应了一种存储特定数据类型的方式。接口可分为两类：collections和maps，前者既可以存储对象又可以遍历这些对象，而后者存储的是一组key/value对。

1.1.集合与数组

相比数组，集合有以下优势：

• 集合持续关注内部元素的数量，无需预先定义容量；

• 集合的容量可以看作是无限的；

• 集合可以过滤存入的元素，例如可以避免存入null；

• 集合提供接口可以判断一个元素是否存在；

• 集合中提供与另一个集合之间的插入、合并等 *** 作。

总的来说，相比数组，集合是一个可扩展的对象，除了JDK自带的能力外，还可以自己扩展新的能力。

1.2.已过时的接口

以下存在于Collections Framework中的接口是已经过时的，应避免使用这些接口：

• Vector和Stack：在非并发环境下，用ArrayList替换Vector，用ArrayDeque替换Stack。

• Enumeration：Vector使用Enumeration来处理对象的迭代，这个接口目前也不应该再使用了，与迭代有关的应使用Iterator接口。

• HashTable：非并发环境下使用HashMap替换，并发环境下使用ConcurrentHashMap替换。

1.3.Collection接口继承结构

如下图所示：

1.3.1.Iterable接口

这个接口本质上不属于Collections Framework，这个接口是2004年加入到Java5版本中的。实现这个接口就说明该对象可以被迭代（遍历）。Java5中的for each就是通过Iterable接口实现的，如下所示：

1.3.2.Collection接口

这个接口封装了List和Set的一些通用能力：

• 涉及元素的能力有：

  • 添加删除元素；

  • 检查元素是否存在；

  • 查看元素个数，查看集合是否为空；

  • 清空元素。

• 涉及集合的能力有：

  • 测试一个集合是否包含在另一个集合内；

  • 取两个集合的并集；

  • 取两个集合的交集；

  • 取两个集合的补集；

• 涉及遍历元素的能力有：

  • 通过迭代器对集合中的元素进行遍历；

  • 通过Stream的方式进行遍历，这种方式可以并行执行。

1.3.3.List接口

List接口在Collection接口的基础上，增加了按照元素的添加顺序排序的能力。有了这个能力后，每次对一个List中的元素进行遍历，结果都是一样的——先输出第一个元素，然后是第二个，以此类推。

排序后出现的另一个能力，是可以根据index编号来访问对应位置的元素。

于是，List在Collection接口的基础上又添加了以下一些能力：

• 根据index编号获取元素或者删除元素；

• 在集合中的特定位置插入或者替换元素；

• 根据两个index编号获取一个范围内的子集。

1.3.4.Set接口

与List接口不同，Set中元素的访问顺序是无法得到保证的。

Set接口在Collection接口的技术上，增加了元素不能有重复的这一限制条件。

在JDK的Set实现中，并没有一个实现是既可以去重又可以按照index编号访问元素的。

在接口方法上，Set仅仅是在方法的具体实现上有要求，但在能力上并没有扩展Collectioin接口。

1.3.5.SortedSet和NavigableSet

Set接口有两个扩展，分别是：SortedSet和NavigableSet。

SortedSet的能力是可以根据升序对元素进行排序，这个能力需要元素实现Comparable接口的的compareTo()方法，另一个方法是为SortedSet指定一个Comparator（比较器），用来执行比较。当然，可以同时使用这两个方法。

与List接口相比，SortedSet的能力是为元素排序，而List仅仅是保证元素的有序。

SortedSet接口扩展了一些能力，包括：

• 可以获得集合中最低或最大的元素；

• 可以根据一个元素，获得比该元素小或者大的一个子集。

遍历时，SortedSet从最低到最高遍历元素。

NavigableSet和SortedSet的行为是一致的，只是增加了一些有用的方法，可以降序的遍历元素。

2.Java中的List浅谈

JDK中的List接口有两个实现：ArrayList和LinkedList，前者建立在一个内置的数组的基础上，后者则基于一个双向链表。

绝大多数情况下，ArrayList都是最好的选择。ArrayList遍历元素和随机获取元素的速度要远远快于LinkedList。不过，因为双向链表的原因，LinkedList在获取第一个元素和最后一个元素的速度要快于ArrayList，当需要LIFO（后进先出）的栈或者FIFO（先进先出）的队列时，可以考虑使用LinkedList。

2.1.ArrayList与LinkedList性能对比 2.1.1.Add方法对比

测试代码如下：

public static void main(String[] args) {
  int count = 50000000;
  List list = initList(count, ArrayList.class);
  // List list = initList(count, LinkedList.class);
}
​
​
private static List initList(int count, Class listClass) {
  long begin = System.currentTimeMillis();
​
  List list;
  if (listClass == ArrayList.class) {
    list = new ArrayList<>();
  } else if (listClass == LinkedList.class) {
    list = new LinkedList<>();
  } else {
    throw new IllegalArgumentException();
  }
​
  for (int i = 0; i < count; i++) {
    list.add("element" + i);
  }
​
  timer(begin, System.currentTimeMillis());
  return list;
}
​
private static void timer(long begin, long end) {
  System.out.println("cost: " + (end - begin) + "ms");
}

这段代码做的事情很简单，就是用ArrayList或者LinkedList创建一个List集合，然后向其中放入5千万条记录，对比二者花费的时间。

首先是ArrayList：

接着是LinkedList：

可以看到，经过更多次的GC后，LinkedList花费了11274ms，而ArrayList的GC次数不但少很多，而且只用了3508ms。可见，相比ArrayList，LinkedList的增加元素不仅慢，而且更加耗费内存。

ArrayList胜！

2.2.2.遍历对比

在上一个例子初始化后，通过循环的方式遍历每一个元素，比较二者在时间上的花费。

public static void main(String[] args) {
  int count = 50000000;
  List list = initList(count, ArrayList.class);
  //List list = initList(count, LinkedList.class);
​
  iterateList(list);
}
​
private static void iterateList(List list) {
  long begin = System.currentTimeMillis();
  for (String ele : list) {
    ;
  }
  timer(begin, System.currentTimeMillis());
}

ArrayList花费357ms。

LinkedList花费1239ms。

ArrayList再一次胜出！

2.2.3.随机读对比

这次我们每一种List都获取第一个元素、中间的元素和最后一个元素。

public static void main(String[] args) {
  int count = 50000000;
  List list = initList(count, ArrayList.class);
  //List list = initList(count, LinkedList.class);
​
  randomRead(list, 0);
  randomRead(list, count / 2);
  randomRead(list, count);
}
  
private static void randomRead(List list, int position) {
  long begin = System.currentTimeMillis();
  list.get(position);
  timer(begin, System.currentTimeMillis());
}

ArrayList：0ms    0ms    0ms

LinkedList：0ms    704ms   0ms

ArrayList依然是最佳选择！

2.2.4.插入对比

在第一个位置和最后一个位置插入新元素，对比两个List花费的时间。

public static void main(String[] args) {
  int count = 50000000;
  List list = initList(count, ArrayList.class);
  //List list = initList(count, LinkedList.class);
  
  insertAt(list, 0);
  insertAt(list, count);
}
​
private static void insertAt(List list, int position) {
  long begin = System.currentTimeMillis();
  list.add(position, "new");
  timer(begin, System.currentTimeMillis());
}

ArrayList：91ms    0ms

LinkedList：0ms    0ms

啊哦。。。ArrayList战败了！

这是因为向ArrayList中添加元素时，底层的数组需要拷贝，插入的位置越靠前，拷贝的数据量就越大（下一集我们通过源码继续来分析）。而LinkedList只需要维护当前元素与相邻元素的引用关系就可以了。

2.3.小结

如果没有功能上的特殊要求，就用ArrayList行了，当出现性能问题的时候，再考虑下是适合用LinkedList替换。

3.再谈Java中的List

这部分留到下一次再说。下次会从ArrayList和LinkedList的源码分析，再来讨论下二者在使用过程中需要注意的点。敬请期待！

插播个小广告：

本人新书发布！《企业架构与绕不开的微服务》。

• 在理论方面，介绍了企业架构标准、云原生思想和相关技术、微服务的前世今生，以及领域驱动设计等；

• 在实践方面，介绍了用于拆分微服务的“五步法”、包含4个维度的“企业云原生成熟度模型”，以及衡量企业变革成果的“效果收益评估方法”等。

本书可以帮助企业明确痛点、制定原则、规划路径、建设能力和评估成效，最终实现微服务架构在企业中的持续运营和持续演化，从而应对日益增多的业务挑战。

点击这里进入购买页面

 

更多内容请关注我的个人公众号