Java ArrayList 详解
程序员文章站
2022-09-22 15:21:04
只记录目前为止关注的。JDK1.8 一、基础属性 1.1 内部参数 1.2 三个重载构造方法 二、操作及策略 2.1 动态扩容 扩容策略: 当数组全满了才扩容,新长度=旧长度\ 1.5 动态扩容有两个入口:供用户调用的显式扩容 和添加元素时的隐式扩容 ,不过均是调用 来根据传入所需容量值决定是否扩容 ......
只记录目前为止关注的。jdk1.8
一、基础属性
1.1 内部参数
//空存储实例。直接new arraylist()便是以该空数组作为实例 private static final object[] empty_elementdata = {}; //默认容量大小,在由空实例进行首次扩容时,扩到到该长度。 //实际使用中,并未实际存在capacity这个参数,需要扩容时直接根据旧数组的length进行扩容 private static final int default_capacity = 10; //实际存储数组 transient object[] elementdata; //存储元素个数 private int size; //该字段用于迭代器的fail-fast机制【参考另一篇文章】 protected transient int modcount = 0;
1.2 三个重载构造方法
//构建一个空实例,elementdata指向容量为0的空数组 public arraylist() { this.elementdata = defaultcapacity_empty_elementdata; } //以给定容量初始化存储数组 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); } } //以集合初始化创建列表 //步骤:1. 调用toarray(),将给定集合转成数组(以arraylist为例,toarray()返回的是实际存在元素的那部分数组,即[0,size)) //2. 让size直接等于给定集合的数组长度 //3. 判断size如果为0则直接创建空存储实例,否则使用arrays.copyof将给定集合数组复制一份(浅拷贝),作为存储数组 public arraylist(collection<? extends e> c) { elementdata = c.toarray(); if ((size = elementdata.length) != 0) { // c.toarray might (incorrectly) not return object[] (see 6260652) if (elementdata.getclass() != object[].class) elementdata = arrays.copyof(elementdata, size, object[].class); } else { // replace with empty array. this.elementdata = empty_elementdata; } } // arraylist 的 toarray()源码,复制[0,size)部分返回 public object[] toarray() { return arrays.copyof(elementdata, size); }
二、操作及策略
2.1 动态扩容
扩容策略:当数组全满了才扩容,新长度=旧长度*1.5
动态扩容有两个入口:供用户调用的显式扩容ensurecapacity()
和添加元素时的隐式扩容ensurecapacityinternal()
,不过均是调用ensureexplicitcapacity()
来根据传入所需容量值决定是否扩容,最终实际扩容操作在grow()
方法中。
//显式扩容入口方法 public void ensurecapacity(int mincapacity) { int minexpand = (elementdata != defaultcapacity_empty_elementdata) // any size if not default element table ? 0 // larger than default for default empty table. it's already // supposed to be at default size. : default_capacity; if (mincapacity > minexpand) { ensureexplicitcapacity(mincapacity); } } //隐式扩容入口方法 //其中参数 mincapacity 值为 size+1,由add方法调用传入 private void ensurecapacityinternal(int mincapacity) { ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity)); } //添加方法 public boolean add(e e) { // 传入最小所需容量为size+1 ensurecapacityinternal(size + 1); // increments modcount!! elementdata[size++] = e; return true; } //计算所需容量,实则不需要计算 //只是单纯判断当前是否是空实例,为空就话返回 "默认容量"与mincapacity之间的较大值,不为空直接返回mincapacity //参数 mincapacity 只有两种情况: // 1. 隐式扩容时,如add()传入,其值为 size+1 // 2. 显式扩容,用户指定 private static int calculatecapacity(object[] elementdata, int mincapacity) { if (elementdata == defaultcapacity_empty_elementdata) { return math.max(default_capacity, mincapacity); } return mincapacity; } //在此处,根据最小所需容量来判断是否实际进行扩容 private void ensureexplicitcapacity(int mincapacity) { modcount++; // overflow-conscious code if (mincapacity - elementdata.length > 0) //若已经占满,才进行扩容 grow(mincapacity); } //实际扩容方法 //可以看到扩容策略为:length + length*0.5(右移1位缩小1倍) //然后调用arrays.copyof浅复制 private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; int newcapacity = oldcapacity + (oldcapacity >> 1); //旧长度+旧长度*2 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); }
2.2 删除操作
arraylist中有两个remove方法public e remove(int index)
和public boolean remove(object o)
源码实现得其实挺简单,本来还在犹豫有没有必要把remove方法记录下来,但发现有个点值得注意以下:
注意点:jdk对于数组内元素统一移动操作,偏好使用system.arraycopy(ary, srcpos, ary, destpos, len)
来移动
//通过给定下标来删除元素,并返回删除元素 public e remove(int index) { rangecheck(index); // 检查下标范围 modcount++; e oldvalue = elementdata(index); // 合理的话,先获取该元素(等会儿用于返回) int nummoved = size - index - 1; // 计算待移动元素个数(删除元素后,后面的元素要统一往前挪补上) if (nummoved > 0) system.arraycopy(elementdata, index+1, elementdata, index, nummoved); // 使用system.arraycopyl来移动数组元素 elementdata[--size] = null; // clear to let gc do its work // 删除后size-1,并将先前最后一个元素置null return oldvalue; //返回删除元素 } // 判断下标是否合理(<size),否则抛出异常 private void rangecheck(int index) { if (index >= size) throw new indexoutofboundsexception(outofboundsmsg(index)); } // 删除首个与给定元素相等的元素,元素判等使用equal方法 // 成功返回true,失败返回false public boolean remove(object o) { if (o == null) { // 可以删除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])) { // 从头开始一个个检查,使用equal判等 fastremove(index); return true; } } return false; } /* * 官方注释说得很清楚了:删除元素,但跳过边界检查且不返回删除元素。(就是remove(index)的缩略版 * private remove method that skips bounds checking and does not * return the value removed. */ 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; // clear to let gc do its work }
上一篇: 晚会再救
下一篇: 成吉思汗苦等一女子几十年,她是谁呢?