文档章节

数据结构--ArrayList源码摘要

颓废的幻想者
 颓废的幻想者
发布于 2016/06/06 15:02
字数 481
阅读 34
收藏 0

ArrayList源码


public class ArrayList<E> extends AbstractList<E>  
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
{  
    ......  
  
    /** 
     * The array buffer into which the elements of the ArrayList are stored. 
     * The capacity of the ArrayList is the length of this array buffer. 
     */  
    private transient E[] elementData;  
  
  
    /** 
     * The size of the ArrayList (the number of elements it contains). 
     * 
     * @serial 
     */  
    private int size;  
   ......  
}  

ArrayList 的底层最重要的两个属性:Object 数组和 size 属性。

 ArrayList 的底层数组的调整

add方法--ArrayList源码摘要:


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

ensureCapacity方法--ArrayList源码摘要:

public void ensureCapacity(int minCapacity) {  
    modCount++;  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {  
        Object oldData[] = elementData;  
        int newCapacity = (oldCapacity * 3)/2 + 1;  
        if (newCapacity < minCapacity) 
            newCapacity = minCapacity;
    }
    elementData = (E[])new Object[newCapacity];  
    System.arraycopy(oldData, 0, elementData, 0, size);  
} 

结论:

  a. ArrayList 是通过将底层 Object 数组复制的方式(System.arraycopy方法)来处理数组的增长;

  b. 当ArrayList 的容量不足时,其扩充容量的方式:先将容量扩充至当前容量的1.5倍,若还不够,则将容量扩充至当前需要的数量。

顺便看看 remove 方法

remove 方法--ArrayList源码摘要:


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

fastRemove 方法--ArrayList源码摘要:


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; // Let gc do its work  
}  

private void fastRemove(int index) 可见,ArrayList 的元素移除后,也是通过 Object 数组复制的方式(System.arraycopy方法)来处理数组的变化; size 总是记录着当前的数组元素的数量。

这也就解释了 ArrayList 的特点:增加、删除和移动元素的效率低(数组复制过程消耗资源较多); 而查找元素和更新元素的效率高。

get 方法--ArrayList 源码摘要:


public E get(int index) {  
    RangeCheck(index);  
    return elementData[index];  
}  

set 方法--ArrayList 源码摘要:

   public E set(int index, E element) {  
        RangeCheck(index);  
        E oldValue = elementData[index];  
        elementData[index] = element;  
        return oldValue;  
   } 

 

本文转载自:http://kakajw.iteye.com/blog/1562025

颓废的幻想者
粉丝 30
博文 62
码字总数 18405
作品 0
南京
程序员
私信 提问
数据结构与算法-线性表ArrayList源码分析

前言 ArrayList继承了AbstractList,实现了List。ArrayList在工作中经常用到,所以要弄懂这个类是极其重要的。 构造图如下: 蓝色线条:继承 绿色线条:接口实现 image.png 正文 ArrayList简介...

小朱v
2017/12/29
0
0
ArrayList源码分析

java中的数据结构源码分析的系列文章: ArrayList源码分析 LinkedList源码分析 一、简述 我们知道,数据结构中有两种存储结构,分别是:顺序存储结构(线性表)、链式存储结构(链表),在j...

CSDN_LQR
2017/11/08
0
0
集合系列开篇:为什么要学集合?

集合可以说是学习 Java 中最重要的一块知识点了,无论做任何业务系统,集合总是最为基础的那块 API。我第一次接触集合,是在我大三的时候,那时候去面试,面试官问我:你了解过集合吗?可惜那...

陈树义
08/23
0
0
java中List接口的实现类 ArrayList,LinkedList,Vector 的区别 list实现类源码分析

java面试中经常被问到list常用的类以及内部实现机制,平时开发也经常用到list集合类,因此做一个源码级别的分析和比较之间的差异。 首先看一下List接口的的继承关系: list接口继承Collectio...

分享达人
2016/03/13
0
0
LinkedList VS ArrayList

List,根据名字我们知道是有序的元素集合。先贴一张集合的关系图。这里我们分析LinkedList与ArrayList。 Collection结构 LinkedList与ArrayList 它们都实现了List接口。但是内部实现上有些区...

Real_man
2018/03/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

UAVStack功能上新:新增JVM监控分析工具

UAVStack推出的JVM监控分析工具提供基于页面的展现方式,以图形化的方式展示采集到的监控数据;同时提供JVM基本参数获取、内存dump、线程分析、内存分配采样和热点方法分析等功能。 引言 作为...

宜信技术学院
14分钟前
3
0
MySQL的5种时间类型的比较

日期时间类型 占用空间 日期格式 最小值 最大值 零值表示 DATETIME 8 bytes YYYY-MM-DD HH:MM:SS 1000-01-01 00:00:00 9999-12-31 23:59:59 0000-00-00 00:00:00 TIMESTAMP 4 bytes YYYY-MM......

物种起源-达尔文
21分钟前
4
0
云服务OpenAPI的7大挑战,架构师如何应对?

阿里妹导读:API 是模块或者子系统之间交互的接口定义。好的系统架构离不开好的 API 设计,而一个设计不够完善的 API 则注定会导致系统的后续发展和维护非常困难。比较好的API设计样板可以参...

阿里云官方博客
25分钟前
2
0
Rancher + VMware PKS实现全球数百站点的边缘K8S集群管理

Sovereign Systems是一家成立于2007年的技术咨询公司,帮助客户将传统数据中心技术和应用程序转换为更高效的、基于云的技术平台,以更好地应对业务挑战。曾连续3年提名CRN,并且在2012年到2...

RancherLabs
29分钟前
4
0
6、根据坐标,判断该坐标是否在地图区域范围内

最近在写配送区域相关的代码,具体需求如下: 根据腾讯地图划分配送区域,总站下边设多个配送分站,然后将订单中的收货地址将其分配给不同的配送分站。 1、地图区域划分(腾讯地图) 1.1、H...

有一个小阿飞
31分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部