Java之ArrayList源码分析（第三篇：删除元素） |
您所在的位置：网站首页 › arraylist删除元素的方法 › Java之ArrayList源码分析（第三篇：删除元素） |
Java之ArrayList源码分析（第三篇：删除元素）
|
（注意：本文基于JDK1.8） 删除元素的4个方法
清空元素的clear（）方法
删除指定位置index（下标）的元素并返回旧的元素，传入参数index表示下标值 1、检查下标值是否符合要求 通过rangeCheck（）方法完成下标值index的检查工作，检查下标值是否满足范围要求，如果传入的下标值index超过或者等于元素总数size，将抛出一个IndexOutOfBoundsException异常对象，具体的检查过程，下文会提到rangeCheck（）方法的源码分析 2、fail-fast机制，防止多线程下使用ArrayList的办法 将实例变量modCount加1，表示已经产生了修改元素的行为，modCount并不在ArrayList中定义，我向上查找，发现它在基类AbstractList中定义 3、获取当前下标index中的已经保存的元素 从ArrayList对象持有的底层数组对象elementData中的下标index处取出元素对象，并赋值给局部变量oldValue持有 4、计算需要挪动的元素数量 现在需要删除一个元素，空余的位置，需要后面的元素向前移动占满，先计算下需要挪动几个元素，使用公式size - index - 1即可 举个例子：假设目前ArrayList一共保存了5个元素，此时size==5，你需要删除下标0的元素，我们用公式计算一下需要挪动几个元素（size - index - 1）。5 - 0 - 1 = 4，共计4个元素要向前“挪动”，其实是下标0之后的4个元素，依次向前复制一位，比如开始的数组是【"8"，"9"，"3"，"5"，"6"】，现在删除下标0的元素，然后下标0后面的4个元素会向前复制一位，则数组变为【"9"，"3"，"5"，"6"，"6"】，看到了吧？数组的最后一位此时还是存在的，只是第一位的元素被覆盖了…… 5、向前挪动所有元素 使用System的arraycopy（）方法完成“挪动元素” 第一个参数elementData表示需要挪动的源数组对象 第二个参数index+1表示从源数组对象的哪个下标处开始 第三个参数表示要拷贝到的目标数组对象 第四个参数表示从目标数组对象的哪个下标处开始拷贝 第五个参数表示复制的元素总数，挪动数量numMoved即表示需要复制的元素总数 6、将元素总数size减1 7、将无用的元素赋值为null，便于GC回收 因为所有index后面的元素都向前挪动了一位（向前复制），此时size处下标仍然保存的是未挪动前的元素对象，只有直接赋值为null，日后此对象才能被GC回收掉（不然就会造成数组多个下标指向同一个对象，造成对象无法被回收） 8、向调用者返回结果 返回旧的元素对象 rangeCheck（int）方法分析 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }用于检查下标值index是否符合范围的方法 1、判断传入的下标值index大于或者等于元素总数size 如果不符合要求，将执行下面的步骤2和步骤3 2、生成异常信息字符串 先是调用了一个outOfBoundsMsg（）方法，outOfBoundsMsg（）方法接受了下标值index，该方法返回的字符串信息会在控制台展示，在第二篇文章中已经分析了outOfBoundsMsg（）方法的实现，这里不再解释 3、抛出一个IndexOutOfBoundsException异常对象 remove（Object）方法分析 public boolean remove(Object o) { 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); return true; } } return false; }用于将相等的元素对象删除的方法，传入的参数表示元素对象 因为ArrayList支持添加null作为元素，所以作者将null元素与非null元素的删除逻辑分开处理，我们分别学习一下 一、传入的元素为null 当传入的元素为null时，则会从数组对象elementData的第1个元素开始遍历，一直遍历到元素总数size-1的下标处，每1轮的迭代会判断elementData对应下标的元素值是否为null，此处使用==作为元素相等的判断依据，因为null无法使用equals（）方法比较对象是否相等 1、当从ArrayList对象持有的elementData找到一个元素为null时，调用fastRemove（）方法进行删除元素，并结束遍历，整个remove（Object）方法会返回true，表示找到相等的元素，并删除元素成功 2、如果遍历结束，没有在elementData中找到任何的null元素，remote（Object）方法会返回false，表示删除元素失败 二、传入的元素为非null时 传入的元素为非null，同样从底层数组对象elementData的第一个元素开始遍历，遍历过程中每一轮都会调用传入的元素Object对象的equals（）方法与elementData对应下标中的元素对象进行比较，此处使用Object的equals（）方法比较元素对象的相等性，equals（）方法的返回结果表示相等性，true表示两个对象相等、false表示两个对象不相等 1、当在elementData中找到一个匹配的元素（此时equals（）方法返回true），执行fastRemove（int）方法进行删除元素，之后遍历结束，整个remove（）方法返回true，表示删除元素成功 2、当遍历结束，没有找到匹配相等的元素，整个remote（Object）方法返回false，表示删除元素失败 fastRemove（int）方法分析 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 }删除ArrayList对象持有的elementData数组对象中元素的方法，学习一下它的源码 说明：无论删除null元素、还是删除Object元素，都会调用该方法进行删除 1、fail-fast机制，防止多线程下使用ArrayList 将表示修改次数的实例变量modCount加1 2、计算需要向前挪动的元素数量 计算公式为size - index - 1，结果保存在局部变量numMoved中 3、当需要挪动的元素大于0，执行数组元素复制，即数组元素挪动 同样使用System的静态方法arraycopy（）完成元素的复制（挪动），删除操作会执行向前复制元素 4、元素总数size减去1 5、将不再使用的下标赋值为null，便于GC未来回收指向的对象 size值作为下标，将其赋值为null removeAll（Collection）方法分析 public boolean removeAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, false); }用于删除指定集合中的多个元素，传入一个Collection对象，表示待删除的元素集合 1、检查传入的Collection必须不能为null 调用了Objects下的方法来判断是否为null 2、调用一个batchRemove（）方法完成批量删除工作 调用batchRemove（）方法，同时传入一个Collection对象与一个false值 3、返回batchRemove（）方法的执行结果给调用方 batchRemove（）方法分析 private boolean batchRemove(Collection c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }用于删除集合中的所有元素 1、获取ArrayList对象持有的底层数组对象elementData 首先获取当前ArrayList对象持有的底层数组对象elementData，并赋值给一个同名的局部变量elementData持有 2、定义两个局部变量 一个局部变量r表示读取下标（遍历时elementData数组时的，读取下标） 一个局部变量w表示写入下标 3、定义一个标志位 局部变量modified，初始值为false，表示什么呢？后面看看 4、检查现有ArrayList对象持有的每一个元素是否与传入的Collection对象的任意一个元素匹配，如果不匹配，说明是要保留的元素对象，此时将要保留的元素会继续存放在底层数组对象elementData中下标w处，并且下标w之后会加1，最终w坐标及之前的所有元素均为需要存入的元素，这里需要画一张图 5、针对c.ontains（）方法抛出异常的情况做处理 finally代码块对c.contains可能抛出异常的情况也做了处理，如果c.contains抛出了异常，则r一定不等于size，此时将r下标后面的元素一个一个的复制到以w下标开始的数组中 6、清除无用元素占用的数组位置 将保留所有元素的后面位置，全部赋值为null，是从局部变量w开始的下标算起，size减去局部变量w的值就是要被修改的数量，此时也会对modCount做了更新，后面又更新了最新的元素总数，w的值目前就是新的元素总数，所以最后又赋值给size 7、将标志位更为true 标记到modified变量中，表示删除结果 8、返回删除结果 将modified的boolean值返回给调用方 clear（）方法分析 public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }用于清空ArrayList所有元素的方法 1、fail-fast机制，防止多线程下使用ArrayList的办法 首先将modCount增加1个，其它位置对modCount会做判断 2、将elementData数组对象中的所有元素赋值为null 将ArrayList对象持有的底层数组elementData对象中的持有的所有对象，全部赋值为null，剩下的工作就交给GC了 3、更新元素总数 元素总数size赋值为0 总结1、modCount值用于fail-fast机制（防止多线程下使用ArrayList），添加单个元素或多个元素、删除单个元素或多个元素、清空所有元素时，均对modCount值做了+1，表示修改次数加1 2、中间删除元素，也是O（n）的时间复杂度，因为删除元素后，需要将后面的元素，一个一个的向前复制元素（表示挪动元素） 3、感叹作者想的好周全，removeIf（）方法将单独分析…… 4、System的静态方法arraycopy（）继续作为数组元素向前"挪动"的功能，这个native方法值得学习 |
【本文地址】
今日新闻 |
推荐新闻 |