做网站合伙怎么分,网站开发前如何配置电脑,seo外包公司费用,永久免费国外域名注册一、ArrayList的数据结构 ArrayList底层的数据结构就是数组#xff0c;数组元素类型为Object类型#xff0c;即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作(增删改查等)#xff0c;其底层都是基于数组的。 定义底层数据结构#xff1a;Object[] elementDat…一、ArrayList的数据结构 ArrayList底层的数据结构就是数组数组元素类型为Object类型即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作(增删改查等)其底层都是基于数组的。 定义底层数据结构Object[] elementData /*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access The capacity of the ArrayList is the length of this array buffer. 注释中这句话的意思是ArrayList的capacity即容量是数组elementData的长度。capacity elementData.length而不是arrayList.size()。 Any empty ArrayList with elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added. 注释中这句话的意思是当通过如ListString dataList new ArrayList();创建ArrayList的一个对象时此时该dataList是没有被定义容量的当add第一个元素的时候此时才将dataList的容量设置为 DEFAULT_CAPACITY即10. 举例说明 因为ArrayList中数组elementData的属性是default所以我们通过反射来获取数组的长度即capacity。 public class Test {public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {ListString dataList new ArrayList();//初始化时获取ArrayList的capacityint arrayListCapacity getArrayListCapacity(dataList);System.out.println(初始化时ArrayList的capacity arrayListCapacity);dataList.add(zhangsan);//添加第一个元素初始化时获取ArrayList的capacityint arrayListCapacity1 getArrayListCapacity(dataList);System.out.println(add第一个元素后ArrayList的capacity arrayListCapacity1);}/*** 反射获取ArrayList的容量capacity* param arrayList* return* throws NoSuchFieldException* throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {ClassArrayList arrayListClass ArrayList.class;Field elementData arrayListClass.getDeclaredField(elementData);elementData.setAccessible(true);Object[] objects (Object[]) elementData.get(arrayList);return objects.length;}
} 结果 初始化时ArrayList的capacity0
add第一个元素后ArrayList的capacity10 二、ArrayList的属性 public class ArrayListE extends AbstractListEimplements ListE, RandomAccess, Cloneable, java.io.Serializable{// 版本号private static final long serialVersionUID 8683452581122892189L;// 缺省容量private static final int DEFAULT_CAPACITY 10;// 空对象数组private static final Object[] EMPTY_ELEMENTDATA {};// 缺省空对象数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};// 元素数组transient Object[] elementData;// 实际元素大小默认为0private int size;// 最大数组容量private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;
} ArrayList类的属性中核心的属性为elementData类型为Object[]用于存放实际元素并且被标记为transient也就意味着在序列化的时候此字段是不会被序列化的。 三、ArrayList的构造函数 public ArrayList()型构造函数 /*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} 构造一个空的arrayList对象初始容量为10。该初始容量也是add第一个元素的时候设置的。 public ArrayList(int initialCapacity)型构造函数 /*** Constructs an empty list with the specified initial capacity.** param initialCapacity the initial capacity of the list* throws IllegalArgumentException if the specified initial capacity* is negative*/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);}} 构造一个空的arrayList对象并指定初始容量不允许初始容量小于0否则抛出异常。 public ArrayList(Collection? extends E c)型构造函数 /*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collections* iterator.** param c the collection whose elements are to be placed into this list* throws NullPointerException if the specified collection is null*/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;}} 举例说明 public class Test {private static int size;public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {ListString dataList new ArrayList();dataList.add(zhangsan);dataList.add(lisi);dataList.add(wangwu);System.out.println(传入的参数dataList的大小: dataList.size());ListString dataList2 new ArrayList(dataList);System.out.println(new ArrayList(dataList)的元素: dataList2);int arrayListCapacity getArrayListCapacity(dataList2);System.out.println(new ArrayList(dataList)的capacity: arrayListCapacity);}/*** 反射获取ArrayList的容量capacity* param arrayList* return* throws NoSuchFieldException* throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {ClassArrayList arrayListClass ArrayList.class;Field elementData arrayListClass.getDeclaredField(elementData);elementData.setAccessible(true);Object[] objects (Object[]) elementData.get(arrayList);return objects.length;}
} 结果 传入的参数dataList的大小: 3
new ArrayList(dataList)的元素: [zhangsan, lisi, wangwu]
new ArrayList(dataList)的capacity: 3 此种构造方法得到的arrayList的capacity为传入collection的size。 四、ArrayList的增删改查 1、增add public class TestArrayList {public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {ListString dataList new ArrayList();int arrayListCapacity getArrayListCapacity(dataList);System.out.println(未添加元素在时capacity arrayListCapacity);dataList.add(zhangsan1);int arrayListCapacity1 getArrayListCapacity(dataList);System.out.println(add第一个元素在时capacity arrayListCapacity1);dataList.add(zhangsan2);dataList.add(zhangsan3);dataList.add(zhangsan4);dataList.add(zhangsan5);dataList.add(zhangsan6);dataList.add(zhangsan7);dataList.add(zhangsan8);dataList.add(zhangsan9);dataList.add(zhangsan10);int arrayListCapacity2 getArrayListCapacity(dataList);System.out.println(add第十个元素在时capacity arrayListCapacity2);dataList.add(zhangsan11);int arrayListCapacity3 getArrayListCapacity(dataList);System.out.println(add第十一个元素在时capacity arrayListCapacity3);}/*** 反射获取ArrayList的容量capacity* param arrayList* return* throws NoSuchFieldException* throws IllegalAccessException*/public static int getArrayListCapacity(List arrayList) throws NoSuchFieldException, IllegalAccessException {ClassArrayList arrayListClass ArrayList.class;Field elementData arrayListClass.getDeclaredField(elementData);elementData.setAccessible(true);Object[] objects (Object[]) elementData.get(arrayList);return objects.length;}
} 结果 未添加元素在时capacity0
add第一个元素在时capacity10
add第十个元素在时capacity10
add第十一个元素在时capacity15 结合以上在添加第一个元素时进行了扩容capacity为10。当添加第十一个元素时此时容量为10已不够用又进行了扩容capacity为15。 add源码如下 /*** Appends the specified element to the end of this list.** param e element to be appended to this list* return tttrue/tt (as specified by {link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size 1); // Increments modCount!!elementData[size] e;return true;} ensureCapacityInternal函数确保elemenData数组有合适的大小。指定minCapacity大小 private void ensureCapacityInternal(int minCapacity) {if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);} ensureExplicitCapacity函数判断是否需要扩容。当arrayList所需的最小容量minCapacity大于当前数组elementData的长度时就需要扩容了。 private void ensureExplicitCapacity(int minCapacity) {modCount;// overflow-conscious codeif (minCapacity - elementData.length 0)grow(minCapacity);} 真正的扩容方法grow。 拷贝扩容Arrays.copyOf(elementData, newCapacity)根据newCapacity构建一个新的数组并将原数组elementData的数组复制到新数组中。最后将新的数组赋值给原数组。 /*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint 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);} int newCapacity oldCapacity (oldCapacity 1); 正常情况下会扩容1.5倍特殊情况下新扩展数组大小已经达到了最大值则只取最大值。 增插入add(int index,E element) 举例 public class Test {public static void main(String[] args) {ListString list new ArrayList();list.add(zhangsan1);list.add(zhangsan2);list.add(zhangsan3);list.add(zhangsan4);System.out.println(list before add list);list.add(1,zhaoliu);System.out.println(list after add list);}
} 结果 list before add[zhangsan1, zhangsan2, zhangsan3, zhangsan4]
list after add[zhangsan1, zhaoliu, zhangsan2, zhangsan3, zhangsan4] 源码分析类似于下面的remove都涉及到元素的移动。 /*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** param index index at which the specified element is to be inserted* param element element to be inserted* throws IndexOutOfBoundsException {inheritDoc}*/public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size 1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index 1,size - index);elementData[index] element;size;} 2、删remove 举例 public class TestArrayList {public static void main(String[] args) {ListString dataList new ArrayList();dataList.add(zhangsan);dataList.add(lisi);dataList.add(wangwu);dataList.add(zhaoliu);System.out.println(dataList);dataList.remove(1);System.out.println(dataList);}
} 结果 [zhangsan, lisi, wangwu, zhaoliu]
[zhangsan, wangwu, zhaoliu] remove源码 /*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices).** param index the index of the element to be removed* return the element that was removed from the list* throws IndexOutOfBoundsException {inheritDoc}*/public E remove(int index) {rangeCheck(index);modCount;E oldValue elementData(index);int numMoved size - index - 1;if (numMoved 0)System.arraycopy(elementData, index1, elementData, index,numMoved);elementData[--size] null; // clear to let GC do its workreturn oldValue;} 解释说明 对索引进行校验后判断删除后需要移动的个数本例中删除索引1的元素需要移动索引23即两个元素 移动元素使用的是System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)方法。 原数组 [zhangsan, lisi, wangwu, zhaoliu] 变成 [zhangsan, wangwu, zhaoliu, zhaoliu] 最后 elementData[--size] null 将最后一个元素置为null。此时的size为3即将element[3]置为null显示如下 [zhangsan, wangwu, zhaoliu] 注意这句注释clear to let GC do its work 说明置空原尾部数据 不再强引用, 可以GC掉引用为null 3、改set 举例 public class TestArrayList {public static void main(String[] args) {ListString dataList new ArrayList();dataList.add(zhangsan);dataList.add(lisi);dataList.add(wangwu);dataList.add(zhaoliu);System.out.println(dataList);dataList.set(3,zl);System.out.println(dataList);}
} 结果 [zhangsan, lisi, wangwu, zhaoliu]
[zhangsan, lisi, wangwu, zl] set源码 /*** Replaces the element at the specified position in this list with* the specified element.** param index index of the element to replace* param element element to be stored at the specified position* return the element previously at the specified position* throws IndexOutOfBoundsException {inheritDoc}*/public E set(int index, E element) {rangeCheck(index);E oldValue elementData(index);elementData[index] element;return oldValue;} 判读所给索引是否在arrayList的size之内否则抛出 IndexOutOfBoundsException异常。 /*** Checks if the given index is in range. If not, throws an appropriate* runtime exception. This method does *not* check if the index is* negative: It is always used immediately prior to an array access,* which throws an ArrayIndexOutOfBoundsException if index is negative.*/private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));} 4、查get 举例说明 public class TestArrayList {public static void main(String[] args){ListString dataList new ArrayList();dataList.add(zhangsan);dataList.add(lisi);dataList.add(wangwu);dataList.add(zhaoliu);System.out.println(dataList.get(3));}
} 结果 zhaoliu get源码 /*** Returns the element at the specified position in this list.** param index index of the element to return* return the element at the specified position in this list* throws IndexOutOfBoundsException {inheritDoc}*/public E get(int index) {rangeCheck(index);return elementData(index);} 可以看到ArrayList的增、删都涉及到元素的移动当元素数量比较多的时候效率相对就会降低。但是改、查不涉及到元素的移动根据索引值直接定位效率比较高。 五、总结 1、ArrayList的优缺点 从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下 1、ArrayList底层以数组实现是一种随机访问模式再加上它实现了RandomAccess接口因此查找也就是get的时候非常快 2、ArrayList在顺序添加一个元素的时候非常方便只是往数组里面添加了一个元素而已 不过ArrayList的缺点也十分明显 1、删除元素的时候涉及到一次元素复制如果要复制的元素很多那么就会比较耗费性能 2、插入元素的时候涉及到一次元素复制如果要复制的元素很多那么就会比较耗费性能 因此ArrayList比较适合顺序添加、随机访问的场景。 2、ArrayList和Vector的区别 Vector它是ArrayList的线程安全版本其实现90%和ArrayList都完全一样区别在于 1、Vector是线程安全的ArrayList是线程非安全的 2、Vector可以指定增长因子如果该增长因子指定了那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子如果不指定增长因子那么就给原数组大小*2源码如下 int newCapacity oldCapacity ((capacityIncrement 0) ?capacityIncrement : oldCapacity); 参考资料 https://blog.csdn.net/hrbeuwhw/article/details/79435934 集合间关系图 https://www.cnblogs.com/leesf456/p/5308358.html https://www.cnblogs.com/xrq730/p/4989451.html转载于:https://www.cnblogs.com/zfyang2429/p/10341923.html
