ArrayList源码分析

myeveryheart 发布于2019-08-19 11:03 / 2734人阅读

摘要：源码分析类的实现接口及继承父类和和都实现了接口。这个接口的作用是实现它能够支持快速随机访问。在取出值的时候利用范型转为声明的类型。如果等于则初始化为空如果小于则抛出异常。并且设置为传入的大小。常用方法解析的元素数方法很简单直接返回值的大小。

ArrayList源码分析 类的实现接口及继承父类

 public class ArrayList extends AbstractList. implements List, RandomAccess, Cloneable, java.io.Serializable

AbstractList 和 List

ArrayList 和AbstractList 都实现了List接口。
并且AbstractList是ArrayList的父类。

RandomAccess

RandomAccess接口里没有方法需要实现。这是一个很特别的空接口。这个接口的作用是：

List实现它能够支持快速随机访问。主要能提高随机访问的性能。
 for (int i=0, n=list.size(); i < n; i++)
    list.get(i);
比下面这种快。
for (Iterator i=list.iterator();i.hasNext(); )
    i.next();

Cloneable

此接口也是一个空接口，实现次接口，需要重写object对象的clone()方法，并且方法是访问权限是public的。

clone()是值拷贝，即为浅拷贝。

测试是否为浅拷贝：

拷贝对象：

package xuelongjiang.ArrayListCloneTest;

/**
 * @author xuelongjiang
 */
public class User {

private String name ;

private Integer sex;

public User() {
}

public User(String name, Integer sex) {
    this.name = name;
    this.sex = sex;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public Integer getSex() {
    return sex;
}

public void setSex(Integer sex) {
    this.sex = sex;
}


@Override
public String toString() {
    return "User{" +
            "name="" + name + """ +
            ", sex=" + sex +
                    "//
" +
            getClass().getName() + "@" + Integer.toHexString(hashCode())+
            "}";
}

}

测试类：

package xuelongjiang.ArrayListCloneTest;


import java.util.ArrayList;
import java.util.List;

/**
 *
 * 结论： clone 是浅拷贝 值相同，对象的引用相同
 * @author xuelongjiang
 */
public class CloneObject {


public static void main(String[] args) {


    ArrayList userList = new ArrayList<>();
    userList.add(new User("xue",1));
    userList.add(new User("lisi",2));

    System.out.println("------------原始值-------------");
    for(User user : userList){
        System.out.println(user);
    }


    List cloneList  = (List) userList.clone();
    System.out.println("------------拷贝值-------------");
    for(User user : cloneList){
        System.out.println(user);
    }


}

}

输出：

------------原始值-------------
User{name="xue", sex=1//
xuelongjiang.ArrayListCloneTest.User@2d98a335}
User{name="lisi", sex=2//
xuelongjiang.ArrayListCloneTest.User@16b98e56}
------------拷贝值-------------
User{name="xue", sex=1//
xuelongjiang.ArrayListCloneTest.User@2d98a335}
User{name="lisi", sex=2//
xuelongjiang.ArrayListCloneTest.User@16b98e56}

实现ArrayList的容器

ArrayList的底层实现为数组。

 transient Object[] elementData;

从上面我们可以看出数组为obejct。在取出值的时候利用范型转为声明的类型。

构造方法

ArrayList 有三个构造方法

第一种构造方法：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

如果使用无参的构造方法，则初始化的数组为空（注意不为null）。

第二种构造方法

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);
}
}

如果初始化的容器值大于0，则初始化为这个值。如果等于0 则初始化为空

 private static final Object[] EMPTY_ELEMENTDATA = {};

如果小于0则抛出异常。

第三种构造方法：

    public ArrayList(Collection 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;
}
}

由于ArrayList的底层实现是Object[] 需要把Collection转为Object[]。并且设置size为传入的Collection大小。

常用方法解析 size() list的元素数

size方法很简单直接返回size值的大小。

private int size;

public int size() {
    return size;
}

add()

在add方法中会对elemenrData进行扩容，如果不需要扩容或者扩容完成了，就把需要添加的元素放入elementData中，并且size自增。

public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

在ensureCapacityInternal中如果容器为空，比较需要扩容的大小和DEFAULT_CAPACITY(= 10)
如果大于DEFAULT_CAPACITY，则使用本次传入的否则设置容量为DEFAULT_CAPACITY。

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

ensureExplicitCapacity方法:

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

如果本次需要的扩容大于elementData的长度，则调用grow方法扩容。

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//1
int newCapacity = oldCapacity + (oldCapacity >> 1);//2
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;//3
if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);//4
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//5
}

获取当前容器的大小

