从源码分析java集合类原理(1)-ArrayList原理分析

ArrayList是一个使用频率极高的集合类,比如数据库查询返回多条数据的时候都会使用ArrayList来保存数据,ArrayList的底层数据结构其实就是一个数组,数组元素的类型为Object类型,对ArrayList的所有操作底层都是基于数组的。



我们先从构造函数入手,ArrayList共有三个构造函数,下面我们来分别对这三个构造函数进行一个详细的分析。

(1)、带初始容量构造函数。此构造函数指定了ArrayList初始容量initialCapacity,也就是数组大小,如果容量大于0,则初始化一个大小为initialCapacity的object数组,此数组也是后续ArrayList操作的基础;如果initialCapacity等于0,则初始化一个空数组;如果initialCapacity小于0则抛异常。


带初始容量构造函数

(2)、无参构造函数。此构造函数没有任何入参,默认创建一个空数组。


无参构造函数

(3)、带集合类构造函数。 此构造函数入参为一个Collection类,将指定的Collection类的元素放入到ArrayList中,从源码可以看到,其实原理非常简单,就是用到Collection的toArray()方法。


带集合类构造函数



分析完ArrayList的构造函数之后,我们再来看对数据元素的一些操作。

(1)、直接添加元素。上面我们讲到,ArrayList的底层数据结构就是一个数组,而数组的大小一经定义就无法改变,那么我们向ArrayList添加数据的时候就会有一个问题,数组的容量是否还能继续添加新数据,如果数组已经满了,该如何处理。围绕着这个问题,我们继续看源码


添加元素

从源码可以看到,在添加数据之前首先会去进行一个扩容的操作判断,然后将添加的元素放到最后的位置。这里最重要也是最关键的步骤就是扩容,这个也是很多面试的时候面试官会问到的地方,这个地方搞懂了,理解ArrayList的原理也差不多八九不离十了。


判断是否需要扩容


扩容

当数组放置元素的位置大于数组长度的时候,此时数组没有多余位置继续添加数据,必须对数组进行扩容,才能继续添加数据,那么具体怎么扩容呢?扩容多少呢?看源码int newCapacity = oldCapacity + (oldCapacity >> 1);结果就是扩大为原来容量的1.5倍,然后在通过Arrays.copyOf()方法创建一个新容量的数组对象。这样看是不是很容易就理解了ArrayList的扩容机制了呢。

(2)、添加元素到指定位置。上面讲到的添加元素都是默认添加到所有元素的末尾,那么如果我们想要把元素添加到指定的数组位置呢,ArrayList提供了下面的方法将元素添加到指定位置,上源码。


添加元素到指定位置


检查位置下标有效性

其中index为指定的数组位置下标,element为我们需要添加到数组的元素,添加元素时首先需要检查index是否有效,也就是是否在数组的容量范围之内,大于数组容量和小于的0的下标都是无效下标;检查完下标之后接下来需要进行扩容判断,上面已经详细讲过,这里不再赘述;最后通过System.arraycopy将数组从index下标位置开始的数据向后移动一位,相当于将element[index]的位置可以腾出来给element元素,最后一步elementData[index] = element;将element放到index位置。至此,元素就填到指定位置。

(3)、获取元素。我们将数据放到ArrayList的目的就是为了后续程序使用数据,那么我们怎么来获取保存到ArrayList的数据呢?


根据下标获取元素

相对于添加数据而言,获取数据就简单的多了,get方法是通过下标获取对应位置的元素数据,程序首先会检验下标的有效性,跟添加元素到指定位置的下标校验一样,大于数组容量和小于的0的下标都是无效下标,程序都会报错,下标校验通过直接取数组对应下标元素返回就OK了。

(4)、删除指定位置元素。删除指定位置元素跟添加元素到指定位置是一对相反的操作,可以对应来看。


删除指定位置元素

删除指定位置元素其实也很简单,首先校验下标有效性,然后获取对应下标的元素,也就是即将删除的元素,以备方法返回,由于是删除元素,那么整个数组从删除下标开始的所有元素都需要向前移动一位,最后将最后一位元素置空,就完成了整个删除操作。

(5)、删除指定元素。


删除指定元素

删除指定元素的逻辑还是遍历数组找到该元素的位置下标,然后再根据上面所讲的删除指定位置元素来进行删除操作。



总结:通过以上的源码的分析,我相信很多同学对ArrayList的原理有了一个比较深刻的了解,对ArrayList一系列操作无非是对数组的操作;另外还有一些需要强调的是,ArrayList是线程不安全的,它的所有方法都是没有synchronized关键字同步的,在多线程环境下会存在不可预料的问题。

才疏学浅,码字不易,有总结不到位的请各路大神多多指教,欢迎交流!

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