ArrayList源码解读

1.背景

源码解读是提升编程能力的有效方式

在面试中也经常问到…..

2.自己开发一个类似ArrayList的对象

解读源码的最佳方式就是自己开发一个类似的….

import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.RandomAccess;

/**
* @author 姿势帝-博客园
* @address https://www.cnblogs.com/newAndHui/
* @WeChat 851298348
* @create 04/04 6:39
* @description

* 需求:自己设计一个基于数组的集合,功能类似ArrayList
* 设计思路
* 1.使用数组来存放添加的元素
* 2.默认数组长度为10,满了后按照原来的1.5倍扩容
* 3.设置的最大数组长度为MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8,实际最大长度不超过 Integer.MAX_VALUE
* 4.编写一个构造方法,一个添加元素的方法,一个获取元素的方法
* 难点:
* 扩容算法,即计算的实际的数组长度
* 总结:
* 当你看懂了我自己写的MyArrayList这个集合类,你再去看ArrayList,
* 你会发现是不是ArrayList是不是"抄袭"我的MyArrayList,居然和我写的一模一样…哈哈哈…

• /
  public class MyArrayList extends AbstractList
  implements List, RandomAccess, Cloneable, java.io.Serializable {
  /*

  • 默认的空集合
    /
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /*
  • 用于存放数据的集合
  • transient:临时的
  • 本文要介绍的是Java中的transient关键字，transient是短暂的意思。
  • 对于transient 修饰的成员变量，在类的实例对象的序列化处理过程中会被忽略。
  • 因此，transient变量不会贯穿对象的序列化和反序列化，生命周期仅存于调用者的内存中而不会写到磁盘里进行持久化。
    /
    transient Object[] elementData;
    // 数组的默认长度
    private static final int DEFAULT_CAPACITY = 10;
    /最大数组长度
    有些虚拟机会预留出一定长度作为数组的一些头信息，所以数组最大长度达不到Integer的最大值2~32-1 = 2147483647(21亿..)左右，
    这个-8是为了避免内存溢出。
    */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;
    // 数组长度
    private int size;

  /*
  * 构造方法
  /
  public MyArrayList() {
  // 设一个默认的空数组,Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

  /*
  * 添加一个元素
  *
  * @param e
  * @return
  /
  @Override
  public boolean add(E e) {
  // 确保数组长度足够,需要的最小长度为当前数组的长度+1
  ensureCapacityInternal(size + 1);
  elementData[size++] = e;
  return true;
  }

  /*
  * 确保数组的容量不出界
  *
  * @param minCapacity
  /
  private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  }

  /*
  * 计算数组的长度(容量)
  *
  * @param elementData 集合的数组
  * @param minCapacity 需要的长度
  * @return 返回一个数组长度
  /
  private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // 如果数组为默认的空数组
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  // 在默认的数组长度10 与 需要的长度中取最大值
  return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
  }

  /*
  * modCount 解读
  * modCount只记录arraylist被修改次数，在每次添加修改删除的时候进行+1，
  * 这个参数的作用是在多线程并发的时候，由于arraylist不是线程安全的，在当前线程进行遍历或其他操作的时候，
  * 如果其它线程修改了改值，那么当前线程能检测到该参数发生变化，会抛异常。
  *
  * @param minCapacity
  /
  private void ensureExplicitCapacity(int minCapacity) {
  // 累加集合的修改次数
  modCount++;
  // 如果需要的数组长度大于了实际的数组长度,则进行扩容
  if (minCapacity – elementData.length > 0)
  grow(minCapacity);
  }

  /
  * 扩容算法
  *
  * @param minCapacity
  /
  private void grow(int minCapacity) {
  // 原来的数组长度
  int oldCapacity = elementData.length;
  / 新的数组长度,
  * 1.oldCapacity >> 1 右移动2位表示除2,即新长度为原来的+原来的一半（若原来为10，变为15）
  * 2.oldCapacity 第一次进入的时候 oldCapacity =0,因此计算出来的newCapacity=0
  */
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 加一半后长度还是不够，则用传递过来的数值(addAll来说，就是原长度+新集合长度)
  if (newCapacity – minCapacity < 0)
  newCapacity = minCapacity;
  // 新的数组长度大于了设置的最大长度时,计算一个新的长度出来
  if (newCapacity – MAX_ARRAY_SIZE > 0)
  newCapacity = hugeCapacity(minCapacity);
  // 执行扩容,扩容的实现时把原来的数组复制到新的数组中来,新的数组长度就是newCapacity
  elementData = Arrays.copyOf(elementData, newCapacity);
  }

  /*
  * 数组最大值计算
  *
  * @param minCapacity 数组的当前需要的最小长度
  /
  private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0)
  throw new OutOfMemoryError();
  // 三目运算 , minCapacity大于当前设置的数组最大值时,就取Integer.MAX_VALUE,否则就是设置的最大值
  // MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;
  return (minCapacity > MAX_ARRAY_SIZE) ?
  Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
  }

  @Override
  public E get(int index) {
  // 检查下标是否越界
  rangeCheck(index);
  return elementData(index);
  }

  private void rangeCheck(int index) {
  if (index >= size)
  throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

  private String outOfBoundsMsg(int index) {
  return "Index: " + index + ", Size: " + size();
  }

  @SuppressWarnings("unchecked")
  E elementData(int index) {
  // 从数组中取出一个元素
  return (E) elementData[index];
  }

  @Override
  public int size() {
  return size;
  }
  }View Code

3.源码解读

3.1.构造方法解读

public ArrayList() {    // 设一个默认的空数组,Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    // 开始new ArrayList()的时候，数组长度其实是0，并不是10，是个空数组。    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

3.2.add方法解读

@Overridepublic boolean add(E e) {    // 确保数组长度足够,需要的最小长度为当前数组的长度+1    ensureCapacityInternal(size + 1);    // 放在当前元素的下一个位置    elementData[size++] = e;    return true;}

确定数组长度的方法ensureCapacityInternal

private void ensureCapacityInternal(int minCapacity) {    // calculateCapacity 计算需要数组长度minCapacity    // ensureExplicitCapacity 确定明确的值,即是否扩容    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}

calculateCapacity 计算需要数组长度minCapacity

private static int calculateCapacity(Object[] elementData, int minCapacity) {    // 如果数组为默认的空数组    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        // 在默认的数组长度10 与 需要的长度中取最大值        return Math.max(DEFAULT_CAPACITY, minCapacity);    }    return minCapacity;}

ensureExplicitCapacity 确定明确的值,即是否扩容

undefined

/** * modCount 解读 * modCount只记录arraylist被修改次数，在每次添加修改删除的时候进行+1， * 这个参数的作用是在多线程并发的时候，由于arraylist不是线程安全的，在当前线程进行遍历或其他操作的时候， * 如果其它线程修改了改值，那么当前线程能检测到该参数发生变化，会抛异常。 * * @param minCapacity */private void ensureExplicitCapacity(int minCapacity) {    // 累加集合的修改次数    modCount++;    // 如果需要的数组长度大于了实际的数组长度,则进行扩容    if (minCapacity - elementData.length > 0)        grow(minCapacity);}

grow扩容算法

/
 * 扩容算法
 
 * @param minCapacity
 /
private void grow(int minCapacity) {
    // 原来的数组长度
    int oldCapacity = elementData.length;
    / 新的数组长度,
     * 1.oldCapacity >> 1 右移动2位表示除2,即新长度为原来的+原来的一半（若原来为10，变为15）
     * 2.oldCapacity 第一次进入的时候 oldCapacity =0,因此计算出来的newCapacity=0
     /
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 加一半后长度还是不够，则用传递过来的数值(addAll来说，就是原长度+新集合长度)
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新的数组长度大于了设置的最大长度时,计算一个新的长度出来
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 执行扩容,扩容的实现时把原来的数组复制到新的数组中来,新的数组长度就是newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

最大长度计算

/
 * 数组最大值计算
 
 * @param minCapacity 数组的当前需要的最小长度
 /
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 三目运算 , minCapacity大于当前设置的数组最大值时,就取Integer.MAX_VALUE,否则就是设置的最大值
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

3.3get方法解读

这个比较简单

@Overridepublic E get(int index) {    // 检查下标是否越界    rangeCheck(index);    // 获取一个元素    return elementData(index);}/** * 检查下标是否越界 * @param index */private void rangeCheck(int index) {    if (index >= size)        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) {    return "Index: " + index + ", Size: " + size();}@SuppressWarnings("unchecked")E elementData(int index) {    // 从数组中取出一个元素    return (E) elementData[index];}

3.4.size方法解读

@Overridepublic int size() {    return size;}

4.总结

新增一个元素，调用add方法，
如果长度没超出，那么就在数组下个位置放置该元素，
如果超出了，按照当前长度的一半增长,采用的是右位移的算法(如果对位移等基础知识不清楚的可以看之前讲的<

最后:其实你采用断点的方式debug一下,或许对源码的理解会更加深入.

完美!

Original: https://www.cnblogs.com/newAndHui/p/16101626.html
Author: 李东平|一线码农
Title: ArrayList源码解读