Java集合04 - RandomAccess

绝地灬酷狼 2022-12-27 12:54 245阅读 0赞

目录

1.什么是RandomAccess

2.RandomAccess具体实现

3.两种遍历方法性能测试


笔者JDK版本:1.8.0_202

1.什么是RandomAccess

  1. RandomAccessCloneableSerializable接口一样,本质上都是一种标志性接口,无具体实现,意在告知JVM此类(在恒定时间内)可支持快速随机访问。源码中一大段话翻译过来讲了这么几件事:
  2. 1)给List使用的标记型接口,目的是使其支持(在恒定时间内)的快速随机访问
  3. 2)推荐在遍历集合的时候检查该List是否实现了RandomAccess接口,以便让不同的集合使用更优的遍历算法(ArrayListfor循环遍历快一些,LinkedList用迭代器遍历快一些)
  4. 3)通常来说,如果一个Listfor循环遍历比用迭代器遍历的速度快,那么推荐实现RandomAccess接口

2.RandomAccess具体实现

  1. Java中的Collectons类提供了静态操作集合的方法,一起看下Collectons中对RandomAccess接口的判断:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2

  1. 如果这个集合实现了RandomAccess接口或者集合大小小于二分查找阀值时,按下标二分查找,否则使用迭代器实现二分查找,对应源码中说到的第2点和第3点。

3.两种遍历方法性能测试

DEMO:

  1. private static void computingTime(List list) {
  2. long startTime;
  3. long endTime;
  4. if (list instanceof RandomAccess) {
  5. System.out.println(list.getClass() + "实现了RandomAccess接口");
  6. } else {
  7. System.out.println(list.getClass() + "未实现RandomAccess接口");
  8. }
  9. startTime = System.currentTimeMillis();
  10. for (int i = 0; i < list.size(); i++) {
  11. Object o = list.get(i);
  12. }
  13. endTime = System.currentTimeMillis();
  14. System.out.println("采用for循环的方式遍历集合耗时:" + (endTime - startTime) + "ms");
  15. startTime = System.currentTimeMillis();
  16. for (Iterator iter = list.iterator(); iter.hasNext(); ) {
  17. Object o = iter.next();
  18. }
  19. endTime = System.currentTimeMillis();
  20. System.out.println("采用迭代器的方式遍历集合耗时:" + (endTime - startTime) + "ms");
  21. }
  22. public static void main(String[] args) {
  23. ArrayList<Integer> arrayList = new ArrayList<>();
  24. int listSize = 100000;
  25. for (int i = 0; i < listSize; i++) {
  26. arrayList.add(i);
  27. }
  28. List<Integer> linkedList = new LinkedList<>();
  29. for (int i = 0; i < listSize; i++) {
  30. linkedList.add(i);
  31. }
  32. computingTime(arrayList);
  33. computingTime(linkedList);
  34. }

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3

  1. 测试demo很简单,10W条数据存入ArrayListLinkedList后,分别用for循环和迭代器来遍历这两个集合记录遍历时间。通过结果可知,ArrayList for循环遍历的时间小于迭代器遍历时间,而LinkedList for循环遍历的时间选超迭代器遍历时间。原因就和这两个集合的底层实现有关了(在接下来的文章内会详谈),ArrayList底层动态扩容数组,查询时间复杂度O(1),所以两种方式遍历区别不大,快速随机访问略胜一筹;而LinkedList底层基于双向循环链表,因为链表的特性,迭代器查找比快速随机访问(时间复杂度O(n))快的多。

发表评论

表情:
评论列表 (有 0 条评论,245人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Java 2

    set Set接口存储一组唯一,无序的对象 HashSet 是set接口常用得实现类。HashSet 允许集合元素值为null 操作数据的方法与list类似,set 接口

    相关 JAVA

    线性表、栈、队列、优先队列和集合 数据结构是以某种形式将数据组织在一起的合集。数据结构不仅存储数据,还支持访问和处理数据的操作。 JAVA的合集框架如下图所示![在这