百度360必应搜狗淘宝本站头条
nodejsbufferorg.jsoupsetnocountoncv2.bitwise_nottime.strptime
当前位置：网站首页 > 编程字典 > 正文

ArrayList全面详解(看这篇就够了)

toyiye 2024-06-21 12:05 8 浏览 0 评论

ArrayList属于Java集合框架最常用的集合，本篇会详解ArrayList的使用与源码 @mikechen

ArrayList的定义

ArrayList 是 java 集合框架中比较常用的数据结构了，实现了 List 接口。


ArrayList相当于动态数组，与Java中的数组相比，它的容量能动态增长。

ArrayList的特点

  • 允许插入重复的元素
  • 插入的元素是有序的
  • 动态扩容
  • 非线程安全
  • 基于动态数组的数据结构
  • 擅长随机访问(get set)

ArrayList的成员变量

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {


// 实际元素个数
private int size; 


// 存放的元素集合
transient Object[] elementData; 


// 默认初始大小10
private  static  final  int DEFAULT_CAPACITY = 10; 


//记录对List操作的次数,主要使用在Iterator中,防止迭代过程中集合被修改
protected  transient  int modCount = 0; 




// 下面两个变量用在构造函数中,判断第一次添加元素时知道从空的构造函数还是有参构造函数被初始化的
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


    // ...
}

ArrayList的构造函数

1. 无参数构造

//无参数的构造方法
    public ArrayList() {
        //此时 elementData为{}
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

构造一个初始容量为10的空的list集合,但构造函数只是给elementData赋值了一个空的数组,其实是在第一次添加元素时扩大至10。

2.有参构造函数

/**
* Constructs an empty list with the specified initial capacity.
*
* @param  initialCapacity  the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
*         is negative
*/
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);
    }
}

只要保证传递参数值 不 < o，即可，小于 0，会抛异常。

3.集合参数构造函数

 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray(); //转为数组
        if ((size = elementData.length) != 0) { //集合大小不等于0
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)//集合类型不是Object类型
                elementData = Arrays.copyOf(elementData, size, Object[].class);//复制
        } else {//集合大小为0，指定一个空数组
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList的API

// Collection中定义的API
boolean             add(E object)
boolean             addAll(Collection<? extends E> collection)
void                clear()
boolean             contains(Object object)
boolean             containsAll(Collection<?> collection)
boolean             equals(Object object)
int                 hashCode()
boolean             isEmpty()
Iterator<E>         iterator()
boolean             remove(Object object)
boolean             removeAll(Collection<?> collection)
boolean             retainAll(Collection<?> collection)
int                 size()
<T> T[]             toArray(T[] array)
Object[]            toArray()
// AbstractCollection中定义的API
void                add(int location, E object)
boolean             addAll(int location, Collection<? extends E> collection)
E                   get(int location)
int                 indexOf(Object object)
int                 lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
ListIterator<E>     listIterator()
E                   remove(int location)
E                   set(int location, E object)
List<E>             subList(int start, int end)
// ArrayList新增的API
Object               clone()
void                 ensureCapacity(int minimumCapacity)
void                 trimToSize()
void                 removeRange(int fromIndex, int toIndex)

ArrayList主要方法解析

1.add增加

 public boolean add(E e) {//添加一个元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e; //长度+1
        return true; //返回boolean 类型
    }
    
    public void add(int index, E element) {//指定索引位置添加一个元素
        rangeCheckForAdd(index);//检查集合长度级索引大小




        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//复制
        elementData[index] = element; //元素放到集合指定索引的位置
        size++;//长度+1
    }




    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//默认长度10
    }



    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//记录修改次数


           //
        if (minCapacity - elementData.length > 0)//传入长度大于当前长度，扩容
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//老容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);//老容量+ 老容量/2
        if (newCapacity - minCapacity < 0)// 新容量 小于参数传入容量,修改新容量
            newCapacity = minCapacity;
        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);//扩容拷贝
    }



    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow 传入容量 < 0 抛异常
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

添加元素时，会指定默认为10的容量，当添加元素导致集合容量大于10，触发扩容机制，扩容为原来的1.5倍。

2.remove移除

   public E remove(int index) {
        //校验删除位置是否合理
        rangeCheck(index);
      // 同add理由一样
        modCount++;
       // 保存待删除元素
        E oldValue = elementData(index);
        // 判断删除位置：如果>0不在尾部需要调用System.arraycopy，否则在尾部直接删除
        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;
    }

当我们调用 remove(int index) 时，首先会检查 index 是否合法，然后再判断要删除的元素是否位于数组的最后一个位置。

如果 index 不是最后一个，就再次调用 System.arraycopy() 方法拷贝数组。

如果 index 是最后一个元素那么就直接将数组的最后一个位置空，size - 1即可。

3.get获取

    public E get(int index) { //获取指定索引的值
        rangeCheck(index);//是否越界

        return elementData(index);//返回指定下标的值
    }
    private void rangeCheck(int index) {
        if (index >= size) //索引大于 集合长度，抛异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

由于ArrayList底层是基于数组实现的,所以获取元素就相当简单了,直接调用数组随机访问即可。

4.set修改

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }}

修改指定位置的元素为新元素，首先需要校验给定index的值，index必须大于等于0，小于size，然后将新元素保存到index位置，并将旧元素返回。

5.扩容操作

