Java数据结构里究竟存什么？

大家都知道，为了便于编程使用，Java语言本身已经提供了常用的几乎所有数据结构的标准实现。在之前教学中，我遇到了一个很有意思的问题，即Java的数据结构里，到底储存的是value呢，还是reference呢？如果类比到文学领域，这个问题类同于莎翁笔下哈姆雷特的名句“生存还是毁灭”(To be, or not to be)。

在此我做简单的解释。电脑程序运行的时候，各种数据变量以及程序本身都是储存在内存里的。那么对于变量，也就是Java的object，可以理解成是一小块已经分配的带有有意义数据的内存，我们称之为value。另一方面，计算机系统里通过所谓的address来唯一确定内存数据的位置，那么指向某个Java object的address本身，我们称之为reference。value所占用的内存空间可大可小，而reference一般就是一点点——如果是32位操作系统，一般就是32位即4个byte；如果是64位操作系统则是8个byte。考虑到现在电脑文件基本都以kilobyte为最小单位，reference真心不算什么事。用一个比方来说，value可以看成是图书馆里的一本本书，而reference则是每本书对应的统一编号。知道编号的话，很容易按图索骥把书找到，但是光有编号而人不在图书馆是没有任何用处的。

相对应的，编程语言的数据结构在理论上既可以储存value也可以储存reference，参见下图：

诸如C++之类的计算机语言可以由程序员精确指定数据结构是储存value还是储存reference。某些语言则压根没有reference这种东西，因而数据结构只能存value。那么Java是个什么情况呢？下图比较了两种不同数据结构储存方案在进行插入操作时的区别：

由图可见，对于value的存储方式，编程语言会自动将value复制一份全新的拷贝并加入到数据结构中。所以数据结构中的新成员和原始的value本质上是两个一模一样但独立的个体。对于reference的存储方式，编程语言在数据结构中仅存储value所对应的reference的副本。value方式很显然是最直观的，而且这样数据结构中的成员都可以在后续执行的过程中不受外界干扰。问题在于如果value本身是一个很占内存的object的话，数据结构的容器也会跟着迅速膨胀起来，不是特别经济，执行遍历查找等操作时效率也会受到影响。reference方式能够避免value方式的所有缺陷，但是与此同时会带来一个很意外的问题——如果程序其他地方还存在有对于新成员的reference的话，不用直接操作数据结构也能更改新成员的内在状态。实际软件开发过程中由此产生的问题可能需要耗费数小时乃至数天的调试才能被发现并根除。

先看一个错误的示例，在这里我们使用Java最基本的数据结构Stack，然后把String作为储存对象。

VerifyDSWrong.java

import java.util.Stack;

public class VerifyDSWrong{     
  public static void main(String arg[]){
    Stack<String> test=new Stack<String>();
    String myTest="Hello";
    test.push(myTest);
    System.out.println(test.peek());
    myTest=myTest.toUpperCase();
    System.out.println(myTest);
    System.out.println(test.peek());
  }
}

Hello
HELLO
Hello

这就奇怪了，好像数据结构中的内容并没有受到外界的影响？

但这其实是一个错觉。Java中的String与C和C++的对应物不同，具有immutable的特性，通俗的解释就是String的内容是永恒不变的。那你可能会问，明明我们这边toUpperCase()成功了啊？事实上toUpperCase()并不是修改原本的String，而是直接生成了一个新的，并将myTest中存储的String reference替换掉。但是Stack test顶部存储的reference还是指向最初的那个String。

到这边你可能明白了，但是还会多问一句，如果myTest更新了，而又没有Stack test的话，原来的那个String会发生什么呢？答案是Java的garbage collector会追踪所有的String乃至所有的Object是否有合适的reference，如果没有reference的话，表示程序不可能再用到这个Object了，Java就会自动清理它并释放内存资源。

我们先自己写了一个简单的自制TestClass，用modify()来改变状态a。注意我们其实实现了parent class Object的toString() method。一个小贴士是当某个Java class没有extends任何parent class时，它还是有默认的根parent class Object，全称java.lang.Object。

TestClass.java

public class TestClass{
    private Integer a=0;
    
    public void modify(int input){
        a=input;
    }
    
    public String toString(){
        return a.toString();
    }
}

这个则是正确的示例：

VerifyDS.java

import java.util.Stack;

public class VerifyDS{      
    public static void main(String arg[]){
        Stack test=new Stack();
        TestClass myTest=new TestClass();
        test.push(myTest);
        System.out.println(test.peek());
        myTest.modify(5);
        System.out.println(myTest);
        System.out.println(test.peek());
    }
}

0
5
5

从输出的结果看，确实是reference的存储方式，因为我们只modify() myTest，而test的输出也一并发生了变化。注意因为我们实现了toString()，所以可以直接println()，这是Java的优雅之处。

这里是简明扼要的结论。为了防止造诣不深的程序员出错，Java弱化了reference的概念，也不直接提供能轻易操作reference的工具。但考虑到语言设计的优雅性和实际程序时空性能，Java数据结构里储存的还是object的reference，而非把value给复制一遍或者换言之clone() object。