全国协议5人面授小班,企业级独立开发考核,转业者的IT软件工程师基地 登录/注册 | 如何报名
当前位置: Java   >  Java 中基于数组和链表的常用类
admin · 更新于 2021-08-06

1. 前言

通过前面的学习,我们其实对 ArrayList 和 LinkedList 已经很熟悉了,他们虽然都是继承自 List,但是前者是基于数组实现的,后者是基于链表实现的,结合各自的特点我们会在前半节对比总结他们的特点和用法。
HashMap 和 HashSet 分别实现了 Map 接口和 Set 接口,HashSet 是一个值不重复的集合,HashMap 对键值对进行映射,是一个键不重复的集合。我们会在后半部分对比介绍各自的特点和用法。

2. Vector和ArrayList

结合 JAVA 源码,我们可以看到 Vector 和 ArrayList 都是基于数组实现的,都继承自 List 接口。因此他们随机查询的效率是非常高的,但是他们在数据插入或删除,以及需要扩容的时候效率都比较低下,需要在原有数组之外进行复制、移动。还有一点细节的区别在于扩容的默认值,ArrayList 在内存不足时默认扩容至 1.5 倍再加 1 个,Vector 默认扩容为原来的 2 倍。
他们最重要的区别在于 Vector 中大量使用了 synchronized 来修饰方法,所以它是线程安全的,相应的,效率也是比 ArrayList 更低的。所以我们生成今天的第一条结论:

  • 需要线程安全的场景使用Vector

3. ArrayList和LinkeList

经过前面的学习我们已经知道了 ArrayList 是基于数组的,查询快插入慢,LinkedList 是基于链表的,插入快遍历慢。我们来做个实验看一下是不是真的如此:

Integer index = 10000000;List<Integer> arrayList = new ArrayList<Integer>();List<Integer> linkedList = new LinkedList<Integer>();Long arrayStart = new Date().getTime();for (int i = 0; i < index; i++){
    arrayList.add(i);}Long arrayEnd = new Date().getTime();Long linkedStart = new Date().getTime();for (int j = 0; j < index; j++) {
    linkedList.add(j);}Long linkedEnd = new Date().getTime();System.out.println("插入"+index+"条记录:");System.out.println("ArrayList耗时:"+(arrayEnd-arrayStart)+"毫秒");System.out.println("LinkedList耗时:"+(linkedEnd-linkedStart)+"毫秒");
代码块
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

结果:
插入 10000000 条记录:
ArrayList 耗时:359 毫秒
LinkedList 耗时:2891 毫秒

我们会发现两者相差并不大,而且当我们把数据量上升到 10000000 的时候还会发现 ArrayList 的效率反而更快,这是什么原因呢。
原来我们使用的 add (E e) 方法有这样的注释:

Appends the specified element to the end of this list (optional operation).

所以当把元素追加在最后的时候,数组中的其他元素不需要移动,此时 ArrayList 的处理效率也很不错。那么我们换个思路再试:

//元素个数减少到10万即可看出效果Integer index = 100000;List<Integer> arrayList = new ArrayList<Integer>();List<Integer> linkedList = new LinkedList<Integer>();Long arrayStart = new Date().getTime();for (int i = 0; i < index; i++){
	//其他代码不变,我们将每次遍历时添加新元素的位置固定为第一个
    arrayList.add(0,i);}Long arrayEnd = new Date().getTime();Long linkedStart = new Date().getTime();for (int j = 0; j < index; j++) {
	//其他代码不变,我们将每次遍历时添加新元素的位置固定为第一个
    linkedList.add(0,j);}Long linkedEnd = new Date().getTime();System.out.println("插入"+index+"条记录:");System.out.println("ArrayList耗时:"+(arrayEnd-arrayStart)+"毫秒");System.out.println("LinkedList耗时:"+(linkedEnd-linkedStart)+"毫秒");
代码块
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

结果:
插入 100000 条记录
ArrayList 耗时:828 毫秒
LinkedList 耗时:16 毫秒

