subList的陷阱
今天在写华为笔试题的时候遇到了一个特别的错误，因为报错的地方并不是真正出现问题的点，因此解决这个问题花了特别长的时间。
我们可以把这个错误简化一下，看看到底是怎么样一个问题。
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
List<Integer> subList = list.subList(1,3);
System.out.println(list);
System.out.println(subList);
list.remove(1);
System.out.println(list);
System.out.println(subList);
}
}
// [1, 2, 3]
// [2, 3]
// [1, 3]
// Exception in thread "main" java.util.ConcurrentModificationException
// at com.company.Main4.main(Main4.java:19)
在这个example里，我们先新建了一个ArrayList，然后将它的一个subList取出来放在一个新的List引用中。这个时候，如果删掉原来List中的一个元素，再打印这两个List会发生什么？
我期望的结果是List和subList引用互不干扰，也就是一下输出。
[1, 2, 3]
[2, 3]
[1, 3]
[2, 3]
[1, 2, 3]
[2, 3]
[1, 3]
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayListSubList.listIterator(ArrayList.java:1099)
at java.util.AbstractList.listIterator(AbstractList.java:299)
at java.util.ArrayList$SubList.iterator(ArrayList.java:1095)
at java.util.AbstractCollection.toString(AbstractCollection.java:454)
at java.lang.String.valueOf(String.java:2994)
at java.io.PrintStream.println(PrintStream.java:821)
at com.company.Main4.main(Main4.java:19)
恩？为什么报错的是Line 19？Line 19应该只是一条输出而已啊喂。（Line 19也就是System.out.println(subList);这一行)
如果回到subList的本质来回答这个问题，我们会发现subList返回的只是ArrayList中的一个子类（就叫subList），subList对象用的还是List里的东西，所以修改原来的list之后会导致ArrayList中的一个方法checkForComodification产生异常(ConcurrentModificationException)。
实际上，在很多ArrayList的操作里都用到了checkForComodification这个方法，比如调用size，调用add等。如果这个方法发现List和SubList的modCount不相等就会报错。这个方法的内容如下所示
final void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
如果修改了原list的值依然要使用subList，那么两者的modCount就会不同，从而让这个方法抛出ConcurrentModificationException异常。
如此一来，我们明白，开头的Example中之所以打印会出问题，是因为subList的toString方法用到了iterator。而iterator会调用checkForComodification方法，导致报错。
如何避免这个问题呢？List经过subList后如果要修改List，一定要将sublist赋给一个新的变量。就像下面这样。
List<Integer> subList = new ArrayList<>(list.subList(5, list.size()));
正所谓失之毫厘，谬之千里。一个小小的细节没有注意到就会让所有的努力付诸东流。
多线程下的ConcurrentModificationException解决办法
不仅仅是在单线程下使用subList会产生ConcurrentModificationException，在多线程环境下，如果不同的线程修改（增删改）了list的值，也会产生ConcurrentModificationException。这就是fail-fast机制。
通过使用CopyOnWriterArrayList可以完全避免ConcurrentModificationException。因为CopyOnWriterArrayList的实现基本等同于ArrayList，并且CopyOnWriterArrayList 任何对 array 在结构上有所改变的操作（add、remove、clear 等），CopyOnWriterArrayList 都会 copy 现有的数据，再在 copy 的数据上修改，这样就不会影响 COWIterator 中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的 copy 也是相当有损耗的。
subString的内存泄露
由这个问题出发，我联想到subString的实现在Java 6之前也是类似的，它并不把原String的内存回收，而是把原String的几个参数调整一下然后直接返回。
Java 6中subString是这么实现的：
public String substring(int beginIndex, int endIndex) {
if (beginIndex < 0) {
throw new StringIndexOutOfBoundsException(beginIndex);
}
if (endIndex > count) {
throw new StringIndexOutOfBoundsException(endIndex);
}
if (beginIndex > endIndex) {
throw new StringIndexOutOfBoundsException(endIndex - beginIndex);
}
return ((beginIndex == 0) && (endIndex == count)) ? this :
new String(offset + beginIndex, endIndex - beginIndex, value);
}
// String的构造方法，可以看到如果用Java 6的subString，value是不变的
String(int offset, int count, char value[]) {
this.value = value;
this.offset = offset;
this.count = count;
}
Java 6的subString方法的功能是生成一个新的offset和count，返回的新String仍然用的是原来的value，并没有为了新的String创建一个新的value。
也就是说，原来的String有多大，新的String也就有多大。在这样的情况下，假设有String a和subString之后的String b，如果b的生命周期要长于a或者手动设置a为null，当垃圾回收进行后，a被回收掉，b没有回收掉，那么内存占用依旧存在，因为b持有这个字符数组的引用。
在Java 7中彻底修复了这个问题。substring不再是共享一个字符数组，对于子字符串（自身除外）采用了数组复制实现单个字符串持有自己的应该拥有的内容。
public String substring(int beginIndex, int endIndex) {
if (beginIndex < 0) {
throw new StringIndexOutOfBoundsException(beginIndex);
}
if (endIndex > value.length) {
throw new StringIndexOutOfBoundsException(endIndex);
}
int subLen = endIndex - beginIndex;
if (subLen < 0) {
throw new StringIndexOutOfBoundsException(subLen);
}
return ((beginIndex == 0) && (endIndex == value.length)) ? this
: new String(value, beginIndex, subLen);
}
public String(char value[], int offset, int count) {
if (offset < 0) {
throw new StringIndexOutOfBoundsException(offset);
}
if (count < 0) {
throw new StringIndexOutOfBoundsException(count);
}
// Note: offset or count might be near -1>>>1.
if (offset > value.length - count) {
throw new StringIndexOutOfBoundsException(offset + count);
}
this.value = Arrays.copyOfRange(value, offset, offset+count);
}
Java 6的substring实现和subList有异曲同工的地方，他们持有的都是原来string或list的一个引用。不过substring由于常量池的存在，所以不存在修改value的问题，也就不会出现subList中会出现的ConcurrentModificationException。
Java 7中的substring改为了复制一遍value到一个新的String中返回，思路和本文前面讨论到 如何避免subList报错 一样。相比之下，Java 6中substring不需要重新申请内存，速度更快，但是Java 7中的substring可靠性更高。
附：以下是华为笔试题的代码
import java.util.*;
class Tree{
public String content;
public List<Tree> children = new ArrayList<>();
public Tree(String content){
this.content = content;
}
public void printTree(){
System.out.print(content + " ");
for (int i = 0; i < children.size(); i++) {
children.get(i).printTree();
}
}
public Tree searchForContent(String s){
if (content.equals(s)){
return this;
}
for (int i = 0; i < children.size(); i++) {
Tree tree;
if ((tree = children.get(i).searchForContent(s))!=null){
return tree;
}
}
return null;
}
}
public class Main3 {
// a b;a c;b e;e b;c d;d a;
public static void printExpand(Set<String> set, Tree tree){
if (!set.contains(tree.content)){
System.out.print(tree.content + " ");
set.add(tree.content);
}
for (int i = 0; i < tree.children.size(); i++) {
printExpand(set, tree.children.get(i));
}
}
public static List<List<String>> printCircle(List<String> path, Tree tree, List<List<String>> circles){
if (path.contains(tree.content)){
path.add(tree.content);
circles.add(new ArrayList<>(path.subList(path.indexOf(tree.content), path.size()))); // 就是这一句
} else {
path.add(tree.content);
}
for (int i = 0; i < tree.children.size(); i++) {
printCircle(path, tree.children.get(i), circles);
}
path.remove(tree.content);
return circles;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String line = sc.nextLine();
String[] line_array = line.split(";");
String[] first = line_array[0].split(" ");
Tree root = new Tree(first[0]);
root.children.add(new Tree(first[1]));
for (int i = 1; i < line_array.length; i++) {
String[] str_array = line_array[i].split(" ");
root.searchForContent(str_array[0]).children.add(new Tree(str_array[1]));
}
//root.printTree();
Set<String> set = new HashSet<>();
System.out.print("EXPAND:");
printExpand(set, root);
System.out.println();
System.out.print("CIRCLE:");
List<String> path = new ArrayList<>();
List<List<String>> circles = new ArrayList<>();
circles = printCircle(path, root, circles);
Iterator<List<String>> iterator = circles.iterator();
while(iterator.hasNext()){
List<String> list_path = iterator.next();
Iterator<String> it = list_path.iterator();
while (it.hasNext()){
String out = it.next();
if (!it.hasNext()){
break;
}
System.out.print(out + " ");
}
System.out.print(list_path.get(list_path.size()-1));
if (iterator.hasNext()){
System.out.print(";");
} else {
System.out.println();
}
}
}
}
}``
网友评论