可变性与不可变性

本文是对MIT讲义Reading 9: Mutability & Immutability的翻译


本文的翻译主要用于我自己的学习,不追求绝对的准确性,但欢迎读者质疑

可变性

有些对象是不可变的,只要被创建,他们的值就不会再变了。另外一些对象是可变的,他们有改变对象的值的方法。

String是不可变类型的一个例子,一个String对象总代表着相同值。StringBuilder是可变类型的一个例子,它有方法去删除字符串的莫部分,或者插入、替换掉某些字符。

因为String是不可变的,只要被创建,一个String就总保持着相同一个值。想要向一个字符串后面添加其他东西,你就必须创建一个新的String对象。

1
2
String s = "a";
s = s.concat("b"); // s+="b" and s=s+"b" also mean the same thing

注意下图,s改变了指向的对象:
reassignment

相比之下,StringBuilder对象是可变的,这个类有改变对象值的方法,而不是返回新的对象。

1
2
StringBuilder sb = new StringBuilder("a");
sb.append("b");

注意下图,sb没有改变指向的对象,而是改变了对象中的值:
mutation

对一个对象只有一个引用时,可变和不可变没有什么区别,但是当对一个对象有两个以上的引用时,事情就不同了。例如,当另一个变量ts指向相同的String对象,另一个变量sbtb指向相同的StringBuilder对象。这时可变对象与不可变对象之间的区别就变得明显了。

1
2
3
4
5
String t = s;
t = t + "c";

StringBuilder tb = sb;
tb.append("c");

string-vs-stringbuilder
这张图说明了对t的改变不影响s,但是对tb的改变却影响sb

但是我们已经有不可变的String类了,为什么还要可变的StringBuilder类呢?一个常见的应用是连接字符串,看下面的代码:

1
2
3
4
String s = "";
for (int i = 0; i < n; ++i) {
s = s + n;
}

这里我们用的是不可变的String,但这造成了很多的临时副本——第一个字符string(“0”)被复制了n次,第二个字符被复制了n-1次,以此类推······它实际复制了O(n^2)次,即使我们只需要连接n个元素。

StringBuilder被设计用来减少复制次数。它利用了一个简单但是有效的数据结构来避免复制,最后你可以用toString()来得到一个String

1
2
3
4
5
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
sb.append(String.valueOf(i));
}
String s = sb.toString();

得到更好的性能是我们用可变对象的原因之一。另一个原因是便于共享,程序的两部分可以通过一个可变的数据结构进行交流。

可变类型的风险

可变类型似乎比不可变类型更强大,但不可变类型更安全、更易于理解、更容易适应改变。
让我们看两个例子:

风险示例#1:传入可变类型

先看一个简单的sum函数:

1
2
3
4
5
6
7
/** @return the sum of the numbers in the list */
public static int sum(List<Integer> list) {
int sum = 0;
for (int x : list)
sum += x;
return sum;
}

假设现在我们需要一个计算所有值绝对值的和的方法,按照DRY(Don’t Repeat Yourself),实现者利用上面的sum()方法写出了以下的代码:

1
2
3
4
5
6
7
/** @return the sum of the absolute values of the numbers in the list */
public static int sumAbsolute(List<Integer> list) {
// let's reuse sum(), because DRY, so first we take absolute values
for (int i = 0; i < list.size(); ++i)
list.set(i, Math.abs(list.get(i)));
return sum(list);
}

注意这个方法直接修改了list。这似乎对于实现者来说是在理的,因为它利用了已存在着的list,如果这个list有上万条项目长,那么我们就省下了开辟一个新的上万条list长的时间和空间。所以这样设计的实现者有两个理由:DRY和性能

但是实际结果却会让调用它的人大跌眼镜,例如:

1
2
3
4
5
6
7
// meanwhile, somewhere else in the code...
public static void main(String[] args) {
// ...
List<Integer> myData = Arrays.asList(-5, -3, -2);
System.out.println(sumAbsolute(myData));
System.out.println(sum(myData));
}

调用sum()的时候不会得到预期的结果。

我们来看一下这里的要点:

  • 传入可变对象是一个潜在的bug。一些程序员可能因为复用性或性能这些好的目的而不经意间改变了那个list,而且这样引起的bug通常很难找到。
  • 这样使得程序不容易被理解,因为我们无法知道main()中的myData会不会被改变。

风险示例#2:返回可变类型

