Java数据结构与面向对象

发表于

摘要

  • 数据结构是什么，为什么需要数据结构
  • 数据结构的发展历史以及与算法的关系
  • Java数据结构的实现机制
  • Java数据结构——面向对象之技术必然性与偶然性
  • Java数据结构的字节码格式分析
  • 大端与小端

算法和数据结构是计算机的基础，而Java虚拟机的执行引擎框架仍然以此为基础。如同物理CPU能够识别字节码和存储单元，C语言编译器能够识别使用C定义的结构体一样，JVM执行引擎同样能够识别Java语言中的基础数据结构——类型，所以Java语言里的数据结构对于JVM执行引擎而言非常重要。

算法是指令驱动的，一条条指令按照一定的顺序执行，彼此协作，最终实现某种特定的逻辑，便完成了特定的算法。Java程序的算法由Java字节码指令所驱动。而数据结构往往会作为算法的输入、输出和中间产出，即使输出是一个简单的整形数字，也是一种数据结构。

Java类型识别

Java类在编译期生成的字节码有其特定的组织规律，Java虚拟机在加载类时，对编译期生成的字节码信息按照固定的格式进行解析，一步一步解析出字节码中所存储的类型结构信息，从而在运行期完全还原出原始的Java类的全部结构。

  • class字节码概述

    每一个Java类被编译后会生成一个对应的.class字节码文件，下面从几个方面来描述字节码的组成格式。

    • class文件构成基础

      在class字节码文件中，数据都是以二进制流的形式存储。这些字节流之间都严格按照规定的顺序排列，字节之间不存在任何空隙，对于超过8位的数据，将按照大端的顺序存储，即高位字节存储在低的地址上面，而低位字节存储到高地址上面。其实这也是class文件跨平台饿关键，为了class文件在各种异构处理器架构下能够保持统一的存储顺序，虚拟机必须设置统一的存储规范。

    • class文件的10个组成结构

      class字节码文件是采用类似C语言的结构体来存储数据的，主要有两类数据项：无符号数和表。无符号数用来表述数字、索引引用以及字符串等，在.class文件中主要使用的无符号数包括u1、u2、u4和u8，分别表示1字节、2字节、4字节和8字节的无符号数。而表是由多个无符号数以及其他的表组成的复合结构。

      一个class字节码文件主要由以下10部分组成：

      • MagicNumber
      • Version
      • Constant_pool
      • Access_flag
      • This_class
      • Super_class
      • Interfaces
      • Fields
      • Methods
      • Attributes

      这些数据的类型和长度都是不同的，用一个数据结构可以表示如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      ClassFile {
          u4 magic;
        	u2 mijor_version;
          u2 major_version;
        	u2 constant_pool_count;
        	cp_info constant_pool[constant_pool_count - 1];
        	u2 access_flags;
        	u2 this_class;
        	u2 super_class;
        	u2 interfaces_count;
        	u2 interfaces[interfaces_count];
        	u2 fields_count;
        	field_info fields[fields_count];
        	u2 methods_count;
        	methods_info methods[methods_count];
        	u2 attributes_count;
        	attribute_info attributes[attributes_count];
      }

    • class文件中的各组成字段简单说明

      ①MagicNumber

      MagicNumber是用来标志class文件的，位于每一个Java class文件的最前面4个字节，值固定为0xCAFEBABE。虚拟机加载class文件时会检查这4个字节，如果不是0xCAFEBABE，则虚拟机拒绝加载该文件，这样就可以防止加载非class文件而造成虚拟机奔溃。

      ②Version

      Version字段由2个长度都为2字节的字段组成，分别是Major Version和Minor Version，代表当前class文件的主版本和次版本号。随着Java技术的不断发展，Java class会增加一些新的内容来支持Java语言的新特性。同时，不同的虚拟机支持的Java class文件的版本范围是不同的，所以在加载class文件之前可以看看该class文件是否在当前虚拟机的支持范围之内，避免加载不支持的class文件。高版本的JVM可以加载低版本的class，但反之就不行。如果使用低版本的JDK编译Java程序，然后使用高版本的JRE执行class file，能够顺利执行。反之，如果使用高版本的JDK编译Java程序，而使用低版本的JRE执行class file。

      ③常量池

      常量池信息从class文件的第9个字节开始。

      首先是2字节（即第9个和第10个字节）的长度字段constant_pool_count，表明常量池包含了多少个常量。

      接下来的二进制信息描述[constant_pool_count - 1]个常量，常量里放的是字面常量和符号引用。字面常量主要包含文本串以及被声明为final的常量。符号引用包含类和接口的全局限定名、字段的名称和描述符、方法的名称和描述符，因为Java语言在编译的时候没有连接这一步，所以有的引用都是运行时动态加载的，所以就需要把这些引用的信息保存在class文件里。字面常量根据具体的类型分成字符串、整形长整型、浮点型、双精度付浮点型这几种基本类型。符号引用保存的是引用的全局限定名，所以保存的是字符串。

      ④Access_flag

      主要保存当前类的访问权限。

      ⑤This_class

      主要保存当前类的全局限定名在常量池里的索引。

      ⑥Super_class

      主要保存当前类的父类的全局限定名在常量池里的索引。

      ⑦Interfaces

      主要保存当前类实现的接口列表，包含两部分内容：interfaces_count和interfaces[interfaces_count]。interfaces_count指的是当前类实现的接口数目。

      interfaces[]是包含interfaces_count个接口的全局限定名的索引数组。

      ⑧Fields

      主要保存当前类的成员列表，包含两部分的内容：fields_count和fields[fields_count]。

      fields_count是类变量和实例变量的字段的数量的总和。

      fields[]是包含字段详细信息的列表。

      ⑨Methods主要保存当前类的方法列表，包含两部分的内容：methods_count和methods[methods_count]。

      methods_count是该类或者接口显示定义的方法的数量。

      methods[]是包含方法信息的一个详细列表。

      ⑩主要保存当前类attributes列表，包含两部分内容：attributes_count和attributes[attributes_count]。

  • 魔数与JVM内部的int类型

    由于魔数在字节码文件中占4个字节，并且其数据值固定不变，一直都是0xCAFEBABE，因此JVM内部使用u4这种自定义的数据类型存放魔数。u4这种数据类型的定义如下：

    1
    typedef juint u4;

    juint也是自定义类型，但是这种类型是平台相关的，在Linux平台上，juint定义如下：

    1
    typedef uint32_t juint;

    uint32_t仍然是自定义类型，定义如下：

    1
    2
    3
    4
    #ifndef _UINT32_T
    #define _UINT32_T
    typedef unsigned int uint32_t;
    #endif

    由此可知，uint32_t最终所代表的类型是unsigned int，在32位或64位系统平台上，unsigned int都占4字节，正好能够存放下魔数信息。所以，JVM内部的u4数据类型能够存放4字节。而JVM内部除了u4，还定义了另外3中常用的数据类型：

    • u1，该数据类型占1字节，在Linux平台上所代表的C语言类型是unsigned char。
    • u2，该数据类型占2字节，在Linux平台上所代表的C语言类型是unsigned short。
    • u8，该数据类型占8字节，艾Linux平台上所代表的C语言类型是unsigned long。

  • 常量池与JVM内部对象模型

    常量池是Java字节码文件中比较重要的概念，是整个Java类的核心所在，因为常量池中记录了一个Java类的所有成员变量、成员方法和静态变量与静态方法、构造函数等全部信息，包括变量名、方法名、访问标志、类型信息等。

    JVM内部定义了一个C++类型constantPoolOop来记录解析后的常量池信息。constantPoolOop是别名，其原始的类型是constantPoolOopDesc。

    1
    typedef class constantPoolOopDesc* constantPoolOop;

    而事实上，JVM内部为了在运行期描述Java类的类型信息和内部结构，定义了很多以Desc结尾的oop类。

    • oop-class模型

      HotSpot虚拟机在内部使用两组类来表示Java的类和对象。

      ①oop（ordinary object pointer），用于描述对象实例信息。

      ②klass，用来描述Java类，是虚拟机内部Java类型结构的对等体。

      JVM内部定义了各种oop-klass，在JVM看来，不仅Java类是对象，Java方法也是对象，字节码常量池也是对象，一切皆是对象。JVM使用不同的oop-klass模型来表示各种不同的对象，而在技术落地时，这些不同的模型就使用不同的oop类和klass类来表示。由于JVM使用C/C++编写，因此这些oop和klass类便是各种不同的C++类。对于Java类型与实例对象，JVM使用instanceOop和instanceKlass这2个C++类来表示。

      以下是HotSport内部定义的oop大全。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      typedef class oopDesc*                    oop;
      typedef class instanceOopDesc*            instanceOop;
      typedef class methodOopDesc*              methodOop;
      typedef class constMethodOopDesc*         constMethodOop;
      typedef class methodDataOopDesc*          methodDataOop;
      typedef class arrayOopDesc*               arrayOop;
      typedef class objArrayOopDesc*            objArrayOop;
      typedef class typeArrayOopDesc*           typeArrayOop;
      typedef class constantPoolOopDesc*        constantPoolOop;
      typedef class constantPoolCacheOopDesc*   constantPoolCacheOop;
      typedef class klassOopDesc*               klassOop;
      typedef class markOopDesc*                markOop;
      typedef class compiledICHolderOopDesc*    compiledICHolderOop;

      HotSpot使用klass来描述Java得到类型信息。HotSpot定义了如下几种类型信息。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Klass;
      class instanceKlass;
      class instanceMirrorKlass;
      class instanceRefKlass;
      class methodKlass;
      class constMethodKlass;
      class methodDataKlass;
      class klassKlass;
      class instanceKlassKlass;
      class arrayKlassKlass;
      class objArrayKlassKlass;
      class typeArrayKlassKlass;
      class arrayKlass;
      class objArrayKlass;
      class typeArrayKlass;
      class constantPoolKlass;
      class constantPoolCacheKlass;
      class compiledICHolderKlass;

      纵观以上oop和klass体系的定义，可以发现，无论是oop还是klass，基本都被划分为来分别表示instance、method、constantMethod、methodData、array、objArray、constantPool、constantPoolCache、klass、compoiledICHolder这几种模型，这几种模型中的每一种都有一个对应的xxxOopDesc和对应的xxxKlass。通俗而言，这几种模型分别用于描述Java类类型和类型指针、Java方法类型和方法指针、常量池类型及指针、基本数据类型的数组类型及指针、引用类型的数组类型及指针、常量池缓存类型及指针、Java类实例对象类型及指针。

      以下举个栗子来说明oop-klass模型，若Java程序中定义了一个类CalssA，同时程序中有如下代码：

      1
      ClassA a = new ClassA();

      当HotSpot执行到这里时，会先将ClassA这个类型加载到方法区，然后在HotSpot堆中为其实例对象a开辟一块内存空间，存放实例数据。在JVM加载ClassA到方法区时，JVM就会创建一个instanceKlass，instanceKlass中保存了ClassA这个Java类中所定义的一切信息，包括变量、方法、父类、接口、构造函数、属性等，所以instanceKlass就是ClassA这个Java类类型结构的对等体。而instanceOop这个“普通对象指针”对象中包含了一个指针，该指针就指向klassInstance这个实例。在JVM实例化ClassA时，JVM又会创建一个instanceOop，instanceOop便是ClassA对象实例a在内存中的对等体，主要存储ClassA实例对象的成员变量。其中，instanceOop中有一个指针指向instanceKlass，通过这个指针，JVM便可以在运行期获取这个类实例对象的类元信息。

    • oopDesc

      JVM中所有oop对象的老祖宗是oopDesc类，上述列表的所有oopDesc，诸如instanceOopDesc、constantPoolOopDesc、klassOopDesc等，在C++的继承体系中，最终全部都来自顶级的父类oopDesc。Java的面向对象和运行期反射的能力，便是由oopDesc予以体现和支撑。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      class oopDesc {
      	friend class VMStructs;
      private:
        	volatile markOop _mark;
        	union _metadata {
              wideKlassOop _klass; // 宽指针
            	narrowOop _compresses_klass; // 压缩指针
          } _metadata;
        	static BarrierSet* _bs;
      }

      Java类在整个生命周期中，会涉及到线程状态、并发锁、GC分代信息等内部标识，这些标识全都打在_mark变量上。 _metadata用于标识元数据，每一个Java类都会包含一定的变量、方法、父类、所实现的接口等信息，这些均可成为Java类的“元数据”。Java类的结构信息在编译期被编译为字节码格式，JVM则在运行期进一步解析字节码格式，从字节码二进制流中还原出一个Java在源码期间所定义的全部数据结构信息，JVM需要将解析出来的结果保存在内存中，以便在运行期进行各种操作，例如反射，而 _metadata便起到指针的作用，指向Java类的数据结构被解析后所保存的内存位置。

    • Java结构与其他编程语言结构的比较

      当C、C++和Delphi等程序被编译成二进制程序后，原来所定义的高级数据结构都不复存在了，当操作系统加载这些二进制程序时，是不会加载这些语言中所定义的高级数据结构的，宿主机不知道原来定义了哪些数据结构、哪些类，所有的数据结构都被转换为对特定内存段的偏移地址。而JVM虚拟机在加载字节码程序时，会记录字节码中所定义的所有类型的原始信息（元数据），JVM知道程序中包含了哪些类，以及每个类中所关联的字段、方法、父类等信息。这是JVM与操作系统最大的区别所在。

      正因为JVM需要保存字节码中的类元信息，所以JVM最终就自然而然地演化出了oop-klass这种二分模型，klass用于保存类元信息，而oop用于表示JVM所创建的类实例对象。klass信息被保存在perm永久区，而oop则被分配在heap堆区。同时JVM为了支持反射等技术，必须在oop中保存一个指针，用于指向其所属的类型klass，这样Java开发者便能够基于反射技术，在Java程序运行期获取Java的类型信息。

