1、ArrayList-底层使用数组实现
/*** 默认初始容量大小为10*/private static final int DEFAULT_CAPACITY = 10;/*** 如果自定义容量为0，则会默认用它来初始化ArrayList，或者用于空数组替换*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** 如果没有自定义容量，则会使用它来初始化ArrayList，或者用于空数组比对。*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 实际ArrayList的大小/集合中元素的个数*/private int size;/**存储ArrayList元素的数组缓冲区。ArrayList的容量是这个数组缓冲区的长度。任何elementData==DEFAULTCAPACITY_empty_elementData的空ArrayList，当添加第一个元素时，将扩展到默认的容量。*/transient Object[] elementData;
2、ArrayList-构造方法
1、ArrayList提供了三种方式的构造器：/*** 构造一个初始容量为10的空列表。*/public ArrayList() {//如果没有传入初始化容量，则使用空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA//使用这个数组是在添加第一个元素的时候就会扩容到默认大小10this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** 构造具有指定初始容量的空列表。* 这就是ArrayList底层用到的数组* 非私有，用于简化嵌套类访问* transient 在已经实现序列化的类中，不允许某变量序列化(让某些被修饰的变量不参加序列化。)。** @param 列表的初始容量* @throws 如果指定的初始容量为负数，则为IllegalArgumentException*/public ArrayList(int initialCapacity) {//如果传入的初始容量大于0，则新建一个数组来存储元素if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//如果传入的初始容量等于0，则使用空数组EMPTY_ELEMENTDATAthis.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);}}/*** 构造一个包含指定集合元素的列表，其顺序由集合的迭代器返回** @param 要将其元素放入此列表中的集合* @throws 如果指定的集合为null，则发生NullPointerException*/public ArrayList(Collection<? extends E> c) {//.toArray();集合转数组elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)//检查c.toArray()返回值是不是Object[]类型，如果不是，重新拷贝成Object[].class类型if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.//如果c是空集合，则初始化为空数组EMPTY_ELEMENTDATAthis.elementData = EMPTY_ELEMENTDATA;}}
3、ArrayList-存储元素方法
1、ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)这些添加元素的方法。/*** 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。** @param 要替换的元素的索引* @param 要存储在指定位置的元素元素* @return 以前位于指定位置的元素* @throws 数组下标越界异常*/public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}/*** 将指定的元素追加到此列表的末尾。时间复杂度为O(1)** @param 要附加到此列表的元素* @return 元素添加成功，返回true*/public boolean add(E e) {//检查是否需要扩容//size+1???//1.如果集合添加元素成功后，集合中的实际元素个数。 2.为了确保扩容不会出现错误。//如果默认大小是0，则0 + 0 » 1还是0。 如果size是1，则1 + 1 » 1还是1//jdk1.8版本以后，ArrayList中的扩容放在add()方法中。之前放在构造方法中。//默认所以ArrayList arrayList = new ArrayList();size应该是0。所以,size+ 1对扩容来讲很必要。ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}/*** 在此列表的指定位置插入指定的元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（在其索引中添加一个元素）* 时间复杂度O(n)* @param 要插入指定元素的索引* @param 要插入的元素* @throws 数组下标越界异常*/public void add(int index, E element) {//检查是否越界rangeCheckForAdd(index);//如果数组长度不足，将进行扩容。ensureCapacityInternal(size + 1); // Increments modCount!!//.arraycopy():// 将 elementData中从Index位置开始、长度为size-index的元素，// 拷贝到从下标为index+1位置开始的新的elementData数组中。// 即将当前位于该位置的元素以及所有后续元素右移一个位置。System.arraycopy(elementData, index, elementData, index + 1,size - index);//将元素插入到index的位置elementData[index] = element;size++;}/*** .arraycopy();1.Object src：原数组2.int srcPos：从元数据的起始位置开始3.Object dest：目标数组4.int destPos：目标数组的开始起始位置5.int length：要复制的数组的长度*/public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);/*** 将指定集合中的所有元素追加到此列表，按照指定集合的迭代器。* @param 包含要添加到此列表的元素的c集合* @return 添加成功则返回true* @throws 如果追加的集合是空的，则抛出空指针异常*/public boolean addAll(Collection<? extends E> c) {//将集合转为数组Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;//如果c不为空就返回true,否则返回false。return numNew != 0;}/*** 从指定的位置开始，将指定collection中的所有元素插入到此列表中。** @param 从指定集合插入第一个元素的索引* @param 包含要添加到此列表的元素的c集合* @return 添加成功则返回true* @throws 数组下标越界异常* @throws 如果追加的集合是空的，则抛出空指针异常*/public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew); // Increments modCountint numMoved = size - index;if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0;}
4、ArrayList-获取元素方法
1、ArrayList提供了get(int index);获取元素的方法。//返回此列表中指定位置上的元素。 时间复杂度O(1)public E get(int index) {//检查元素是否越界rangeCheck(index);checkForComodification();//返回数组index位置的元素return ArrayList.this.elementData(offset + index);}
5、ArrayList-删除元素方法
1、ArrayList提供了根据下标或者指定对象两种方式的删除功能。2、[!!!]从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。/*** 移除此列表中指定位置上的元素。 时间复杂度为O(n)** @param 索引要删除的元素的索引* @return 从列表中删除的元素* @throws 数组下标越界异常*/public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);// 如果index不是最后一位，则将index之后的元素往前挪一位int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 将最后一个元素删除，帮助GCelementData[--size] = null; // clear to let GC do its work// 返回旧值return oldValue;}/*** 移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。* 时间复杂度为O(n)*/public boolean remove(Object o) {//由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。if (o == 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])) {//.fastRemove(index)快速删除相对于remove(int index)少了检查索引越界的操作。fastRemove(index);return true;}}return false;}private void fastRemove(int index) {modCount++;// 如果index不是最后一位，则将index之后的元素往前挪一位int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 将最后一个元素删除，帮助GCelementData[--size] = null; // clear to let GC do its work}
6、ArrayList-数组容量调整方法
1、每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。2、数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。3、[!!!]在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。/*** 增加这个<tt>ArrayList</tt>实例的容量* minCapacity = size+1* @param 期望的最小容量*/public void ensureCapacity(int minCapacity) {//如果元素数据不为空，则初始化为0，否则为默认初始容量大小：为10int 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);}}// 存储元素相关方法中调用该方法，比如：.add()中// minCapacity = size+1// 确保内部容量private void ensureCapacityInternal(int minCapacity) {//如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则初始化为默认大小10.if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//确保许可容量ensureExplicitCapacity(minCapacity);}//确保许可容量private void ensureExplicitCapacity(int minCapacity) {//modCount不用理它，它用来计算修改次数//ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)//扩容，增加容量grow(minCapacity);}/*** 增加容量，以确保它至少可以容纳minimum capacity参数指定的元素数。* minCapacity=size+1* 假如不size+1处理，如果默认大小是0，则0 + 0 » 1还是0。 如果size是1，则1 + 1 » 1还是1。* 默认所以ArrayList arrayList = new ArrayList();size应该是0。因为size在只会调用add()方法时才会自增。* @param 最小容量所需的最小容量*/private void grow(int minCapacity) {// overflow-conscious code//计算元素数据的大小int oldCapacity = elementData.length;//默认扩容1.5倍//表示将oldCapacity右移一位（位运算），相当于除2.再加上1，相当于新容量扩容1.5倍。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://以新容量拷贝出来一个新的数组赋值给elementDataelementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 如果新容量大于最大容量，则新容量为 Integer.MAX_VALUE；否则为 Integer.MAX_VALUE - 8return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}/*** 将这个集合实例的容量调整为列表的当前大小(将elementData的数组设置为ArrayList实际的容量，动态增长的多余容量被删除了。)。* 应用程序可以使用此操作最小化<tt>ArrayList</tt>实例的存储。* 将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。*/public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}
7、ArrayList-集合运算方法
1、 并集：.addAll(Collection<? extends E> c) :按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾交集：.retainAll(Collection<?> c): 仅保留此列表中包含在指定集合中的元素。差集：.removeAll(Collection<?> c) :从此列表中删除指定集合中包含的所有元素。无重复并集：list2.removeAll(list1);list1.addAll(list2);1-1、求两个集合的交集：list1.retainAll(list2);//获取两个集合的交集public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);// 调用批量删除方法，这时complement传入true，表示删除不包含在c中的元素return batchRemove(c, true);}//具体操作集合的方法，当complement为false时表示删除c中包含的元素、为true时表示删除c中不包含的元素private boolean batchRemove(Collection<?> c, boolean complement) {//获得当前对象的所有元素，final修改final Object[] elementData = this.elementData;// 使用读写两个指针同时遍历数组// 读指针每次自增1，写指针放入元素的时候才加1int r = 0, w = 0;// 设置标记位boolean modified = false;try {// 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）for (; r < size; r++)if (c.contains(elementData[r]) == complement)elementData[w++] = elementData[r];//存在则直接保存} finally {// 正常来说r最后是等于size的，除非c.contains()抛出了异常// Preserve behavioral compatibility with AbstractCollection,// even if c.contains() throws.if (r != size) {// 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后System.arraycopy(elementData, r,elementData, w,size - r);w += size - r;//当前集合大小}if (w != size) {//将写指针之后的元素置为空，帮助GC// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;//新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）modCount += size - w;size = w;//交集大小modified = true;}}return modified;}1-2、求两个集合的差集：list1.removeAll(list2);//只保留当前集合中不在c中的元素，不保留在c中不在当前集体中的元素。public boolean removeAll(Collection<?> c) {// 集合c不能为空Objects.requireNonNull(c);// 同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素return batchRemove(c, false);}// 删除指定范围的元素protected void removeRange(int fromIndex, int toIndex) {modCount++;int numMoved = size - toIndex;System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);// 同样是利用copy去操作的 计算出位置直接赋值// clear to let GC do its workint newSize = size - (toIndex-fromIndex);for (int i = newSize; i < size; i++) {elementData[i] = null;}size = newSize;}1-3、求两个集合的并集：list1.addAll(list2);见.addAll();方法
8、ArrayList-集合源码分析总结
1、ArrayList-集合源码分析总结1-1、ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；1-2、ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；1-3、ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；1-4、ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；1-5、ArrayList从尾部删除元素极快，时间复杂度为O(1)；1-6、ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；1-7、ArrayList支持求并集，调用addAll(Collection c)方法即可；1-8、ArrayList支持求交集，调用retainAll(Collection c)方法即可；1-9、ArrayList支持求单向差集，调用removeAll(Collection c)方法即可;
若有收获，就点个赞吧
0 人点赞