我们来看这样一个例子,Date是一个Java的内置类,它是可变的,假设我们写了下面一个方法来计算春天的第一天:

1
2
3
4
/** @return the first day of spring this year */
public static Date startOfSpring() {
return askGroundhog();
}

这里用了著名的Groundhog算法来计算春天什么时候开始。

客户开始用这个方法,例如,用它来决定什么时候开party:

1
2
3
4
5
// somewhere else in the code...
public static void partyPlanning() {
Date partyDate = startOfSpring();
// ...
}

代码运行的很好,人们也很高兴。但是这个时候,发生了这样两件事:
第一,startOfSpring()意识到每次都要调用askGroundhog()而每次都返回相同的值,这很没必要。所以他重写了startOfSpring()的代码,最多调用一次askGroundhog(),然后将得到的答案缓存起来以备后面使用:

1
2
3
4
5
6
/** @return the first day of spring this year */
public static Date startOfSpring() {
if (groundhogAnswer == null) groundhogAnswer = askGroundhog();
return groundhogAnswer;
}
private static Date groundhogAnswer = null;

第二,一个startOfSpring()的客服觉得一开春太冷了,他决定推后一个月开party:

1
2
3
4
5
6
7
// somewhere else in the code...
public static void partyPlanning() {
// let's have a party one month after spring starts!
Date partyDate = startOfSpring();
partyDate.setMonth(partyDate.getMonth() + 1);
// ... uh-oh. what just happened?
}

现在我们看到了改动后的代码的一些问题,这张快照图显示出了潜在的bug:
risky
快照图显示了groundhogAnswer指向了可变的Date,而此时Date中的月份已经改变了,这就造成了缓存着的groundhogAnswer也就改变了,你无意中将春天开始时间推后了一个月!

解决这个bug的一个简单方法是让startOfSpring()返回groundhog的一个副本:

1
return new Date(groundhogAnswer.getTime());

这种模式就叫做防御性复制(defensive copying),防御性复制意味着partyPlanning可以随意修改startOfSpring()的返回值,而不会有副作用。

别名(aliases)

事实上,当你完全只在一个方法内部使用可变类型,并且只有一个对该可变对象的引用,那么这是完全没有问题的。造成前面的例子出问题的原因是对相同的对象有多个引用,也称为别名(aliases)

回想之前的两个例子:

  • List中,(sumsumAbsolute中的)list和(main中的)myData指向了相同的list。sumAbsolute的程序员想要修改list,而main的程序员却想让list中的值不变。由于存在别名,main的程序员的愿望没有达成。
  • Date中,有两个变量groundhogAnswerpartyDate指向了一个相同的Date对象。这些别名存在于代码中完全不同的部分,
    控制这些不同部分的不同程序员又完全不知道其他人想要做什么。

为可变方法书写规范

在可变方法的规范中加入可变性的说明是很重要的。这有两个例子:
这是一个可变方法的例子:

1
2
3
4
static void sort(List<String> lst)
requires: nothing
effects: puts lst in sorted order, i.e. lst[i] <= lst[j]
for all 0 <= i < j < lst.size()

这是一个不改变参数的方法:

1
2
3
static List<String> toLowerCase(List<String> lst)
requires: nothing
effects: returns a new list t where t[i] = lst[i].toLowerCase()

数组和列表的迭代器

接下来要讨论的一个可变对象是迭代器(iterator)——一个逐步遍历集合元素并逐个返回元素的对象。当你在java中使用for each循环时,其实java就在底层调用迭代器。下面的代码:

1
2
3
4
List<String> lst = ...;
for (String str : lst) {
System.out.println(str);
}

被编译器翻译为:

1
2
3
4
5
6
List<String> lst = ...;
Iterator iter = lst.iterator();
while (iter.hasNext()) {
String str = iter.next();
System.out.println(str);
}

一个迭代器有两个方法:

  • next()返回集合中的下一个元素
  • hasNext()判断是否已到达集合末尾

注意next()方法是一个mutator方法,它不仅返回一个元素,还使迭代器前进一步,所以下次调用next()的时候会返回一个不同的元素。

MyIterator