大端与小端

Java是跨平台的语言，并且支持丰富多样的数据类型。但是在不同的平台上，数据在寄存器、内存、磁盘上的存储格式并不相同，准确的说，是数据存储的顺序不同。这种不同的存储顺序衍生了计算机底层的2个概念——大端与小端。

标准的大端和小端的定义如下：

  • 小端就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。
  • 大端就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。

网络字节序，TCP/IP协议中使用的字节序通常称为网路字节序，TCP/IP各层协议将字节序定义为大端。

JVM在解析魔数及Java类的其他结构信息时，均需要读取字节码信息。Java源代码一般由编译器被编译为字节码文件，而Java编译器本身一般也都是用Java语言编写而成的，因此Java编译器在对Java源程序进行语法树分析并将分析结果写入字节码文件时，字节码文件中的信息存储便是大端模式。这种写入文件的顺序不会收到计算机硬件体系到底是大端模式还是小端模式的影响。但是读取字节码文件的是JVM，JVM是由C与C++混合写成的，因此Java字节码文件的写入端与读取端属于两种不同的编程语言，此外，JVM由C和C++编写，而C和C++的大小端模式默认情况下与计算机硬件平台的大小端模式保持一致，因此最终所又完全取决于读取端所在的计算机硬件平台的大小端模式。所以，JVM最终引入了swap_u4()这类相应的函数转换接口。

总结

  • 从程序的角度看，数据结构是若干数据的有机结合，一个数组、一个链表、一个堆/栈都是数据集，这些数据在内存位置上有着紧密的联系，例如，对于数组而言，相邻的两个元素在内存位置上一行也是彼此相邻的；而对于链表，内存空间上未必彼此相连，但是相邻的两个元素中必然有一个元素保存这一个指针指向另一个元素的内存位置。而从人类的角度看，一个特定的数据结构·1可以更好地描述客观世界，例如通过一个Java类可以描述一直猫，一个手机，而通过类的组合则可以描述几乎任何复杂的事物。
  • Java的数据结构的实现机制是，编译时编程字节码，运行期实现。
  • Java编译期不支持数据结构的原因：
    • Java为了实现算法的跨平台性而选择了字节码，数据结构的实现也必须跨平台，而不能直接被编译成机器指令。
    • Java药品实现RTTI，及运行期类型识别。