栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【JavaSE】ArrayList、Vector、LinkedList扩容的底层实现原理

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【JavaSE】ArrayList、Vector、LinkedList扩容的底层实现原理

学习目录
  • 前言
    • 一.传统数组扩容
    • 二.集合扩容
      • 1.ArrayList()
      • 2.Vector
      • 3.LinkedList

前言

编程语言是实现人类思维的一种工具,想到扩容这一问题首先应该学会联系生活实际,在当前容量不够的前提下我们会选择扩容,而这一句话就包含两个核心要素:
1.判断容量是否足够 2.扩大容量
通过集合添加元素的过程就是这两点的隐式重复

一.传统数组扩容

这是我大一在没有接触到集合的时候实现的数组扩容:

1.定义初始数组int[] arr = {1,2,3}
2.定义一个新的数组int[ ] arrNew = new int[ arr.length+1];
3.遍历arr数组,依次将arr的元素拷贝到arrNew数组
4.将新值赋给arrNew[arrNew.length - 1] =4; 把值赋给arrNew最后一个元素
5.让arr 指向arrNew ;arr = arrNew;达到扩容并add的目的

它的本质还是通过在堆中创建新的数组对象,然后让原数组指向堆中的新数组对象

二.集合扩容

上述这个过程并没有实现检测当前容量大小判断是否要扩容的机制,更没有实现自动扩容,都属于人为操作,而这就是数组与集合最大的差别
集合与之不同,它只需要通过一个简单的add方法就能自动扩容并添加,本质是因为方法内部封装了很多复杂的方法实现了很多动作。 今天就来追根溯源

1.ArrayList()

通过Debug遍历的方式查看源码:

public class ArrayListsource {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        for (int i = 0; i < 10; i++) {
            arrayList.add(i);
        }
    }
}

源码部分:

1.当创建ArrayList对象时,如果使用的是无参构造器,首先创建空的elementData数组

2.执行add()向空数组扩容
这个方法里包含了很多动作它先通过ensureCapacityInternal()判断是否要扩容

再通过calculateCapacity()判断elementData是否为空数组,若是则返回10,并将空数组扩容至为空间为10

3.当执行的add操作大于当前容量(10)则与当前空间大小比较并执行grow()方法进行扩容
4.前面我们知道初始elementData容量为0,第1次添加,则扩容elementData为10,如需要再次扩容,则扩容elementData为1.5倍,注意没有拷贝数祖前里面的元素都是null

综上所述:
不难看出ArrayList扩容的本质和传统数组扩容基本差不多,就是把新数组空间变大,然后把值拷贝到新的数组,只不过执行一个简单的add()方法的过程就自动实现了

2.Vector
    public static void main(String[] args) {
        Vector vector=new Vector();
        for (int i = 0; i < 10; i++) {
            vector.add(i);
        }
    }

1.与ArrayList类似,Vector使用无参构造时一开始就赋给他10个空间大小

2.中间过程也是先判断再扩容,Vector扩容的grow()方法与之不同,为两倍增长并非1.5倍 接下来解读一下Vector的grow()方法


实现细节:
在Vector初始化的时候,产生了两个属性initialCapacity和capacityIncrement
一个是初始容量,一个是容量增量,Vector的grow()方法就是通过容量增量(capacityIncrement)来执行的,第一次扩容的时候capacityIncrement=0它不符合条件,于是返回的是oldCapacity,这样就达到了二倍的效果
3.最后进行拷贝实现扩容

3.LinkedList

首先我们看一个动图了解一下双向链表增加元素的实现原理

本质就是更改节点的指向,让插入位置前后元素的头尾指向新元素

代码实现:

 public static void main(String[] args) {
         LinkedList linkedlist=new LinkedList();
             linkedlist.add(1);
     } 

1.首先也是通过构造器创建一个大小为0的链表,并且头尾都指向null
2.当执行add()添加操作时调用linkLast()方法
使用linkLast()将新的节点加入到双向链表尾部,也就是last指向“1”这个节点

同理也使用Linkedfirst()让first指向“1”这个节点

最后完成了add(1)的操作 将1添加到双向链表中

分析到这:懒羊羊寿命-1年

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/955700.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号