您现在的位置是:首页 > 文章详情

ArrayList源码分析

日期:2019-04-23点击:285

一、核心变量

 // 序列化ID private static final long serialVersionUID = 8683452581122892189L; // 默认初始化容量 private static final int DEFAULT_CAPACITY = 10; // 空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 存储数据元素的数组 transient Object[] elementData; // non-private to simplify nested class access // 当前arraylist集合的大小,也就是elementData数组中数据元素的个数 private int size; 

二、构造函数

 /** * 一:无参构造方法 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 二:携带一个int类型的参数,指定arraylist的初始容量 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } 
1、无参构造

可以看到,在构造方法中直接将 elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组,这个时候该ArrayList的size为初始值0。

1、有参构造

进行参数校验:
参数大于0,则指定数组长度;
参数等于0,则为空数组;
参数小于0,则抛异常。

三、add方法

 /** * 一:直接添加数据元素到arraylist的尾部 */ public boolean add(E e) { //是否扩容、记录modCount ensureCapacityInternal(size + 1); // Increments modCount!! //把值添加到数组尾部 elementData[size++] = e; return true; } ---------------------------------------------------------------------- private void ensureCapacityInternal(int minCapacity) { //minCapacity=size+1; //minCapacity表示如果添加成功后,数组的最小长度 //如果为无参构造 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //取默认长度和minCapacity的最大值,即10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //是否扩容 ensureExplicitCapacity(minCapacity); } ---------------------------------------------------------------------- private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果添加后最小长度大于 数组长度 if (minCapacity - elementData.length > 0) //扩容 grow(minCapacity); } ---------------------------------------------------------------------- private void grow(int minCapacity) { //获取数组长度 int oldCapacity = elementData.length; //1.5倍扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5倍扩容也不够用 if (newCapacity - minCapacity < 0) //扩容后长度=minCapacity newCapacity = minCapacity; //简直最大长度 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 复制 elementData = Arrays.copyOf(elementData, newCapacity); } 

代码中已经有注释了,很清晰。

四、remove方法

/* * 一:根据角标进行remove操作 */ public E remove(int index) { // 1. 对角标越界进行判断 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); // 2.modCount自增1 modCount++; // 3.获取到指定下角标位置的数据 E oldValue = (E) elementData[index]; // 4.计算需要移动的元素个数 int numMoved = size - index - 1; if (numMoved > 0) // 5. 指定角标位置后的元素前移一位,效率低 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 6.将size自减1,并将数组末尾置为null,便于垃圾回收 elementData[--size] = null; // clear to let GC do its work // 7.最后将所要删除的数据元素return掉 return oldValue; } /* * 二:根据数据元素进行remove操作 */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } ---------------------------------------------------------------------- private void fastRemove(int index) { // 1.modCount的值自增1 modCount++; // 2.计算需要移动的元素个数 int numMoved = size - index - 1; if (numMoved > 0) // 3. 指定角标位置后的元素前移一位 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 4.将size自减1,并将数组末尾置为null,便于垃圾回收 elementData[--size] = null; // clear to let GC do its work } 

五、set方法

public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); //检查modCount checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } ---------------------------------------------------------------------- public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } ---------------------------------------------------------------------- final void checkForComodification() { if (expectedModCount != ArrayList.this.modCount) throw new ConcurrentModificationException(); } 

六、get方法

public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } ---------------------------------------------------------------------- E elementData(int index) { return (E) elementData[index]; } 

七、clear方法

public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } 

八、contains方法

public boolean contains(Object o) { return indexOf(o) >= 0; } ---------------------------------------------------------------------- public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } 

未命名文件.jpg

九、fail-fast机制

ail-fast机制是集合中的一种错误检测机制,我们在操作集合中经常会遇到 java.util.ConcurrentModificationException异常,产生该异常的原因就是fail-fast机制。

实现:如果在迭代期间计数器被修改,那么hasNext或next将抛出concurrentModificationException
缺点:这种检查是没有同步的情况下进行的,因此可能会看到失效的计数值,而迭代器可能并没有意识到已经发生了修改。这是一种设计上的权衡,从而降低了并发修改操作的检测代码对程序性能带来的影响。

十、可能的并发问题

  1. add()
    EX:a、100个元素,可能最后数组长度不到100。
    两个线程并发add,对索引位置5的地方几乎同时赋值,第二个线程会覆盖第一个线程的值,并且size少了1个。
    b、假设有两个线程在操作同一个ArrayList,线程一执行step1(容量足够)后被挂起,线程二执行add()方法后,线程一被唤醒,这时线程一因为已经不再判断容量是否足够(已经判断过),执行step2就会出现数组越界
  2. 数组容量检测的并发问题
  3. remove
    两个线程有可能会想要删除同一个内容,一个线程先完成的时候第二个线程再删,就找不到这个内容了
原文链接:https://my.oschina.net/u/3670641/blog/3041455
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章