ArrayList-追根问底

ArrayList的基本原理

在Eclipse中按着ctrl键鼠标点击ArrayList,打开源代码。

1.new ArrayList()原理

List list = new ArrayList();

List list2 = new ArrayList(10);

源代码(抽取如下):

package test;
public class ArrayList{
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定义一个空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};//定义一个空数组
    transient Object[] elementData;//定义一个数组
    //initialCapacity是定义集合的大小
    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);
            }
     }
    
     public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
     }
        
    
}

解释:首先我们可以看到2个ArrayList构造方法,一个无参构造器,一个有参构造器。
无参构造器:为elementData这个对象数组赋了一个空值,也就是建立了一个空数组
有参构造器:传入集合大小,如果大于0,则创建一个有初始大小的数组;如果等于0,则创建一个空数组;如果小于0,则抛出异常。

2.add()背后的原理

list.add(E e);

在ArrayList源文件中,使用快捷键ctrl+o,找到add(E e)并点击

源代码:

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

解释:首先可以看到返回的是boolean值。当我们添加一个元素时先执行ensureCapacityInternal(size + 1),然后执行elementData[size] = e,最后size进行自增运算。这里就是list.size()方法所获取的返回值,而这个返回值代表的是集合中添加的元素个数,而不是集合的大小。现在我们来看第一行代码所代表的意思:

ensureCapacityInternal(size + 1);

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

    ensureExplicitCapacity(minCapacity);
}

解释:这个方法传入了一个参数(size+1),就是我们添加的所有元素的个数。此时如果数组elementData为空,则选取DEFAULT_CAPACITY和(size+1)中的最大值。那么DEFAULT_CAPACITY又是多少呢?按下ctrl键,点击这个变量,可以看到:

 private static final int DEFAULT_CAPACITY = 10;

不错,是10。也就是说,如果我们传入的(size+1),也就是我们添加的元素的总个数小于10的话,那么集合会自动将自己的大小设置为10,但是此时集合中的元素还是(size+1)个,相当于:

List list = new ArrayList(10);//此时elementData.length的值为0,而集合大小为10

如果(size+1)大于10的话,就相当于:

List list = new ArrayList(size+1);//此时elementData.length的值为size+1,而集合长度是(size+1)的1.5倍

下面再看一下最后一行代码:

ensureExplicitCapacity(minCapacity);

源代码:

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

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

解释:首先也是讲我们之前获取的minCapacity这个参数传进来。modCount是我们操作的次数,这个不用管。看后面,此时假设elementData.length的值为1的话,minCapacity为10,明显大于elementData数组长度,会执行grow方法,下面我们看grow方法:

grow(int)

 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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,此时,并创建了一个变量oldCapacity,其值为数组长度1或10,并对其增加自身的一半,赋值给newCapacity,如果newCapacity小于传入的数,就将集合大小设为minCapacity,如果newCapacity大于集合所能存储的最大值,就将集合大小设置为最大值,最后复制一个新的数组。就实现了数组大小的扩展。

3.size()背后的原理

list.size()

 public int size() {
    return size;
}

解释: 可以看到这里直接返回一个int类型的size,就是我们刚才的那个size

注意:
1. 从源码可以看出,在第一次向集合中添加元素的时候,集合大小就变为10了
2. 默认长度扩展是自身长度的50%
3. 以上写的数组其实也是集合,不必纠结

总结:整体上代码很多但其实就完成了2个功能:

1.通过add(E e)这个方法添加元素

2. 通过以下三个方法对集合(数组)扩展

ensureCapacityInternal(int minCapacity)//获取集合的size
ensureExplicitCapacity(int minCapacity)//判断size是否超出集合大小
grow(int minCapacity)//扩展集合
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,456评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,370评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,337评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,583评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,596评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,572评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,936评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,595评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,850评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,371评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,951评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2 342

推荐阅读更多精彩内容