为了更好的理解迭代器是怎样工作的,我们用一个例子来说明。下面是一个对ArrayList<String>的迭代器的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* A MyIterator is a mutable object that iterates over
* the elements of an ArrayList<String>, from first to last.
* This is just an example to show how an iterator works.
* In practice, you should use the ArrayList's own iterator
* object, returned by its iterator() method.
*/
public class MyIterator {

private final ArrayList<String> list;
private int index;
// list[index] is the next element that will be returned
// by next()
// index == list.size() means no more elements to return

/**
* Make an iterator.
* @param list list to iterate over
*/
public MyIterator(ArrayList<String> list) {
this.list = list;
this.index = 0;
}

/**
* Test whether the iterator has more elements to return.
* @return true if next() will return another element,
* false if all elements have been returned
*/
public boolean hasNext() {
return index < list.size();
}

/**
* Get the next element of the list.
* Requires: hasNext() returns true.
* Modifies: this iterator to advance it to the element
* following the returned element.
* @return next element of the list
*/
public String next() {
final String element = list.get(index);
++index;
return element;
}
}

iterator
上面这个快照图展示了MyIterator对象的典型状态。
注意从list发出的箭头是双线的,这表示listfinal的,意思是这个箭头一旦被画出来就不能改变了。但是它指向的ArrayList对象是可变的,它里面的元素可以被改变,而将list声明为final并不影响这一点。

iterator由于可变性引起的一个问题

假设我们要写这样一个方法:将代号以”6.”开头的课程从list中删掉。我们为它写了下面这样的规范:

1
2
3
4
5
6
7
/**
* Drop all subjects that are from Course 6.
* Modifies subjects list by removing subjects that start with "6."
*
* @param subjects list of MIT subject numbers
*/
public static void dropCourse6(ArrayList<String> subjects)

下面根据测试优先编程的思想,我们设计了一个测试策略来划分输入域,然后选择一些测试用例覆盖所有的分区:

1
2
3
4
5
6
7
8
9
10
11
// Testing strategy:
// subjects.size: 0, 1, n
// contents: no 6.xx, one 6.xx, all 6.xx
// position: 6.xx at start, 6.xx in middle, 6.xx at end

// Test cases:
// [] => []
// ["8.03"] => ["8.03"]
// ["14.03", "9.00", "21L.005"] => ["14.03", "9.00", "21L.005"]
// ["2.001", "6.01", "18.03"] => ["2.001", "18.03"]
// ["6.045", "6.005", "6.813"] => []

然后,我们来实现它:

1
2
3
4
5
6
7
8
9
public static void dropCourse6(ArrayList<String> subjects) {
MyIterator iter = new MyIterator(subjects);
while (iter.hasNext()) {
String subject = iter.next();
if (subject.startsWith("6.")) {
subjects.remove(subject);
}
}
}

现在来运行我们的测试用例,他们生效了!额,但是……最后一个测试用例失败了:

1
2
// dropCourse6(["6.045", "6.005", "6.813"])
// expected [], actual ["6.005"]

注意这并不仅是MyIterator的一个bug,ArrayList内置的iterator也会遇到同样的问题,所以同样的for each循环也会遇到这个问题,只是问题以不同的形式表现出来,如果你用for each循环来写代码的话:

1
2
3
4
5
for (String subject : subjects) {
if (subject.startsWith("6.")) {
subjects.remove(subject);
}
}

那么你会得到一个Concurrent­Modification­Exception
内置的iterator检测到你正在修改它的list,所以他抛出了这个异常。

怎么样来解决这个问题呢?一种方法是用Iteratorremove()方法来代替subjectremove()方法。这样iterator就会正确的调整自己的指针:

1
2
3
4
5
6
7
Iterator iter = subjects.iterator();
while (iter.hasNext()) {
String subject = iter.next();
if (subject.startsWith("6.")) {
iter.remove();
}
}

事实证明,这种实现方式将会更加的有效,因为iter.remove()已经知道要删除元素的位置了,而subjects.remove(subject)每次都要重新搜索想要删除的元素。

所以我们在来看一下这个问题,第一种实现方式,调用subjects.remove()会使ArrayList中的相应元素被删除,所以ArrayList中的元素下标index也就会发生改变,但是迭代器iterator却不知道下标的变化,当第一次调用next()后,它内部的index就会变成1,而此时ArrayList已经变成了[, "6.005", "6.813"],之前下标为0的元素已经被删除了,而之前下标为1的元素现在的下标变成了0,所以迭代器就把它错过了。
而后一种实现方式中,迭代器的iter.remove()会自己调整自己的指针,所以会得出正确的结果。

讲义原文地址

Reading 9: Mutability & Immutability