本文中的测试代码来源于《think in java》第四版
附件中有测试代码
1、各种List的各种操作的耗时
size:每一个list的元素数量,从10到10W
操作:add增加到list末端,get随机访问,set修改某个元素值,insert在list中间插入(代码中只是插入到了第五个元素,放大了随机插入的操作时间),rmMiddle从list中间删除元素(代码中是删除了第五个元素,放大了从list.size()/2的操作时间,rmLast从list末端删除,rmFirst从list首部删除
操作时间:是指每一次操作所用的时间,单位纳秒
环境:64bit JDK7
ArrayList和Vector都是基于数组实现的,区别就是Vector是同步的,以下将统称为“数组list”
2、分析
2.1 add操作,数组和链表旗鼓相当
首先,当list仅有10个元素的add耗时,要大于100/1k/1w/10w元素的add耗时,这里可能是因为“JIT的热点优化”导致。可以通过增加循环次数来验证,在我的机器上:“往一个list增加10个元素”,循环13W次时,每次的操作耗时降到 2位数
其次,比较数组list和链表list,向末端增加时,操作耗时几乎不随着list元素数变化而变化。
数组元素add时的扩容动作最终调用的方法:
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
无疑,native方法System.arraycopy的效率是高的,几乎不随list.size()变化而变化。
因为System.arraycopy的高效,在这里不得不提到一点,链表在add操作时比数组list要复杂的多(LinkedList是双向链表),当list.size()数量超过百万时,链表的add可能就会比数组add要慢,这一点有待验证。
2.2get随机访问,数组完胜
数组list的get耗时,在list.size()增长时,无变化
链表list的get耗时,在list.size()增长时,性能下降。
值得一提的就是jdk5中遍历操作的foreach写法,如下:
for (String x : list) { System.out.println(x); }
此种写法是基于集合的iterator迭代器,只要是实现了Iterable接口的类,均可使用此种写法。数组的迭代器访问,本质还是基于数组的随机访问,和get随机访问比,将无变化。而链表的迭代器访问,与get随机访问相比,性能将有大幅度提升,应该和数组的随机访问差不多,而且不会因为list.size()的增长而导致系能下降
2.3set修改,数组完胜
修改操作,数组list不随size增大而导致效率降低,链表则随着list.size()增大导致效率降低,看链表set源码
public E set(int index, E element) { //查找Entry Entry<E> e = entry(index); E oldVal = e.element; e.element = element; return oldVal; } private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header;//从header开始 //index小于size一半,则向后遍历,否则向前遍历 if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
也就是说,每次set时候,都会从header向前或向后遍历链表。由此可以想到,修改第"list.size/2"个元素,则是代价最大的修改。
2.4 insert插入,链表完胜数组
1)无论链表还是数组,insert操作的效率将会随着list.size()的增大而降低
2)数组需要将insert元素,以后的元素,整体后移动
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
2.5 remove删除,链表小胜
public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; }
数组list每次删除都有System.arraycopy操作,因此效率最低的应该是remove first删除list中的第一个元素。耗时最少的删除是remove last删除最后一个元素。
链表则无论是第一个删除、中间删除、末尾删除,都无需考虑效率问题,而且,删除效率不随list.size()增大而降低
如果是从末尾删除,数组甚至比链表要快。
结论:List中首选Arraylist,基于数组实现list平均性能是最好的,如果有大量的insert或者从首部/中部删除元素的操作,则应该选择LinkedList
其实LinkedList作为队列、堆栈来操作,无疑,应该是首选,效率够高
相关推荐
《Java深度历险》与《深入Java虚拟机》是两本深受Java开发者喜爱的经典书籍,它们涵盖了Java编程语言和Java虚拟机(JVM)的高级主题,旨在帮助读者深入理解Java平台的工作原理。 《Java深度历险》这本书通常会涵盖...
Java集合框架是处理数据结构和算法的关键,包括List、Set、Map等各种接口及其实现类,以及并发容器和Stream API。掌握这些内容,能有效提高代码的可读性和效率。 最后,JVM(Java虚拟机)的内部工作原理也是《Java...
Java容器,也被称为Java集合框架(Java Collection Framework,...Java容器的深度学习需要理解每个接口和类的特点、适用场景以及它们之间的关系。通过熟练掌握Java容器,开发者可以编写出更高效、更易于维护的代码。
《王森 Java深度历险》是一本深受Java开发者喜爱的技术专著,旨在带领读者深入探索Java编程的世界。这本书详尽地讲解了Java的核心概念、高级特性以及实际开发中的最佳实践,帮助读者提升对Java语言的理解和应用能力...
《Java深度历险》是王森撰写的一本深入讲解Java编程技术的书籍,它旨在帮助读者从基础到高级,全面掌握Java的核心概念和技术。这里我们主要探讨Java编程中的关键知识点,包括但不限于类与对象、继承、多态性、异常...
Java深度历险是一本专为Java开发者准备的深入学习书籍,尤其对于想要探索Java语言精髓的程序员来说,这本书无疑是一份宝贵的参考资料。虽然书中的文字是繁体字,但这并不影响我们理解其中所涵盖的丰富Java知识。在这...
《Java深度体验》一书,正如其标题所示,是一本旨在带领读者深入探索Java编程语言的著作。在Java的世界里,深度体验意味着不仅要掌握基本语法,还要理解其背后的原理,以及如何利用这些知识来解决实际问题。这本书...
《Java深度历险》是王森撰写的一本深入探讨Java编程技术的书籍,它涵盖了Java语言的核心特性、高级特性和实战应用。这本书旨在帮助读者从初级程序员晋升为Java开发的高手,通过深入学习和理解,提升编程技能和解决...
- **STL(Standard Template Library)**:提供容器(如vector、list)、迭代器、算法和函数对象,极大地简化了数据结构和算法的实现。 - **模板**:允许创建泛型代码,适用于多种数据类型。 4. **Java特有**: ...
Java程序设计是计算机科学中的重要课程,尤其在清华大学这样的顶级学府中,其教学质量与深度备受业界关注。郑莉老师是这门课程的主讲教师,她以其深厚的学术背景和丰富的教学经验,引领学生们深入理解Java语言的核心...
《Thinking in Java》是Bruce Eckel的经典之作,被誉为学习Java编程的权威指南。...通过阅读和实践书中的例子,你可以提升自己的编程技能,理解Java编程的深度和广度,为解决实际问题打下坚实基础。
"很少见的Java经典代码"这个主题可能包含了那些在实际开发中并不常见,但极具技术深度或者巧妙解决问题的代码示例。这些代码可能是解决特定问题的独特方法,或者是优化性能的关键技巧。下面我们将探讨一些可能包含在...
这份压缩包包含的主要文件是《Java开发手册1.5.pdf》,这是一本全面且深度讲解Java编程的电子书。 在Java开发过程中,遵循一定的规范至关重要,因为这直接影响到代码的可读性、可维护性和团队协作效率。手册中可能...
在IT行业中,Java是一种广泛应用的高级编程语言,尤其在企业级应用开发中占据了主导地位。这份压缩包包含的“JAVA编程题全集(50题及答案).doc”和“Java面试题(附答案).doc”是针对Java程序员准备的面试资源,涵盖了...
《Java疯狂讲义教程》是一本深度探讨Java编程语言的教材,主要针对初学者和有一定基础的开发者。这本书涵盖了从基础语法到高级特性的全面内容,旨在帮助读者深入理解Java编程,提升技能水平。源码和课后习题解析的...
《Java编程艺术》是一本深度探讨Java编程技术与实践的书籍,旨在提升程序员的设计和代码编写技巧。在Java这个广泛使用的编程语言中,理解和掌握这些艺术对于任何开发者来说都至关重要。下面,我们将深入讨论Java编程...
六、Java集合框架深度探索 1. Map接口:HashMap、TreeMap等实现了键值对存储,各有其性能特点和适用场景。 2. Set接口:HashSet、LinkedHashSet、TreeSet等提供了不同的元素唯一性保证和排序规则。 3. List接口:...
7. **集合(Collection)**:Java的`java.util.Collection`接口是所有集合类的父接口,包括单值容器如`Set`和多值容器如`List`。`Set`不允许重复元素,而`List`保持元素顺序。 8. **树(Tree)**:二叉树是一种重要...