前言
前几天接到一个类似版本控制的需求，其中某个元素需要排在最后面。遇到问题有点意思，在实现的过程中出现了元素的重复。
实现过程
由于我需要将某个元素排到最后面，第一想法使用冒泡法，将需要的元素依次与后面的元素做一个交换，完成冒泡排序。
假设 en 你需要转移的元素，完成与 2 、3 这两元素的交换。
正常来说，我们是这样使用的冒泡法的。
String[] str = new String[]{"1", "en", "2", "3"};
String temp;
for (int i = 0; i < str.length; i++) { if ("en".equals(str[i])) { for (int j = i; j < str.length - 1; j++) { temp = str[j]; str[j] = str[j + 1]; str[j + 1] = temp; } break; } }
复制代码
但是现在容器使用的不是数组，而是 list。使用类似这样的方式就出了点差错。
这个是实现的第一版
List<String> list = new ArrayList<>();
list.add("1"); list.add("en"); list.add("2"); list.add("3");
int size = list.size();
String temp1;
String temp2;
for (int i = 0; i < size; i++) { if ("en".equals(list.get(i))) { for (int j = i; j < size - 1; j++) { temp1 = list.get(j); temp2 = list.get(j + 1); list.add(j, temp2); list.add(j + 1, temp1);
} break; } }
复制代码
出乎意料的是，输出结果是
和理想差距很大，正常需要结果应该是 1 2 3 en 。但是看第一版输出结果，复制很多相同元素，感觉是 ArrayLst 添加的时候有问题。所以点进去看看，验证自己的猜测。
// jdk 11 版本 /** * 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); // 记录修改次数 modCount++; final int s; Object[] elementData; // 初始化容器 if ((s = size) == (elementData = this.elementData).length) elementData = grow(); // 数组复制 System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; // 容器容量加一 size = s + 1; }
复制代码
add 源码里有一个 System.arraycopy 以及 全局的 size，前者是数组复制的时候，index 到 index + 1 复制，这也是为什么，当 index = 2 的时候 val = "en" ，复制的时候复制了这个到 index = 3 元素相同。后者进行一次 add 已使用的容器大小就会加一。
根据这两个我们可以模拟出第一次实现的时候出现相同元素、以及 size 变大的问题。
String[] str = new String[16];
str[0] = "1"; str[1] = "en"; str[2] = "2"; str[3] = "3";
System.arraycopy(str, 1, str, 2, 14); System.arraycopy(str, 2, str, 3, 12); for (String s : str) { System.err.println(s); }
复制代码
输出
1enenen23nullnullnullnullnullnullnullnullnullnull
复制代码
解决
既然知道问题是由 System.arraycopy 以及 size 引起的数组复制、容器变大的问题，那就好解决了。
解决重复元素的出现，同时保证下次交换是正确的
保证容器不在变大
所以，第一种解决方案。
List<String> list = new ArrayList<>();
list.add("1"); list.add("en"); list.add("2"); list.add("3");
int size = list.size();
String temp1;
String temp2;
for (int i = 0; i < size; i++) { if ("en".equals(list.get(i))) { for (int j = i; j < size - 1; j++) { temp1 = list.get(j); temp2 = list.get(j + 1); list.remove(temp1); list.remove(temp2); list.add(j, temp2); list.add(j + 1, temp1);
} break; } }
复制代码
复制多的元素要及时删除，这样可以有效避免 System.arraycopy 复制的时候多出来的元素。
第二种，避免使用到 System.arraycopy 这样的方法，使用 list.set 直接进行交换。
List<String> list = new ArrayList<>();
list.add("1"); list.add("en"); list.add("2"); list.add("3");
int size = list.size();
String temp1;
String temp2;
for (int i = 0; i < size; i++) { if ("en".equals(list.get(i))) { for (int j = i; j < size - 1; j++) { temp1 = list.get(j); temp2 = list.get(j + 1); list.set(j, temp2); list.set(j + 1, temp1);
} break; } }
复制代码
总结一下
感觉看源码还是非常有用，无论是在工作中寻找 BUG 的产生还是解决 BUG 等问题。
另外感觉自己对 JDK 代码还不是很熟悉，应该把常用容器的源码都读一下，在使用的时候，可以避免很多坑。
声明
作者: Sinsy
本文链接：https://blog.sincehub.cn/2021/01/23/at-arraylist-bubble/
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版 权协议，转载请附上原文声明。
如您有任何商业合作或者授权方面的协商，请给我留言：550569627@qq.com
评论