public void ensureCapacity(int minCapacity) {
        //修改计时器
        modCount++;
        //ArrayList容量大小
        int oldCapacity = elementData.length;
        /*
         * 若当前需要的长度大于当前数组的长度时，进行扩容操作
         */
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            //计算新的容量大小，为当前容量的1.5倍
            int newCapacity = (oldCapacity * 3) / 2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            //数组拷贝，生成新的数组
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

ensureCapacityInternal方法的目的是确保给定的参数指定的容量值。

真正的扩容逻辑位于grow方法中：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);// 扩容为原容量的1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果最后决定扩容的容量比允许的最大数组容量值要大，那么则进行超限处理
        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为负数（首位为1）则抛出异常错误OutOfMemoryError
    // 如果给定容量大于数组最大容量，则取整数的最大值为容量，否则使用数组的最大容量作为扩容容量
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }}

ensureCapacity()，该方法就是ArrayList的扩容方法，每次扩容处理会是1.5倍。

1.5倍的扩容是最好的倍数，因为一次性扩容太大(例如2.5倍)可能会浪费更多的内存(1.5倍最多浪费33%，而2.5被最多会浪费60%，3.5倍则会浪费71%……)。

但是一次性扩容太小，需要多次对数组重新分配内存，对性能消耗比较严重。

所以1.5倍刚刚好，既能满足性能需求，也不会造成很大的内存消耗。

Fail-Fast机制

在我们每次操作集合的时候，都会记录一个修改次数。

modCount++ 其实他就是fail-fast机制，它是Java集合的一种错误检测机制。

当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

ArrayList总结

最后做一下总结，知识点归纳：

  • ArrayList底层采用数组实现，拥有快速随机访问能力，但是非线程安全的集合。
  • ArrayList默认容量为10，扩容规则为当要保存的新元素所需的容量不足时触发。
  • 扩容机制为首先扩容为原始容量的 1.5 倍。
  • 扩容之后是通过数组的拷贝来确保元素的准确性的，所以尽可能减少扩容操作。
  • 如果在遍历的时候发生结构性变化，会触发ConcurrentModificationException异常。
  • 结构性变化包括：添加新元素，删除元素。

更多架构技术干货，私信【架构】即可查看我原创的300期+BAT架构技术系列文章与1000+大厂面试题答案合集。

相关推荐

Python第三课3. Python 的非正式介绍

3.Python的非正式介绍?在下面的例子中，通过提示符(>>>与...)的出现与否来区分输入和输出：如果你想复现这些例子，当提示符出现后，你必须在提示符后键入例子中的每...

如何使用 Python 构建一个“谷歌搜索”系统?| 内附代码

来源|hackernoon编译|武明利，责编|Carol出品|AI科技大本营（ID:rgznai100）在这篇文章中，我将向您展示如何使用Python构建自己的答案查找系统。基本上，这...

Python 模拟微博登陆，亲测有效!（如何用python爬微博）

今天想做一个微博爬个人页面的工具，满足一些不可告人的秘密。那么首先就要做那件必做之事！模拟登陆……代码是参考了：https://www.douban.com/note/201767245/，我对代码进...

Python 驱动的 AI 艺术批量创作: 免费的Bing 绘图代码解析

这篇文章将深入分析一段Python代码，该代码利用Bing的AI绘图功能，即bing的images/create，根据用户提供的文本提示生成图像。我们将详细探讨其工作原理、代码结构、...

Python爬虫Scrapy库的使用入门?（python scrapy爬虫）

Scrapy是一个开源的并且支持高度可扩展的Python爬虫框架，主要被用来实现从网站提取数据。出现之初就是为网页抓取而设计，但是现在它也可以被用于从APIs中抓取数据或通用的Web抓取任务。Sc...

Python3 标准库概览（python标准库有什么）

操作系统接口os模块提供了不少与操作系统相关联的函数。>>>importos>>>os.getcwd()#返回当前的工作目录'C:\\Python34...

零基础入门学习Python(三):变量和字符串

分享兴趣，传播快乐，增长见闻，留下美好！亲爱的您，这里是LearningYard新学苑。今天小编为大家带来的是...

Python读写docx文件（python读写word）

Python读写docx文件Python读写word文档有现成的库可以处理pipinstallpython-docx安装一下。https://python-docx.readthedocs.io/...

如何利用Xpath抓取京东网商品信息

前几小编分别利用Python正则表达式和BeautifulSoup爬取了京东网商品信息，今天小编利用Xpath来为大家演示一下如何实现京东商品信息的精准匹配~~HTML文件其实就是由一组尖括号构成的标...

如何利用Xpath选择器抓取京东网商品信息

前几小编分别利用Python正则表达式和BeautifulSoup爬取了京东网商品信息，今天小编利用Xpath来为大家演示一下如何实现京东商品信息的精准匹配~~HTML文件其实就是由一组尖括号构成的标...

python之Scrapy爬虫案例:豆瓣（python爬虫书籍豆瓣评分）

python模块之Scrapy爬虫框架...

Python编程入门学习:最常见加密方式和Python实现

前言我们所说的加密方式，都是对二进制编码的格式进行加密的，对应到Python中，则是我们的Bytes。所以当我们在Python中进行加密操作的时候，要确保我们操作的是Bytes，否则就会报错。将字符串...

一日一技:Python中的string.rindex()方法

string.rindex（）方法string.rindex（）方法返回字符串内子字符串的最高索引（如果找到）。如果未找到子字符串，则会引发异常。rindex（）的语法为：...

Asterisk-ARI对通道中的DTMF事件处理

Asterisk通道中关于DTMF处理是一个非常重要的功能。通过DTMF可以实现很多的业务处理。现在我们介绍一下关于ARI对通道中的DTMF处理，我们通过自动话务员实例来说明Asterisk如何创建一...

PyQt5 初次使用（pyqt5下载官网）

本篇文章默认已安装Python3，本篇文章默认使用虚拟环境。安装pipinstallPyQt5PyQt一些图形界面开发工具QtDesigner、国际化翻译工具Liguist需要另外...

取消回复欢迎 你 发表评论:

请填写验证码
一周热门
最近发表
标签列表