计算新的扩容大小：扩容1.5倍

如果默认扩容小于本次需要扩容的大小，则设置为本次需要的扩容大小，否则设为默认扩容

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

     public static final int   MAX_VALUE = 0x7fffffff;//2的31次方，大于20多亿

如果本次需要的扩容大于MAX_ARRAY_SIZE，则容器设置为Integer.MAX_VALUE，如果等于MAX_ARRAY_SIZE则设为MAX_ARRAY_SIZE。

拷贝生成扩容后的容器

remove()

    public E remove(int index) {
    rangeCheck(index);//1
       modCount++;
       E oldValue = elementData(index);//2

            int numMoved = size - index - 1;//3
        if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);//4
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
    }

移除元素后，需要把它之后的虽有元素向前移动1位。

检查索引是否超出范围

返回被移除的元素

需要向前移动的元素数

移动元素：拷贝

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;
}

循环容器判断每一个元素是否和目标值相等。
**注意：如果是对象的话这里比较的对象的引用，在开发中很多时候我们要比较的实体，实体映射的是数据库里的一条记录，比较的其实是主键是否相等，所以如果
是这种情况需要重写equal方法及hashCode方法**

clear()

public void clear() {
modCount++;

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

size = 0;
}

把容器中的每个元素的值设为null，之后垃圾回收机制会收回被使用的内存。

迭代器

java5之后，集合框架可以使用迭代器，并且提供了foreach语法糖。

public Iterator iterator() {
return new Itr();
}

public E next()
public boolean hasNext()

迭代器模式：https://blog.csdn.net/u013565...

开发中的易犯错误

https://blog.csdn.net/u013565...

关注我的公众号第一时间阅读有趣的技术故事
扫码关注：

也可以在微信搜索公众号即可关注我：codexiulian
渴望与你一起成长进步！

云服务器海外云主机 ArrayList源码源码分析 nginx源码分析 webrtc源码分析

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76916.html

Java集合源码分析系列-（一）ArrayList源码剖析

摘要：需要注意的是，通过构造函数定义初始量是动态数组的实际大小。带容量的构造函数新建一个容量为的数组默认构造函数，默认为空构造一个包含指定元素的第一个构造方法使用提供的来初始化数组的大小。前言今天介绍经常使用的一个Java集合类——ArrayList（基于JDK1.8.0_121）。ArrayList在工作和日常面试中经常被使用或者提到。总的来说，工作中使用ArrayList主要是因为动...

Miyang 2019-08-15 12:00 评论0 收藏0
ArrayList源码和多线程安全问题分析

摘要：源码和多线程安全问题分析在分析线程安全问题之前，我们线对此类的源码进行分析，找出可能出现线程安全问题的地方，然后代码进行验证和分析。即当多线程调用方法的时候会出现元素覆盖的问题。 1.ArrayList源码和多线程安全问题分析在分析ArrayList线程安全问题之前，我们线对此类的源码进行分析，找出可能出现线程安全问题的地方，然后代码进行验证和分析。 1.1 数据结构 ArrayLi...

genedna 2019-08-15 11:58 评论0 收藏0
JDK1.8 ArrayList部分源码分析小记

摘要：部分源码分析小记底层数据结构底层的数据结构就是数组，数组元素类型为类型，即可以存放所有类型数据。初始容量大于初始化元素数组新建一个数组初始容量为为空对象数组初始容量小于，抛出异常无参构造函数。 JDK1.8 ArrayList部分源码分析小记底层数据结构底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都...

王军 2019-08-15 11:56 评论0 收藏0
ArrayList源码分析

摘要：表明该类具有序列化功能。关键属性默认初始容量大小指定该容量为时，返回该空数组。构造一个包含指定的元素的列表，这些元素是按照该的迭代器返回它们的顺序排列的。对扩容后的容量进行判断，如果大于允许的最大容量，则将容量再次调整为。总览 showImg(https://segmentfault.com/img/bVbsm9v?w=1232&h=643); 底层：ArrayList底层是一个数...

boredream 2019-08-16 17:15 评论0 收藏0
Vector源码分析（对比ArrayList）

摘要：同步众所周知，是同步的而不是，在一些必要的方法上都加了关键字，但是这也会加大系统开销。中有一个方法用来返回一个，以匿名内部类的方式实现的接口和类似，都用作于对集合进行迭代，不过没有删除功能，已经被取代。还有是的，但不是，这一点很重要。在上篇文章ArrayList源码浅析中分析了一下 ArrayList的源码和一些重要方法，现在对比 ArrayList，总结一下 Vector和 Arr...

wall2flower 2019-08-14 12:23 评论0 收藏0