这个测试结果跟理论就匹配上了,ArrayList 把大量的时间都用在了移动元素上,而 LinkedList 不需要做这样的操作,所以此时它的效率优势体现的非常明显。所以我们在日常使用中一定要区分,在使用 add 方法的时候是否需要指定新添加元素的位置,另外,由于 ArrayList 是基于无序数组的,因此遍历的时候可能输出顺序和插入顺序是不一致的,而 LinkedList 由于有严格的指针相连,顺序一定是固定的。
所以我们生成第二组结论:

  • 需要频繁在指定位置添加、删除元素,而查询指定位置数据较少的场景优先使用 LinkedList
  • 随机查询较多、在指定位置添加、删除元素较少,或者干脆不关心插入或删除元素的位置及遍历顺序时,优先使用 ArrayList
  • 需要元素按顺序排列时,使用 LinkedList

4. Map家族

Java.util.Map 接口常用的实现类有 HashMap、HashTable、ConcurrentHashMap、LinkedHashMap 和 TreeMap。他们都是用来储存 key-value 键值对的,可以通过键快速的读取值,也因此,他们的键都是不可以重复的。那么他们各自又有什么特点,彼此又有什么区别呢?

4.1 HashMap

HashMap 是我们最常用的 Map 类,它的底层是由数组和链表来实现的,允许键或值为 null,并且顺序是不固定的,默认容量是 16,当元素超过 Entry 数组的加载因子(默认值是 75%)时触发扩容,扩容时原来数组中的元素要依次重新插入到新的数组中。它是非线程安全的。

4.2 HashTable

HashTable 初始容量为 11,并且键和值都不允许为 null,其他特性与 HashMap 没有太大区别。虽然它是线程安全的,但是我个人更推荐大家使用 ConcurrentHashMap。

4.3 ConcurrentHashMap

我们可以在 Java.util.concurrent.ConcurrentHashMap 下通过注释了解到,这个类在 HashMap 和 HashTable 的基础上做了优化。它实现了线程安全,通过把 Map 分段成若干个段,在需要锁定的时候只锁定其中的一段,而在读取的时候不做任何锁定操作,另外用 volatile 修饰 HashEntry 的 value 来实现数据的实时更新,在 HashTable 的基础上大大提升了效率。

4.4 LinkedHashMap

LinkedHashMap 记录了元素保存的顺序,因此在遍历的时候可以按照当时的顺序读取,一般用于我们需要保留元素顺序的场景。

Map<String, String> hashMap = new HashMap<String, String>();hashMap.put("水果", "苹果");hashMap.put("蔬菜", "白菜");hashMap.put("坚果", "核桃");Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();while(iterator.hasNext()) {
    Map.Entry entry = iterator.next();
    String key = (String) entry.getKey();
    String value = (String) entry.getValue();
    System.out.println("key:" + key + ",value:" + value);}
代码块
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

对于无序的 HashMap,依次输出
key: 蔬菜,value: 白菜
key: 水果,value: 苹果
key: 坚果,value: 核桃

Map<String, String> linkedHashMap = new LinkedHashMap<String,String>();linkedHashMap.put("水果", "苹果");linkedHashMap.put("蔬菜", "白菜");linkedHashMap.put("坚果", "核桃");Iterator<Map.Entry<String, String>> iterator = linkedHashMap.entrySet().iterator();while(iterator.hasNext()) {
    Map.Entry entry = iterator.next();
    String key = (String) entry.getKey();
    String value = (String) entry.getValue();
    System.out.println("key:" + key + ",value:" + value);}
代码块
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

对于有序的 LinkedHashMap,依次输出
key: 水果,value: 苹果
key: 蔬菜,value: 白菜
key: 坚果,value: 核桃

4.5 TreeMap

TreeMap 的底层实现了红黑树的结构,是一个可以比较元素大小的 Map 集合,默认会根据元素的 key 值进行自然排序(前提是 key 值实现了 Comparable 接口),我们也可以自己定义比较器来进行排序。
总结一下:

  • 日常使用 HashMap;
  • 需要线程安全时用 ConcurrentHashMap;
  • 需要记录元素保存顺序时使用 LinkedHashMap;
  • 需要排序时使用 TreeMap。

5. 小结

本节我们学习了数据结构在 Java 中的应用,对于不同数据结构的封装类的使用场景做了一些总结:List 接口下需要线程安全的场景使用 Vector,增、删较多或需要元素有序时使用 LinkedList,查询较多时使用 ArrayList;Map 接口下需要线程安全的场景使用 ConcurrentHashMap,需要记录元素顺序时使用 LinkedHashMap,需要排序时使用 TreeMap,日常使用 HashMap


为什么选择汉码未来