最近在看jdk的源码,看到ArrayList的时候发现一个问题,在插入的时候,如果进行扩容,会进行两次数组的copy。
第一次:
public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // 在此把整个数组copy到一个新的数组 elementData = Arrays.copyOf(elementData, newCapacity); } }
第二次拷贝:
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); // 如果数组长度不足,将进行扩容 ensureCapacity(size+1); // Increments modCount!! // copy发生在这里,index后边的数据都需要再次copy System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
从代码可以看到,从插入点index后边的数据如果需要扩容,则会拷贝两次。一次为拷贝到新的数组,一次为整体向后挪一位。
后来考虑是不是可以创建新数组的时候拷贝两次,把index以前的数据先copy到新数组,然后index以后的数据直接向后挪一位copy入新的数组。
修改后的代码:
public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); // 如果数组长度不足,将进行扩容 // ensureCapacity(size+1); // Increments modCount!! int minCapacity = size + 1; modCount++; int oldCapacity = elementData.length; Object[] newObj = null; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3) / 2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; newObj = new Object[newCapacity]; } if (newObj != null) { System.arraycopy(elementData, 0, newObj, 0, index); System.arraycopy(elementData, index, newObj, index + 1, size - index); elementData = newObj; } else { System.arraycopy(elementData, index, elementData, index + 1, size - index); } elementData[index] = element; size++; }
因环境问题,过段时间找台测试机器把测试结果贴出来。目前在本机测效率无提升,不知道是因为机器上东西太多还是因为这个思路本身不对。
相关推荐
本资源根据个人学习和总结,主要介绍Java中ArrayList扩容机制源码的解析,主要包含文字和代码等内容,以源码的形式进行分析,详细介绍了ArrayList扩容机制的整个流程,特此将该资源分享
主要介绍了Java ArrayList扩容问题实例详解,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
Arraylist扩容原理走读
ArrayList集合与HashMap的扩容原来.docx
ArrayList的列表对象实质上是存储在一个引用型数组里的,下面这篇文章主要给大家介绍了关于Java中Arraylist动态扩容方法的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...
今天小编就为大家分享一篇对Java ArrayList的自动扩容机制示例讲解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
今天小编就为大家分享一篇关于ArrayList及HashMap的扩容规则讲解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
主要介绍了Java使用数组实现ArrayList的动态扩容的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
C语言版的ArrayList,具有ArrayList的基本方法增加、插入、删除、自动扩容等。
主要介绍了聊一聊jdk1.8中的ArrayList 底层数组是如何扩容的,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
软通面试答案,里面有我去软通面试的题目和答案供有需要帮助的朋友提供帮助 14 .关于 ArrayList 答案: ordered no sorttrd 并且是按照 index 排 15- 如何从 ArrayList 里取对象? 用 get(int index) 这个方法。
初始申请的空间与扩容阈值之间的关系,围绕第二次扩容阈值与初始指定申请空间的关系说明 4、模拟写一个新增或删除或扩容的方法 5、是否线程安全?为何不安全?如果不安全如何规避或替代类? 6、for循环数据过程中...
ArrayList Jdk1.8采用的是数组的数据结构,是非线程安全的一个集合 (多线程下数据不安全),本文章主要讲解ArrayList集合添加和集合扩容,其他方法都相对简单,读懂这个后相信你翻翻源码即可读懂其他方法原理,下面...
首先,它不是静态的,编译时每一维度的元素个数不用指定,系统默认元素个数为16,当元素增多并即将大于16时,它会增倍扩容到32,依次规律增长,变小时,相反处理。 其次,元素类型是弱类型,object。在运行时,...
阅读本文大约需要10分钟,将分成两部分解读ArrayList的扩容机制,源码部分来源于JDK8。 首先,挖个坑:为什么要尽量指定集合大小? 集合初始化 集合初始化有两种方式,直接new,或者在new的时候指定集合大小 List ...
掌握 ArrayList 的扩容机制 掌握 Iterator 的 fail-fast 、fail-safe 机制 ArrayList() 会使用长度为零的数组 ArrayList(int initialCapacity) 会使用指定容量的数组 public ArrayList(Collection<? extends E> c) ...
老猿说说-ArrayList MD文件 ...4. 除了数组+链表+红黑树的基本结构外,新增了转移节点,是为了保证扩容时的线程安全的节点; 5. 提供了很多Stream流式方法,比如说:forEach、search、reduce等等。
适用人群:JavaSE初学者,对源码感兴趣的,想要深度了解ArrayList底层实现、数据结构、add方法、Remove方法、以及自动扩容机制的同学,并且对ArrayList已经有过使用,想要学习它与LinkedList,Vector等的区别,该...
1、首先看ArrayList默认构造方法创建 /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first ...
ArrayList与LinkedListArrayList与LinkedList扩容数组最大容量默认的初始容量扩容新容量=旧容量*1.5* Increases