精华内容
下载资源
问答
  • 起因做java开发有一些年头,常用的工具类相比大家都很熟悉,但是对于其中的实现机制,如果不曾细看,还真回答不上来,前日一友人问起StringBuffer和StringBuilder有什么区别,我自以对答如流,当问起StringBuffer...

    起因

    做java开发有一些年头,常用的工具类相比大家都很熟悉,但是对于其中的实现机制,如果不曾细看,还真回答不上来,前日一友人问起StringBuffer和StringBuilder有什么区别,我自以对答如流,当问起StringBuffer扩容机制,我表示只知底层为数组,不知道如何扩容,甚是惭愧,于是我读了下相应的源码,希望把自己看到的能分享一下

    扩容源码解析

    首先我们看一下StringBuffer的继承结构

    d72513bb9a29e09e02a7a1abdae56b77.png

    StringBuffer继承结构

    可以看到其实StringBuffer继承自AbstractStringBuilder并且实现了CharSequence和Serializable接口

    cb5743f49aed584f26eb00f86be34927.png

    父类append方法

    从上图可以看出,StringBuffer是调用的父类AbstractStringBuilder的append方法并且使用ensureCapacityInternal方法进行扩容,图中count变量为目前数组的长度,下面看下ensureCapacityInternal的实现

    f818825572a507d8f77d869065c45b64.png

    扩容

    上图我们可以看到新的数组长度为原来的数组长度的两倍加2,如果新的字符串长度加上原字符串的长度大于原来的数组长度的两倍加2则新数组的长度为新的字符串长度加上原字符串的长度,有点拗口,哈哈,不过大概这个意思

    以上就是我对StringBuffer扩容的解读,欢迎拍砖

    展开全文
  • Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。ArrayList继承于 AbstractList,实现了 List, ...

    ArrayList 简介

    ArrayList 的底层是数组队列,相当于动态数组。与 Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

    ArrayList继承于 AbstractList,实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

    3b808ca1c16a2344fe8b54354ad31d0f.pngpublic class ArrayList extends AbstractList

    implements List, RandomAccess, Cloneable, java.io.Serializable{}

    复制代码RandomAccess 是一个标志接口(空接口),表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中,我们即可以通过元素的序号快速获取元素对象,这就是快速随机访问。(原因是:底层是使用Object[]数组存储数据的)

    ArrayList 实现了 Cloneable 接口 ,即覆盖了函数clone(),能被克隆。

    ArrayList 实现了java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。

    ArrayList 核心源码解读

    JDK1.8版本package java.util;

    import java.util.function.Consumer;

    import java.util.function.Predicate;

    import java.util.function.UnaryOperator;

    public class ArrayList extends AbstractList

    implements List, RandomAccess, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = 8683452581122892189L;

    /**

    * 默认初始容量大小

    */

    private static final int DEFAULT_CAPACITY = 10;

    /**

    * 空数组(用于空实例)。

    */

    private static final Object[] EMPTY_ELEMENTDATA = {};

    //用于默认大小空实例的共享空数组实例。

    //我们把它从EMPTY_ELEMENTDATA数组中区分出来,以知道在添加第一个元素时容量需要增加多少。

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**

    * 保存ArrayList数据的数组

    */

    transient Object[] elementData; // non-private to simplify nested class access

    /**

    * ArrayList 所包含的元素个数

    */

    private int size;

    /**

    * 带初始容量参数的构造函数(用户可以在创建ArrayList对象时自己指定集合的初始大小)

    */

    public ArrayList(int initialCapacity) {

    if (initialCapacity > 0) {

    //如果传入的参数大于0,创建initialCapacity大小的数组

    this.elementData = new Object[initialCapacity];

    } else if (initialCapacity == 0) {

    //如果传入的参数等于0,创建空数组

    this.elementData = EMPTY_ELEMENTDATA;

    } else {

    //其他情况,抛出异常

    throw new IllegalArgumentException("Illegal Capacity: "+

    initialCapacity);

    }

    }

    /**

    *默认无参构造函数

    *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10,也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10

    */

    public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    /**

    * 构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。

    */

    public ArrayList(Collection extends E> c) {

    //将指定集合转换为数组

    elementData = c.toArray();

    //如果elementData数组的长度不为0

    if ((size = elementData.length) != 0) {

    // 如果elementData不是Object类型数据(c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断)

    if (elementData.getClass() != Object[].class)

    //将原来不是Object类型的elementData数组的内容,赋值给新的Object类型的elementData数组

    elementData = Arrays.copyOf(elementData, size, Object[].class);

    } else {

    // 其他情况,用空数组代替

    this.elementData = EMPTY_ELEMENTDATA;

    }

    }

    /**

    * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。

    */

    public void trimToSize() {

    modCount++;

    if (size < elementData.length) {

    elementData = (size == 0)

    ? EMPTY_ELEMENTDATA

    : Arrays.copyOf(elementData, size);

    }

    }

    //下面是ArrayList的扩容机制

    //ArrayList的扩容机制提高了性能,如果每次只扩充一个,

    //那么频繁的插入会导致频繁的拷贝,降低性能,而ArrayList的扩容机制避免了这种情况。

    /**

    * 如有必要,增加此ArrayList实例的容量,以确保它至少能容纳元素的数量

    * @param minCapacity 所需的最小容量

    */

    public void ensureCapacity(int minCapacity) {

    //如果是true,minExpand的值为0,如果是false,minExpand的值为10

    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

    // any size if not default element table

    ? 0

    // larger than default for default empty table. It's already

    // supposed to be at default size.

    : DEFAULT_CAPACITY;

    //如果最小容量大于已有的最大容量

    if (minCapacity > minExpand) {

    ensureExplicitCapacity(minCapacity);

    }

    }

    //得到最小扩容量

    private void ensureCapacityInternal(int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

    // 获取“默认的容量”和“传入参数”两者之间的最大值

    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    ensureExplicitCapacity(minCapacity);

    }

    //判断是否需要扩容

    private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    //调用grow方法进行扩容,调用此方法代表已经开始扩容了

    grow(minCapacity);

    }

    /**

    * 要分配的最大数组大小

    */

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**

    * ArrayList扩容的核心方法。

    */

    private void grow(int minCapacity) {

    // oldCapacity为旧容量,newCapacity为新容量

    int oldCapacity = elementData.length;

    //将oldCapacity 右移一位,其效果相当于oldCapacity /2,

    //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    //再检查新容量是否超出了ArrayList所定义的最大容量,

    //若超出了,则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE,

    //如果minCapacity大于MAX_ARRAY_SIZE,则新容量则为Interger.MAX_VALUE,否则,新容量大小则为 MAX_ARRAY_SIZE。

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    elementData = Arrays.copyOf(elementData, newCapacity);

    }

    //比较minCapacity和 MAX_ARRAY_SIZE

    private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow

    throw new OutOfMemoryError();

    return (minCapacity > MAX_ARRAY_SIZE) ?

    Integer.MAX_VALUE :

    MAX_ARRAY_SIZE;

    }

    /**

    *返回此列表中的元素数。

    */

    public int size() {

    return size;

    }

    /**

    * 如果此列表不包含元素,则返回 true 。

    */

    public boolean isEmpty() {

    //注意=和==的区别

    return size == 0;

    }

    /**

    * 如果此列表包含指定的元素,则返回true 。

    */

    public boolean contains(Object o) {

    //indexOf()方法:返回此列表中指定元素的首次出现的索引,如果此列表不包含此元素,则为-1

    return indexOf(o) >= 0;

    }

    /**

    *返回此列表中指定元素的首次出现的索引,如果此列表不包含此元素,则为-1

    */

    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++)

    //equals()方法比较

    if (o.equals(elementData[i]))

    return i;

    }

    return -1;

    }

    /**

    * 返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。.

    */

    public int lastIndexOf(Object o) {

    if (o == null) {

    for (int i = size-1; i >= 0; i--)

    if (elementData[i]==null)

    return i;

    } else {

    for (int i = size-1; i >= 0; i--)

    if (o.equals(elementData[i]))

    return i;

    }

    return -1;

    }

    /**

    * 返回此ArrayList实例的浅拷贝。 (元素本身不被复制。)

    */

    public Object clone() {

    try {

    ArrayList> v = (ArrayList>) super.clone();

    //Arrays.copyOf功能是实现数组的复制,返回复制后的数组。参数是被复制的数组和复制的长度

    v.elementData = Arrays.copyOf(elementData, size);

    v.modCount = 0;

    return v;

    } catch (CloneNotSupportedException e) {

    // 这不应该发生,因为我们是可以克隆的

    throw new InternalError(e);

    }

    }

    /**

    *以正确的顺序(从第一个到最后一个元素)返回一个包含此列表中所有元素的数组。

    *返回的数组将是“安全的”,因为该列表不保留对它的引用。 (换句话说,这个方法必须分配一个新的数组)。

    *因此,调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。

    */

    public Object[] toArray() {

    return Arrays.copyOf(elementData, size);

    }

    /**

    * 以正确的顺序返回一个包含此列表中所有元素的数组(从第一个到最后一个元素);

    *返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组,则返回其中。

    *否则,将为指定数组的运行时类型和此列表的大小分配一个新数组。

    *如果列表适用于指定的数组,其余空间(即数组的列表数量多于此元素),则紧跟在集合结束后的数组中的元素设置为null 。

    *(这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。)

    */

    @SuppressWarnings("unchecked")

    public T[] toArray(T[] a) {

    if (a.length < size)

    // 新建一个运行时类型的数组,但是ArrayList数组的内容

    return (T[]) Arrays.copyOf(elementData, size, a.getClass());

    //调用System提供的arraycopy()方法实现数组之间的复制

    System.arraycopy(elementData, 0, a, 0, size);

    if (a.length > size)

    a[size] = null;

    return a;

    }

    // Positional Access Operations

    @SuppressWarnings("unchecked")

    E elementData(int index) {

    return (E) elementData[index];

    }

    /**

    * 返回此列表中指定位置的元素。

    */

    public E get(int index) {

    rangeCheck(index);

    return elementData(index);

    }

    /**

    * 用指定的元素替换此列表中指定位置的元素。

    */

    public E set(int index, E element) {

    //对index进行界限检查

    rangeCheck(index);

    E oldValue = elementData(index);

    elementData[index] = element;

    //返回原来在这个位置的元素

    return oldValue;

    }

    /**

    * 将指定的元素追加到此列表的末尾。

    */

    public boolean add(E e) {

    ensureCapacityInternal(size + 1); // Increments modCount!!

    //这里看到ArrayList添加元素的实质就相当于为数组赋值

    elementData[size++] = e;

    return true;

    }

    /**

    * 在此列表中的指定位置插入指定的元素。

    *先调用 rangeCheckForAdd 对index进行界限检查;然后调用 ensureCapacityInternal 方法保证capacity足够大;

    *再将从index开始之后的所有成员后移一个位置;将element插入index位置;最后size加1。

    */

    public void add(int index, E element) {

    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1); // Increments modCount!!

    //arraycopy()这个实现数组之间复制的方法一定要看一下,下面就用到了arraycopy()方法实现数组自己复制自己

    System.arraycopy(elementData, index, elementData, index + 1,

    size - index);

    elementData[index] = element;

    size++;

    }

    /**

    * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧(从其索引中减去一个元素)。

    */

    public E remove(int index) {

    rangeCheck(index);

    modCount++;

    E oldValue = elementData(index);

    int numMoved = size - index - 1;

    if (numMoved > 0)

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    elementData[--size] = null; // clear to let GC do its work

    //从列表中删除的元素

    return oldValue;

    }

    /**

    * 从列表中删除指定元素的第一个出现(如果存在)。 如果列表不包含该元素,则它不会更改。

    *返回true,如果此列表包含指定的元素

    */

    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 remove method that skips bounds checking and does not

    * return the value removed.

    */

    private void fastRemove(int index) {

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    elementData[--size] = null; // clear to let GC do its work

    }

    /**

    * 从列表中删除所有元素。

    */

    public void clear() {

    modCount++;

    // 把数组中所有的元素的值设为null

    for (int i = 0; i < size; i++)

    elementData[i] = null;

    size = 0;

    }

    /**

    * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。

    */

    public boolean addAll(Collection extends E> c) {

    Object[] a = c.toArray();

    int numNew = a.length;

    ensureCapacityInternal(size + numNew); // Increments modCount

    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

    }

    /**

    * 将指定集合中的所有元素插入到此列表中,从指定的位置开始。

    */

    public boolean addAll(int index, Collection extends E> c) {

    rangeCheckForAdd(index);

    Object[] a = c.toArray();

    int numNew = a.length;

    ensureCapacityInternal(size + numNew); // Increments modCount

    int numMoved = size - index;

    if (numMoved > 0)

    System.arraycopy(elementData, index, elementData, index + numNew,

    numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);

    size += numNew;

    return numNew != 0;

    }

    /**

    * 从此列表中删除所有索引为fromIndex (含)和toIndex之间的元素。

    *将任何后续元素移动到左侧(减少其索引)。

    */

    protected void removeRange(int fromIndex, int toIndex) {

    modCount++;

    int numMoved = size - toIndex;

    System.arraycopy(elementData, toIndex, elementData, fromIndex,

    numMoved);

    // clear to let GC do its work

    int newSize = size - (toIndex-fromIndex);

    for (int i = newSize; i < size; i++) {

    elementData[i] = null;

    }

    size = newSize;

    }

    /**

    * 检查给定的索引是否在范围内。

    */

    private void rangeCheck(int index) {

    if (index >= size)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    /**

    * add和addAll使用的rangeCheck的一个版本

    */

    private void rangeCheckForAdd(int index) {

    if (index > size || index < 0)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    /**

    * 返回IndexOutOfBoundsException细节信息

    */

    private String outOfBoundsMsg(int index) {

    return "Index: "+index+", Size: "+size;

    }

    /**

    * 从此列表中删除指定集合中包含的所有元素。

    */

    public boolean removeAll(Collection> c) {

    Objects.requireNonNull(c);

    //如果此列表被修改则返回true

    return batchRemove(c, false);

    }

    /**

    * 仅保留此列表中包含在指定集合中的元素。

    *换句话说,从此列表中删除其中不包含在指定集合中的所有元素。

    */

    public boolean retainAll(Collection> c) {

    Objects.requireNonNull(c);

    return batchRemove(c, true);

    }

    /**

    * 从列表中的指定位置开始,返回列表中的元素(按正确顺序)的列表迭代器。

    *指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。

    *返回的列表迭代器是fail-fast 。

    */

    public ListIterator listIterator(int index) {

    if (index < 0 || index > size)

    throw new IndexOutOfBoundsException("Index: "+index);

    return new ListItr(index);

    }

    /**

    *返回列表中的列表迭代器(按适当的顺序)。

    *返回的列表迭代器是fail-fast 。

    */

    public ListIterator listIterator() {

    return new ListItr(0);

    }

    /**

    *以正确的顺序返回该列表中的元素的迭代器。

    *返回的迭代器是fail-fast 。

    */

    public Iterator iterator() {

    return new Itr();

    }

    复制代码

    ArrayList 扩容机制分析

    构造函数

    ArrayList 有三种方式来初始化,构造方法源码如下:/**

    * 默认初始容量大小

    */

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**

    *默认构造函数,使用初始容量10构造一个空列表(无参数构造)

    */

    public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    /**

    * 带初始容量参数的构造函数。(用户自己指定容量)

    */

    public ArrayList(int initialCapacity) {

    if (initialCapacity > 0) {//初始容量大于0

    //创建initialCapacity大小的数组

    this.elementData = new Object[initialCapacity];

    } else if (initialCapacity == 0) {//初始容量等于0

    //创建空数组

    this.elementData = EMPTY_ELEMENTDATA;

    } else {//初始容量小于0,抛出异常

    throw new IllegalArgumentException("Illegal Capacity: "+

    initialCapacity);

    }

    }

    /**

    *构造包含指定collection元素的列表,这些元素利用该集合的迭代器按顺序返回

    *如果指定的集合为null,throws NullPointerException。

    */

    public ArrayList(Collection extends E> c) {

    elementData = c.toArray();

    if ((size = elementData.length) != 0) {

    // c.toArray might (incorrectly) not return Object[] (see 6260652)

    if (elementData.getClass() != Object[].class)

    elementData = Arrays.copyOf(elementData, size, Object[].class);

    } else {

    // replace with empty array.

    this.elementData = EMPTY_ELEMENTDATA;

    }

    }

    复制代码

    d9faf9cc8bb751c0e95ff4b6c6b01647.png//默认初始容量大小

    private static final int DEFAULT_CAPACITY = 10;

    //空数组(用于空实例)。

    private static final Object[] EMPTY_ELEMENTDATA = {};

    //用于默认大小空实例的共享空数组实例。

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //保存ArrayList数据的数组

    transient Object[] elementData; // non-private to simplify nested class access

    //ArrayList 所包含的元素个数

    private int size;

    //默认构造函数,使用初始容量10构造一个空列表(无参数构造)

    public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    复制代码

    以无参数构造方法创建 ArrayList 时,实际上初始化赋值的是一个空数组。

    b4a0f4c98b5901d8748d9f166dbc8e11.png

    那么什么时候才真正分配容量呢??答案是添加第一个元素时

    add()

    6ed9fb50334662a048a14f491d2b9a8a.png/**

    * 将指定的元素追加到此列表的末尾。

    */

    public boolean add(E e) {

    //添加元素之前,先调用ensureCapacityInternal方法

    ensureCapacityInternal(size + 1); // Increments modCount!!

    //这里看到ArrayList添加元素的实质就相当于为数组赋值

    elementData[size++] = e;

    return true;

    }

    复制代码

    add()将制定的元素追加到末尾, 我们可以看到该方法中首先是调用了 ensureCapacityInternal(size + 1); size+1 =0+1=1。

    ensureCapacityInternal()

    该方法得到的是得到最小扩容量minCapacity

    a3868e74be9bd198a60c391dd8c91abd.png//得到的是得到最小扩容量minCapacity

    private void ensureCapacityInternal(int minCapacity) {

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    }

    复制代码

    该方法中调用的是ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    calculateCapacity()

    我们首先来看calculateCapacity这个方法,计算容量

    aa89110ae1e06b064d67ddf7e8cb9d37.pngprivate static int calculateCapacity(Object[] elementData, int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

    return Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    return minCapacity;

    }

    复制代码

    elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA使用默认构造器时已经赋值this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;所以符合条件为true。

    return Math.max(DEFAULT_CAPACITY, minCapacity); 比较两值取最大值。DEFAULT_CAPACITY 值为10,minCapacity为传过来的值,第一次为size+1=0+1=1。所以最大值为10。返回10。

    ensureExplicitCapacity()

    此时我们再会到add方法中查看这个被调用的ensureExplicitCapacity方法,该方法是判断是否需要扩容

    41851308757561f310fad56f5b9de757.png//判断是否需要扩容

    private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    //调用grow方法进行扩容,调用此方法代表已经开始扩容了

    grow(minCapacity);

    }

    复制代码

    第一次添加元素时,我们经过重重判断已经得到了minCapacity=10,此时判断minCapacity - elementData.length > 0此时到数据长度还是为0,所以10-0=10>0,符合条件调用grow()方法。当我们要 add 进第 1 个元素到 ArrayList 时,elementData.length 为 0 (因为还是一个空的 list),因为执行了 ensureCapacityInternal() 方法 ,所以 minCapacity 此时为 10。此时,minCapacity - elementData.length > 0成立,所以会进入 grow(minCapacity) 方法。

    当 add 第 2 个元素时,minCapacity 为 2,此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时,minCapacity - elementData.length > 0 不成立,所以不会进入 (执行)grow(minCapacity) 方法。

    添加第 3、4···到第 10 个元素时,依然不会执行 grow 方法,数组容量都为 10。

    直到添加第 11 个元素,minCapacity(为 11)比 elementData.length(为 10)要大。进入 grow 方法进行扩容。

    当我们添加第1个元素,和第11个元素时是符合扩容条件的。

    grow()

    要分配的最大数组大小

    51f9a46c30b26e19c7ad89526c7f40a9.png

    添加第1个元素时:int oldCapacity = elementData.length; oldCapacity=0;

    int newCapacity = oldCapacity + (oldCapacity >> 1); newCapacity = 0 + 0/2 = 0;

    newCapacity这个代表了新的数组的大小,>>1 右移一位相当于除 2,加上原数组大小的一半,也就是扩容1.5oldCapacity 为偶数就是 1.5 倍,否则是 1.5 倍左右)! 奇偶不同,比如 :10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

    第一个if条件newCapacity - minCapacity < 0此时是满足的0-10=-10<0,所以newCapacity = minCapacity;此时newCapacity为10

    第二个if条件newCapacity - MAX_ARRAY_SIZE > 0由上面定义的代码可以的得到private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;这个数是21亿,比他小。不符合。

    elementData = Arrays.copyOf(elementData, newCapacity);通过Arrays.copy将原本的数组复制并且长度变成了newCapacity也就是10。此时我们的ArrayList也就终于有了容量。默认为10

    此时终于可以回到add方法了执行后面的代码elementData[size++] = e;此时elemetnData的长度已经为10了,size为0,在elementData[0]添加元素,size+1=1。返回true。

    191f6626c3a3ac6f6bd2d7bc304e256f.png

    当添加第11个元素时:int oldCapacity = elementData.length; 为10

    int newCapacity = oldCapacity + (oldCapacity >> 1); 10+10/2 = 15

    全都不符elementData = Arrays.copyOf(elementData, newCapacity);复制原数组扩容为15。/**

    * 要分配的最大数组大小

    */

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**

    * ArrayList扩容的核心方法。

    */

    private void grow(int minCapacity) {

    // oldCapacity为旧容量,newCapacity为新容量

    int oldCapacity = elementData.length;

    //将oldCapacity 右移一位,其效果相当于oldCapacity /2,

    //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,

    //如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    elementData = Arrays.copyOf(elementData, newCapacity);

    }

    复制代码

    hugeCapacity()

    从上面 grow() 方法源码我们知道: 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,如果 minCapacity 大于最大容量,则新容量则为Integer.MAX_VALUE,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

    38eb6b6c438bc08016ed2d34bc091139.pngprivate static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow

    throw new OutOfMemoryError();

    //对minCapacity和MAX_ARRAY_SIZE进行比较

    //若minCapacity大,将Integer.MAX_VALUE作为新数组的大小

    //若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小

    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    return (minCapacity > MAX_ARRAY_SIZE) ?

    Integer.MAX_VALUE :

    MAX_ARRAY_SIZE;

    }

    复制代码

    System.arraycopy() 和 Arrays.copyOf()

    阅读源码的话,我们就会发现 ArrayList 中大量调用了这两个方法。比如:我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法!

    2eb743107d85f051bc82c557afd5def1.png

    a32593b4051abb86ec8bee19c3bda111.png

    看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

    arraycopy() 需要目标数组,将原数组拷贝到你自己定义的数组里或者原数组,而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组,并返回该数组。

    总结

    当我们使用默认的构造器是实例化ArrayList时,数组大小经过种种判断扩容为10。

    使用默认构造器实例化的ArrayList,在第一次添加元素和第11次添加元素时才会触发扩容。也就是第一次时,和超过数组容量时添加才触发扩容。

    而初始化指定实例化创建的ArrayList只有超过数组容量时添加才触发扩容。扩容为1.5倍左右(分奇偶数)

    ensureCapacity方法

    ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有,这个方法 ArrayList 内部没有被调用过,所以很显然是提供给用户调用的,那么这个方法有什么作用呢?/**

    如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minimum capacity参数指定的元素数。

    *

    * @param minCapacity 所需的最小容量

    */

    public void ensureCapacity(int minCapacity) {

    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

    // any size if not default element table

    ? 0

    // larger than default for default empty table. It's already

    // supposed to be at default size.

    : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {

    ensureExplicitCapacity(minCapacity);

    }

    }

    复制代码

    最好在 add 大量元素之前用 ensureCapacity 方法,以减少增量重新分配的次数

    我们通过下面的代码实际测试以下这个方法的效果:public class EnsureCapacityTest {

    public static void main(String[] args) {

    ArrayList list = new ArrayList();

    final int N = 10000000;

    long startTime = System.currentTimeMillis();

    for (int i = 0; i < N; i++) {

    list.add(i);

    }

    long endTime = System.currentTimeMillis();

    System.out.println("使用ensureCapacity方法前:"+(endTime - startTime));

    }

    }

    复制代码

    运行结果:使用ensureCapacity方法前:2158

    复制代码public class EnsureCapacityTest {

    public static void main(String[] args) {

    ArrayList list = new ArrayList();

    final int N = 10000000;

    list = new ArrayList();

    long startTime1 = System.currentTimeMillis();

    list.ensureCapacity(N);

    for (int i = 0; i < N; i++) {

    list.add(i);

    }

    long endTime1 = System.currentTimeMillis();

    System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1));

    }

    }

    复制代码

    运行结果:使用ensureCapacity方法前:1773

    复制代码

    通过运行结果,我们可以看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以减少增量重新分配的次数。

    细节

    JDK7

    JDK1.7:ArrayList像饿汉式,直接创建一个初始容量为10的数组

    JDK1.8:ArrayList像懒汉式,一开始创建一个长度为0的数组,当添加第一个元 素时再创建一个始容量为10的数组

    Arraylist 和 Vector 的区别?ArrayList 是 List 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;

    Vector 是 List 的古老实现类,底层使用 Object[ ]存储,线程安全的。(底层synchronized同步方法)

    Arraylist 与 LinkedList 区别?是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;

    底层数据结构: Arraylist 底层使用的是 Object 数组;LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)

    插入和删除是否受元素位置的影响: ① ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。

    是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

    内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

    展开全文
  • @[TOC](Java-ArrayList 扩容机制 以及 add方法 remove方法 核心代码解读)1、创建MyArrayList类public class MyArrayList {}2、构造方法先看 JDK中ArrayList的构造方法/*** Constructs an empty list with the ...

    @[TOC](Java-ArrayList 扩容机制 以及 add方法 remove方法 核心代码解读)

    1、创建MyArrayList类

    public class MyArrayList {

    }

    2、构造方法

    先看 JDK中ArrayList的构造方法

    /**

    * Constructs an empty list with the specified initial capacity.

    * 使用指定的容量长度 构造一个空list。

    *

    * @param initialCapacity the initial capacity of the list

    * @throws IllegalArgumentException if the specified initial capacity

    * is negative

    */

    public ArrayList(int initialCapacity) {

    if (initialCapacity > 0) {

    // 如果传入的初始化容量大于0 就用初始化容量初始化内部数组

    this.elementData = new Object[initialCapacity];

    } else if (initialCapacity == 0) {

    // 如果初始化容量 等于0 就使用默认的空元素数据来做初始化

    this.elementData = EMPTY_ELEMENTDATA;

    } else {

    // 其他的容量长度是不合法的

    throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);

    }

    }

    /**

    * Constructs an empty list with an initial capacity of ten.

    * 使用一个默认的初始化容量10 构造一个空list, 这应该是jdk1.8之前 会在构造函数中直接初始化内部数组 1.8之后做了修改 放到了add方法中初始化。

    * (但是好像实现中并没有在构造方法中使用默认的数组长度10来初始化内部数组,而是直接使用了DEFAULTCAPACITY_EMPTY_ELEMENTDATA )

    */

    public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    jdk 中的两个最重要的构造方法如上。

    其中有几个重要的参数

    // 内部数组

    private Object[] elementData;

    // 默认数组容量

    private static final int DEFAULT_CAPACITY = 10;

    // 用于空实例的共享空数组实例

    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 共享空数组实例,用于默认大小的空实例。我们将其与EMPTY_ELEMENTDATA区分开来,以了解添加第一个元素时应该膨胀多少。

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //ArrayList的大小(它包含的元素的数量)。

    private int size;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    参考jdk ArrayList 的构造方法 实现MyArrayList的构造方法

    // 1. 构造方法 初始化内部数组

    public MyArrayList(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. 构造方法 初始化内部数组

    public MyArrayList(){

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    2.1ArrayList最多可以存放多少个元素?

    从字段

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    可以看出来 最大值就是Integer的最大值

    Integer的范围是

    因为最左边的一位是符号位 所以剩下31位可以表达数值

    JDK源码中的写法

    /**

    * A constant holding the minimum value an {@code int} can

    * have, -231.

    */

    @Native public static final int MIN_VALUE = 0x80000000;

    /**

    * A constant holding the maximum value an {@code int} can

    * have, 231-1.

    */

    @Native public static final int MAX_VALUE = 0x7fffffff;

    3、add方法的实现

    参考JDK ArrayList add方法实现

    1.确定容量大小(这一步包含内部数组扩容机制)

    2.elementData持有传入的元素

    3.处理完成后返回true

    // 2. add方法

    public Boolean add(Object ele){

    // 2.1确定内部数组的容量大小 判断是否需要扩容(如果是默认无参数构造方法生成的对象,在第一次add的时候会初始化内部数组)

    ensureCapacityInternal(size + 1); // 这里传入的参数是 内置数组应该有的最小值

    // 保存元素到数组中

    elementData[size++] = ele;

    return true;

    }

    // 2.1 确定数组的长度

    private void ensureCapacityInternal(int minCapacity) {

    // 判断是否是使用默认无参数构造方法来创建的arraylist

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

    // 如果是的话 对比需要的最小数组长度和默认数组长度 获取到其中的最大值 作为内部数组的最小长度

    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    // 2.1.1明确数组长度

    ensureExplicitCapacity(minCapacity);

    }

    // 2.1.1明确数组长度 参数是数组应有的最小容量长度

    private void ensureExplicitCapacity(int minCapacity) {

    // overflow-conscious code

    // 如果数组需要的最小值 大于当前数组的长度 则数组需要扩容

    if (minCapacity - elementData.length > 0){

    // 2.1.1.1 数组扩容

    grow(minCapacity);

    }

    }

    // 2.1.1.1 数组扩容

    private void grow(int minCapacity) {

    // overflow-conscious code

    // 获取到 数组原长度

    int oldCapacity = elementData.length;

    // 获取到新的数组长度 (新长度 = 原长度+ 0.5*原长度) >>1 右移一位相当于除2

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 如果新长度 小于 数组应有的最小长度 的话 新长度就等于 最小长度

    // 这里 解决了 初始容量为1的arraylist 的扩容问题

    // 如果没有这个判断的话 根据上面的计算 1的扩容 newCapacity= 1+(1>>1) = 1 导致无法扩容

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    // 如果新长度 大于MAX_ARRAY_SIZE, MAX_ARRAY_SIZE这个

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    // 如果是 已经大于了MAX_ARRAY_SIZE 就赋予一个很大的值 这个条件下 会赋值Integer的最大值

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    // 这里使用了 数组copy的api 来扩容数组

    elementData = Arrays.copyOf(elementData, newCapacity);

    }

    // 获取一个极大的长度

    private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow

    throw new OutOfMemoryError();

    return (minCapacity > MAX_ARRAY_SIZE) ?

    Integer.MAX_VALUE :

    MAX_ARRAY_SIZE;

    }

    3.1、 ArrayList内置数组的扩容规则是什么?

    // 获取到 数组原长度

    int oldCapacity = elementData.length;

    // 获取到新的数组长度 (新长度 = 原长度+ 0.5*原长度) >>1 右移一位相当于除2

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    3.2、为什么ArrayList的默认长度是10?

    从这可以看出 我们初始化时的长度是2,当添加第三个元素的时候要扩容 2+(2>>1) = 3

    如果 我们在添加第四个元素的话 会再次扩容 3+(3>>1) = 5 这样的话,当我们添加第六个元素的时候又会扩容。

    从这里可以看出如果初始定义的长度比较小会造成频繁扩容。

    所以 jdk默认的长度是10.

    3.3、如果ArrayList初始化长度是1 那扩容的时候会怎么处理?

    具体看grow(int minCapacity)方法的实现。

    minCapacity = 2;

    oldCapacity = 1; newCapacity = 1+(1>>1) ;

    newCapacity = 1;

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    所以 这时候 newCapacity = 2;

    最终扩容的结果是2;

    4、get方法实现

    get方法的实现比较简单

    1.检查数组越界

    2.返回对应index的对象

    // 3. get方法

    public Object get(int index){

    // 3.1 检查是否越界

    rangeCheck(index);

    // 返回存储对应index的值

    return elementData[index];

    }

    // 3.1 检查是否越界

    private void rangeCheck(int index) {

    if (index >= size)

    // 3.1.1 输出越界情况

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    // 3.1.1 输出越界情况

    private String outOfBoundsMsg(int index) {

    return "Index: "+index+", Size: "+size;

    }

    5、remove(int index)移除元素方法实现

    根据JDK中ArrayList的remove实现 可以得到remove的处理原理

    删除的原理

    假设 ArrayList中存放 1 2 3 4 5 6

    现在remove(2)

    所以可以获取到要删除 元素 是 3

    3后面有 3个元素 4 5 6 的下标 前移一位 覆盖掉原来的3(这一步通过数组copy的方法来处理System.arraycopy)

    结果就是 1 2 4 5 6

    具体实现代码

    public Object remove(int index) {

    // 4.1 检查左边是否越界

    rangeCheck(index);

    // 4.2 获取到原来的元素

    Object oldValue = elementData[index];

    // 4.3 计算inedx后面 需要移动的元素的数量

    /*

    假设 1 2 3 4 5 6

    remove(2)

    numMoved = 6(size) - 2(index) - 1 = 3 所以后面三个元素要往前移动一个下标

    */

    // 需要移动的元素的数量

    int numMoved = size - index - 1;

    // 如果后面没有要移动的元素 就不做数组copy操作了

    if (numMoved > 0)

    // 4.4 处理数组 原数组是 elementData 从index+1开始复制 复制到 elementData 从index开始复制numMoved个元素

    // 通过这个方式 就把 elementData 的index元素用后面的元素覆盖掉了

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    // 4.5 最后 size - 1 并把size-1后指向的最后一个元素置空

    elementData[--size] = null; // clear to let GC do its work

    // 4.6 返回被删除的元素

    return oldValue;

    }

    //4.1 检查是否越界

    private void rangeCheck(int index) {

    if (index >= size)

    // 3.1.1 输出越界情况

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    6、remove(Object o)方法的实现

    根据JDK中ArrayList相关方法的实现,我们可以看出这个方法的实现是基于remove(int index) 的。

    判断参数o是不是null

    如果是null ,从index=0 开始遍历elementDate内置数组 找到null对应的index,通过index来移除null

    如果不是null,从index=0 开始遍历elementDate内置数组 找到o对应的index,通过index来移除null

    public boolean remove(Object o) {

    // 5.1 判断o是不是null

    if (o == null) {

    // 5.2如果是空的话 就会遍历删除 《《第一个》》 null 对象

    for (int index = 0; index < size; index++)

    // 判断 index 对应的元素是不是null

    if (elementData[index] == null) {

    // 5.3 快速删除index对应的对象

    fastRemove(index);

    return true;

    }

    } else {

    // 5.4 如果不是空

    for (int index = 0; index < size; index++)

    // 5.5 遍历数组

    if (o.equals(elementData[index])) {

    //5.6 如果找到第一个equals的对象 就快速删除掉

    fastRemove(index);

    return true;

    }

    }

    return false;

    }

    // 5.3/5.6 如果找到第一个equals的对象 就快速删除掉

    // 与remove(index) 方法不同的地方是:1.不做越界检查 2.不会返后被删除的数据

    private void fastRemove(int index) {

    int numMoved = size - index - 1;

    if (numMoved > 0)

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    elementData[--size] = null;

    }

    7、add(int index,Object ele) 方法的具体实现

    通过arraylist 对该方法的具体实现 可以看到具体的步骤是

    检查越界

    确定内置数组容量(包含扩容机制)

    利用System.arraycopy方法,移动数组元素

    赋值新对象到 内置数组的指定的index上

    ArrayList的size+1

    具体代码实现

    // 6. 向指定的index 添加元素

    public void add(int index, Object ele) {

    // 6.1 检查是否越界

    rangeCheckForAdd(index);

    // 6.2 确定是否需要扩容

    ensureCapacityInternal(size + 1); // Increments modCount!!

    // 6.3 复制移动数组

    /*

    已有数组 A B C D

    向 index 1 插入 M

    通过arraycopy方法 elementData从index的位置开始复制 复制到 elementData的index+1的位置 复制的长度是 4 - 1 = 3

    所以移动完之后就是 A null B C D

    */

    System.arraycopy(elementData, index, elementData, index + 1,

    size - index);

    // 6.4 赋值对象到指定的index上

    elementData[index] = ele;

    // 6.5 元素总数量+1 size+1

    size++;

    }

    // 6.1 检查是否越界

    private void rangeCheckForAdd(int index) {

    if (index > size || index < 0)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    8、全部代码实现(详细注释)

    package com.lhit.collection;

    import java.util.Arrays;

    public class MyArrayList {

    // 内部数组

    private Object[] elementData;

    // 默认数组容量

    private static final int DEFAULT_CAPACITY = 10;

    // 用于空实例的共享空数组实例

    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 共享空数组实例,用于默认大小的空实例。我们将其与EMPTY_ELEMENTDATA区分开来,以了解添加第一个元素时应该膨胀多少。

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //ArrayList的大小(它包含的元素的数量)。

    private int size;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    // 1. 构造方法 初始化内部数组

    public MyArrayList(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. 构造方法 初始化内部数组

    public MyArrayList(){

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    // 2. add方法

    public Boolean add(Object ele){

    // 2.1确定内部数组的容量大小 判断是否需要扩容(如果是默认无参数构造方法生成的对象,在第一次add的时候会初始化内部数组)

    ensureCapacityInternal(size + 1); // 这里传入的参数是这个数字应该有的最小值

    // 保存元素到数组中

    elementData[size++] = ele;

    return true;

    }

    // 3. get方法

    public Object get(int index){

    // 3.1 检查是否越界

    rangeCheck(index);

    // 返回存储对应index的值

    return elementData[index];

    }

    // 4. remove 通过index

    /*

    删除的原理

    假设 ArrayList中存放 1 2 3 4 5 6

    现在remove(2)

    所以可以获取到 元素 是 3

    3后面有 3个元素 4 5 6 的下标 前移 覆盖掉原来的3(这一步通过数组copy的方法来处理System.arraycopy)

    结果就是 1 2 4 5 6

    */

    public Object remove(int index) {

    // 4.1 检查左边是否越界

    rangeCheck(index);

    // 4.2 获取到原来的元素

    Object oldValue = elementData[index];

    // 4.3 计算inedx后面 需要移动的元素的数量

    /*

    假设 1 2 3 4 5 6

    remove(2)

    numMoved = 6(size) - 2(index) - 1 = 3 所以后面三个元素要往前移动一个下标

    */

    // 需要移动的元素的数量

    int numMoved = size - index - 1;

    // 如果后面没有要移动的元素 就不做数组copy操作了

    if (numMoved > 0)

    // 4.4 处理数组 原数组是 elementData 从index+1开始复制 复制到 elementData 从index开始复制numMoved个元素

    // 通过这个方式 就把 elementData 的index元素用后面的元素覆盖掉了

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    // 4.5 最后 size - 1 并把size-1后指向的最后一个元素置空

    elementData[--size] = null; // clear to let GC do its work

    // 4.6 返回被删除的元素

    return oldValue;

    }

    // 5. remove 通过Object元素来删除

    // 需要注意的是 如果存在相同对象 只能删除index靠前的第一个

    public boolean remove(Object o) {

    // 5.1 判断o是不是null

    if (o == null) {

    // 5.2如果是空的话 就会遍历删除 《《第一个》》 null 对象

    for (int index = 0; index < size; index++)

    // 判断 index 对应的元素是不是null

    if (elementData[index] == null) {

    // 5.3 快速删除index对应的对象

    fastRemove(index);

    return true;

    }

    } else {

    // 5.4 如果不是空

    for (int index = 0; index < size; index++)

    // 5.5 遍历数组

    if (o.equals(elementData[index])) {

    //5.6 如果找到第一个equals的对象 就快速删除掉

    fastRemove(index);

    return true;

    }

    }

    return false;

    }

    // 6. 向指定的index 添加元素

    public void add(int index, Object ele) {

    // 6.1 检查是否越界

    rangeCheckForAdd(index);

    // 6.2 确定是否需要扩容

    ensureCapacityInternal(size + 1); // Increments modCount!!

    // 6.3 复制移动数组

    /*

    已有数组 A B C D

    向 index 1 插入 M

    通过arraycopy方法 elementData从index的位置开始复制 复制到 elementData的index+1的位置 复制的长度是 4 - 1 = 3

    所以移动完之后就是 A null B C D

    */

    System.arraycopy(elementData, index, elementData, index + 1,

    size - index);

    // 6.4 赋值对象到指定的index上

    elementData[index] = ele;

    // 6.5 元素总数量+1 size+1

    size++;

    }

    // 2.1/6.2 确定数组的长度

    private void ensureCapacityInternal(int minCapacity) {

    // 判断是否是使用默认无参数构造方法来创建的arraylist

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

    // 如果是的话 对比需要的最小数组长度和默认数组长度 获取到其中的最大值 作为内部数组的最小长度

    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    // 2.1.1明确数组长度

    ensureExplicitCapacity(minCapacity);

    }

    // 2.1.1明确数组长度 参数是数组应有的最小容量长度

    private void ensureExplicitCapacity(int minCapacity) {

    // overflow-conscious code

    // 如果数组需要的最小值 大于当前数组的长度 则数组需要扩容

    if (minCapacity - elementData.length > 0){

    // 2.1.1.1 数组扩容

    grow(minCapacity);

    }

    }

    // 2.1.1.1 数组扩容

    private void grow(int minCapacity) {

    // overflow-conscious code

    // 获取到 数组原长度

    int oldCapacity = elementData.length;

    // 获取到新的数组长度 (新长度 = 原长度+ 0.5*原长度) >>1 右移一位相当于除2

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 如果新长度 小于 数组应有的最小长度 的话 新长度就等于 最小长度

    // 这里 解决了 初始容量为1的arraylist 的扩容问题

    // 如果没有这个判断的话 根据上面的计算 1的扩容 newCapacity= 1+(1>>1) = 1 导致无法扩容

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    // 如果新长度 大于MAX_ARRAY_SIZE, MAX_ARRAY_SIZE这个

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    // 如果是 已经大于了MAX_ARRAY_SIZE 就赋予一个很大的值 这个条件下 会赋值Integer的最大值

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    // 这里使用了 数组copy的api 来扩容数组

    elementData = Arrays.copyOf(elementData, newCapacity);

    // 从这可以看出 我们初始化时的长度是2,当添加第三个元素的时候要扩容 2+(2>>1) = 3

    // 如果 我们在添加第四个元素的话 会再次扩容 3+(3>>1) = 5 这样的话,当我们添加第六个元素的时候又会扩容。

    // 从这里可以看出如果初始定义的长度比较小会造成频繁扩容。所以 jdk默认的长度是10.

    // 这里如果初始化长度是1 那扩容的时候会怎么处理?

    // 具体看grow(int minCapacity)方法的实现。

    /*

    minCapacity = 2;

    oldCapacity = 1; newCapacity = 1+(1>>1) ;

    newCapacity = 1;

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    所以 这时候 newCapacity = 2;

    最终扩容的结果是2;

    */

    }

    // 3.1/4.1 检查是否越界

    private void rangeCheck(int index) {

    if (index >= size)

    // 3.1.1 输出越界情况

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    // 3.1.1 输出越界情况

    private String outOfBoundsMsg(int index) {

    return "Index: "+index+", Size: "+size;

    }

    // 5.3/5.6 如果找到第一个equals的对象 就快速删除掉

    // 与remove(index) 方法不同的地方是:1.不做越界检查 2.不会返后被删除的数据

    private void fastRemove(int index) {

    int numMoved = size - index - 1;

    if (numMoved > 0)

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    elementData[--size] = null;

    }

    // 6.1 检查是否越界

    private void rangeCheckForAdd(int index) {

    if (index > size || index < 0)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    // 获取一个极大的长度

    private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow

    throw new OutOfMemoryError();

    return (minCapacity > MAX_ARRAY_SIZE) ?

    Integer.MAX_VALUE :

    MAX_ARRAY_SIZE;

    }

    // 获取当前ArrayList的元素数量

    public int getSize() {

    return size;

    }

    }

    9、Vector的扩容机制

    这里吧jdk中的Vector中的扩容函数拿过来了

    public Vector(int initialCapacity, int capacityIncrement) {

    super();

    if (initialCapacity < 0)

    throw new IllegalArgumentException("Illegal Capacity: "+

    initialCapacity);

    this.elementData = new Object[initialCapacity];

    this.capacityIncrement = capacityIncrement;

    }

    public Vector(int initialCapacity) {

    this(initialCapacity, 0);

    }

    public Vector() {

    this(10);

    }

    capacityIncrement 参数是Vector初始化时可以指定的 默认是0

    private void grow(int minCapacity) {

    // overflow-conscious code

    int oldCapacity = elementData.length;

    // 这是是与ArrayList扩容最大的不同点

    // Vector 当默认是0的情况下 会 是2倍扩容

    // 如果初始化时指定了每次扩容的增长容量 则会按照增长量扩容

    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?

    capacityIncrement : oldCapacity);

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

    elementData = Arrays.copyOf(elementData, newCapacity);

    }

    9.1 Vector与ArrayList有什么不同?

    Vector 源码中使用synchronized关键字较多,线程安全要好于ArrayList。

    Vector与ArrayList的内置数组的扩容机制不同。默认情况下Vector是两倍扩容,ArrayList是1.5倍扩容

    9.2 Vector的扩容机制是什么样的?

    Vector在默认情况下是2倍扩容,如果在初始化时指定的每次扩容的容量,则会按照指定容量大小扩容。

    展开全文
  • 今天,来分享下 StringBuilder 与 StringBuffer 动态扩容机制。StringBuilder 与 StringBuffer 的构造方法会创建一个默认大小是 16 的字符数组。无参构造方法,如下所示。public StringBuilder() {super(16);}有参...

    今天,来分享下 StringBuilder 与 StringBuffer 动态扩容机制。

    StringBuilder 与 StringBuffer 的构造方法会创建一个默认大小是 16 的字符数组。

    无参构造方法,如下所示。

    public StringBuilder() {

    super(16);

    }

    有参构造方法,如下所示。

    public StringBuilder(String str) {

    super(str.length() + 16);

    append(str);

    }

    使用 append() 方法时,如果长度超过了字符串存储空间大小就需要进行扩容,调用 expandCapacity() 方法,尝试 将新容量扩为大小变成 2 倍 + 2,直接扩充到需要的容量大小 。

    void expandCapacity(int minimumCapacity) {

    int newCapacity = value.length * 2 + 2;

    if (newCapacity - minimumCapacity < 0)

    newCapacity = minimumCapacity;

    if (newCapacity < 0) {

    if (minimumCapacity < 0) // overflow

    throw new OutOfMemoryError();

    newCapacity = Integer.MAX_VALUE;

    }

    value = Arrays.copyOf(value, newCapacity);

    }

    总结下,StringBuilder 与 StringBuffer 的构造方法会创建一个默认大小是 16 的字符数组。使用 append() 方法时,如果长度超过了字符串存储空间大小就需要进行扩容,它会重新分配内存,创建一个更大的数组,这个数组的容量是原来的 2 倍 + 2 的大小,并将原先的数组复制过来,再丢弃旧的数组。因此,在大多数情况下,可以在创建 StringBuilder 与 StringBuffer 的时候指定大小,这样可以避免在容量不够的时候自动增长,从而提高性能。

    (完)

    展开全文
  • (1)效率:java中的数组是一种效率最高的存储和随机访问对象引用序列的方式。数组就是一个简单的线性序列,这使得元素访问非常快速。但是为这种速度所付出的代价是数组对象的大小被固定(数组的length属性),并且...
  • HashMape Capacity计算:一般我们都会调用无参的构造函数来初始话一个数组对象,所以默认的capacity是16,不用我们计算,这里的计算是 扩容时候或调用有参的构造方法,new HashMap(initail capacity: 10)这里我们给...
  • JDK8中,扩容函数transfer中有如下一段代码,如果槽内的结点为链表结点,把原链表的结点按照某位的元素是否为1,划分为两个链表,分别放置在nextTab[i]和nextTab[n+i]位置上,问题来了:代码中会将链表反序输出,...
  • ArrayList是List接口的实现类,它是支持根据需要而动态增长的数组java中标准数组是定长的...因此,了解它的扩容机制对使用它尤为重要。ArrayList扩容发生在add()方法调用的时候,下面是add()方法的源码:public b...
  • java语言来说,数组是定长的,在被创建之后就不能被加长或缩短了,因此,了解它的扩容机制对使用它尤为重要。下面,我们就一起来看看它的扩容机制是怎么实现的吧。首先我们知道,ArrayList有着三种初始化方式:1)...
  • ArrayList简介ArrayList实现了List接口,它是一个可调整大小的数组,可以用来存放各种形式的数据。它是线程非安全的,按照插入的顺序来存储数据。ArrayList的主要成员变量:private static final int DEFAULT_...
  • 二、一步一步分析 ArrayList 扩容机制 这里以无参构造函数创建的 ArrayList 为例分析: 1、先来看 add 方法 1 /** 2 * 将指定的元素追加到此列表的末尾。3 */ 4 public booleanadd(E e) {5 //添加元素之前,先调用...
  • 多线程无锁扩容的关键就是通过CAS设置sizeCtl与transferIndex变量,协调多个线程对table数组中的node进行迁移。 如何实现线程安全 那么它到底是如何实现线程安全的? 答案:采用了 CAS + synchronized 来保证并发安全...
  • java HashMap扩容机制

    2020-05-09 14:24:10
    jdk7源码: ... //扩容,并且把原来数组中的元素重新放到新数组中 resize(2 * table.length); //... } Hashmap的扩容需要满足两个条件:当前数据存储的数量(即size())大小必须大于等于阈值;当前加...
  • 动态扩容1、add(E e)方法中①ensureCapacityInternal(size+1),确保内部容量,size是添加前数组内元素的数量② elementData[size++] = e 添加元素到相应位置,元素数量加12、ensureCapacityInternal(size+1)确保内部...
  • 在说之前,给大家先普及一些小知识:》ArrayList底层是用数组来实现的》数组一旦创建后,大小就是固定的,如果超出了数组大小后,就会创建一个新的数组》接下来所谓数组扩容实质上是重新创建一个大小更大的新数组@...
  • 总结ArrayList 和Vector默认...ArrayList 默认初始容量为10,(jdk8的时候底层Object[] elementData数组初始化为{},并没有创建长度为10的数组。在add元素时才创建了10个容量。)线程不安全,查询速度快底层数据结构...
  • Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。ArrayList继承于 AbstractList,实现了 List, ...
  • 在说之前,给大家先普及一些小知识:》ArrayList底层是用数组来实现的》数组一旦创建后,大小就是固定的,如果超出了数组大小后,就会创建一个新的数组》接下来所谓数组扩容实质上是重新创建一个大小更大的新数组@...
  • 本人是工作7年的老程序员,在头条分享我对Java运用和源码、各种...上一篇文章我对ConcurrentHashMap的非常重要的put方法做了一个全面的解析,但是遗留了两个也非常重要的知识点:扩容和线程安全,接下来两篇文章就...
  • Java 7 中Hashmap扩容机制一、什么时候扩容:网上总结的会有很多,但大多都总结的不够完整或者不够准确。大多数可能值说了满足我下面条件一的情况。扩容必须满足两个条件:1、 存放新值的时候当前已有元素的个数必须...
  • Java集合的扩容机制

    2020-04-13 17:37:38
    ArrayList扩容机制,按原数组长度的1.5倍扩容。如果扩容后的大小小于实际需要的大小,将数组扩大到实际需要的大小 Vector Vector是线程安全版的ArrayList内部实现都是用数组实现的。Vector通过在方法前用syn...
  • 面试的时候闻到了Hashmap的扩容机制,之前只看到了Hasmap的实现机制,补一下基础知识,讲的非常好原文链接:Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下。网上关于hashmap...
  • 总结一:以下就是List下的三个实现类集合ArrayList 和Vector,LinkedList扩容总结:ArrayList 和Vector扩容机制总结:ArrayList 和Vector,底层都是Object数组,默认加载因子都是1(元素满了才扩展容量).默认容量都是...
  • java集合的扩容机制发布时间:2021-02-28 12:44:36总结一:以下就是List下的三个实现类集合ArrayList 和Vector,LinkedList扩容总结:ArrayList 和Vector扩容机制总结:ArrayList 和Vector,底层都是Object数组,默认...
  • 在面试中我们经常被问到说ArrayList和数组有什么不同,...下面的代码是基于JDK1.8的现在,让我们来看一下ensurecapacitanyin()方法这个方法实际上判断数组是否已经初始化,如果未初始化的话就赋值为10然后我们来剖析...
  • java集合的扩容机制

    千次阅读 2021-02-28 12:06:48
    总结 ArrayList 和Vector默认加载因子都是1(元素满了才扩展容量).默认容量都是10;但是ArrayList 在jdk1.8时默认为空,当添加元素时,才初始化为10个... 扩容增量:原容量的 0.5倍,新容量为原容量的1.5倍。  如 Ar
  • Java集合扩容机制1、ArrayList2、Vector3、Stack4、HashMap 为什么需要扩容?即当前集合能容纳的数据量达到一个饱和状态(饱和状态和加载因子有关)之后,集合需要申请新的存储空间,即扩容。 常见的需要扩容的集合...
  • 1.HashMap在什么条件下扩容...capacity:当前数组容量,始终保持 2^n,可以扩容扩容数组大小为当前的 2 倍。 loadFactor:负载因子,默认为 0.75 loadFactor加载因子是控制数组存放数据的疏密程度,loadFa...
  • HashMap的Put方法HashMap的数据结构设计可以参考链接。接下来回顾HashMap的put(Key k, Value v)过程:(1)对 Key求Hash值,计算出Hash...(2)如果没有碰撞,直接放入桶中,即Hash表数组对应位置的链表表头。(3)如果碰...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 414
精华内容 165
关键字:

java数组扩容机制

java 订阅