ArrayList源码阅读

采用数组方式存储数据,可以添加null元素,此数组元素数大于实际存储的数据以便增加插入元素,都允许直接序号索引元素,但是插入数据要涉及到数组元素移动等内存操作,所以插入数据慢,查找有下标,所以查询数据快

看了这几篇文章,一个系列的,讲的非常好,感谢作者,下面我只进行一些要点的补充以及总结。

https://zhuanlan.zhihu.com/p/27873515
https://zhuanlan.zhihu.com/p/27878015
https://zhuanlan.zhihu.com/p/27938717
https://zhuanlan.zhihu.com/p/28016098

ArrayList是线程不安全的,相比于Vector,Vector在真正操作数据的函数都需要加入synchronized关键字

ArrayList的缓存:

主要是利用static和final的变量特性,不需要我们new,JVM会提前初始化好,并且static变量只有唯一一份,无论多少该类有多少个对象,因而,每次使用ArrayList的无参构造函数new新的对象,作者为了避免我们反复的创建无用数组,所有新new出来的ArrayList底层数组都指向缓存在方法区里的Object[]数组,其实是指向了最根本的DEFAULTCAPACITY_EMPTY_ELEMENTDATA静态数组。

ArrayList允许存在null元素

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

比如其indexOf方法,只要在size范围内,如果存在即可

ArrayList的add(E e):

先确保容量,使用ensureCapacityInternal(),默认容量DEFAULT_CAPACITY为10,不得不上图

1.jpg

2.jpg

这里,grow方法,ArrayList的数组拓展为原数组的1.5倍(使用length,size表示实际的元素有多少个,length是数组带有的属性)。

稍微提一下,这里利用到了Arrays的copyOf方法,其底层实现有native关键字,表示是非java语言实现的,因而,如果有数组拷贝,建议使用java自带的此方法

ArrayList的add(int index, E element):

判断下标是否合法,先确保容量,再将index及其后的元素往后复制,再插入

主要关注时间复杂度:如果我们不指定位置直接添加元素时(add(E element)),元素会默认会添加在最后,不会触发底层数组的复制,不考虑底层数组自动扩容的话,时间复杂度为O(1) ,在指定位置添加元素(add(int index, E element)),需要复制底层数组,根据最坏打算,时间复杂度是O(n)。

add()都需要考虑确保容量问题

EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别:

DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA数组的区别在于当第一个元素被加入进来的时候它知道如何扩张;可以看到在无参构造函数中,代码

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

在这里其实是构造了一个初始容量为 10 的空列表,为何?看add函数便知,在源码中函数add(E e)中的第一行代码中的所在的函数就是这句话的实现,当中调用ensureCapacityInternal,代码在此处确定了容量至少为10(即默认容量)

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

==其实依旧不是很明白,有大神知否?==

ArryList的remove():

有两种形式

  • remove(int index)——检查下标合法,进行元素删除,并且拷贝后面的元素覆盖,将最后一个元素置为null
  • remove(Object o)——先判断o是否为空,在size范围内如果有空,fastRemove后返回true,如果不为空,使用equals判断,其他情况返回false。注意:使用此方法进行删除元素,一般需要重写equals

最终,remove都只是将elementData[i]=null,clear也是一样,但clear需要遍历每一个元素赋值为null,而不是直接将elementData=null

时间复杂度:如果底层数组长度为n,当我们用下标方式去删除元素时,如果删除的是最后一个元素,不会触发数组底层的复制,时间复杂度为O(1)。如果删除第i的元素,会触发底层数组复制n-i次,根据最坏情况,时间复杂度为O(n)。

fastRemove其实只是将代码提取出来,做了拷贝工作而已(在ArrayList中,fastRemove只是给remove方法使用)

ArrayList的RangeCheck():

应用于一下几个函数(add函数使用rangeCheckForAdd)

  • get(int index)
  • set(int index, E element)
  • remove(int index)

比较需要关注的,在RangeCheck里面,没有检查index是否<0,因为这些方法在调用了rangeCheck()方法后,会马上调用elementData(int index)方法来获取指定位置元素的值。(个人表示不咋理解为啥要这么弄,有理解的朋友麻烦讲讲?)这两个方法调用保证了0 < index < size()

ArrayList的get()和set():

由于是数组,底层数组存/取元素效率非常的高,时间复杂度是O(1)

clone()

实现clone()需要有Cloneable接口,否则抛出CloneNotSupportedException,ArrayList的clone只是浅复制,也就是引用的元素本身是跟原本同样的

ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;

ArrayList的优劣势:

下标的标索引、存/取快

查找(非下标查询),插入和删除元素效率似乎不太高,时间复杂度为O(n),尤其是在有大量数据的时候。

插入和删除元素效率->找LinkedList
查找元素效率不高->找HashMap

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

推荐阅读更多精彩内容