Java基础系列之数据结构和运算

导语

初遇Java之后，我们对Java的历史、特征以及垃圾回收机制有了初步认识，接下来我们需要了解下数据结构和运算。程序是什么？就是帮人类干事情的工具（程序员就是开发这个工具的人！）。程序的组成是什么呢？我的理解是数据结构和算法，这里我们不谈算法那么高大上的东西只谈基本运算，毕竟单讲算法就能出一本很厚很厚的书了。

数据结构

前面我们说到，Java是一门面向对象的语言。有人说过这么一句话，“万物皆对象”，其实这也不绝对。Java有8种基本数据类型便不算对象，我们先说说这八种基本数据类型吧。

整型
- byte 在内存中占8位，取值-128 ~127 即 ( $-2^7$ ) ~ ( $2^7-1$ )
- short 在内存中占16位，取值 -32768~32767 即（ $-2^{15}$ ）~ ( $2^{15}-1$ )
- int 在内存中占32位，取值（ $-2^{31}$ ）~ ( $2^{31}-1$ )
- long 在内存中占64位，取值（ $-2^{63}$ ）~ ( $2^{63}-1$ )
浮点型
- float 32位单精度浮点数，最多存储4个字节
- double 64位双精度浮点数，最多存储8个字节
字符型 char
布尔型 boolean 取值true,false
说完基本数据类型，我们再谈谈一个新概念，直接量。直接量通常有三种类型：基本类型、字符串类型、null。基本类型我们刚才已经说过了就是上面的八位，那么字符串类型呢？就是java.lang.String这个类的类型，这是个特殊的类，用来存储字符串。
String类型的特点：字符串直接量不能赋值给其他类型如int,long。这和null类型恰恰相反，null类型可以直接复制任何引用类型和其他基本类型（除了boolean类型）。关于String字符串还有一点需要指出，当程序第一次使用时，JVM会使用常量池来维护这个直接量。当再次使用的时候，Java会直接取常量池中的字符串。
引用数据类型 Date date = new Date(),其中date就是个引用数据类型，这个会在后续的面向对象章节进行详细介绍。

运算

什么是运算？小学生都知道的加、减、乘、除？没错！就是这些，然而，程序执行加、减、乘、除却是一件很费劲的事情，这就引出了我们的位运算。
我们知道，计算机数字系统是由0和1组成的，即二进制。非0即1，逢2进1，因此处理位运算效率会更高。
目前Java支持的位运算有7个，它们分别是：与、或、非、异或、左移、右移、无符号右移。

按位与（&）
System.out.print(5 & 9),我的得到的结果是1.具体运算如下
$\frac{0101}{1001}=0001$
运算规则是同1为1，非1为0
这里有一个经典算法~求一个整数的奇偶：

//我们知道，偶数是能被2整除，那么它的二进制表示最后一位一定是0
//根据与运算，同1为1，非1为0，那么一个一个二进制数和1进行与运算就能获得最后一位值了
int i;
return (i & 1)==0；//偶数

按位或（|）
System.out.print(5 | 9) 运算结果是13，具体运算如下
$\frac{0101}{1001}=1101$
运算规则：有1为1，无1为0
非（~）
System.out.print(~5) 运算结果是：-6

5的原码：0000 0101
~5 就是：1111 1010
由于这是一个负数，这显示的是它的补码，我们先求得它的反码，即补码-1那就是：
1111 1001
然后翻转过来，高位取1即：
1000 0110
得到结果是-6

这里有几个概念：原码、反码、补码。
正数的原码、补码、反码相同
负数的反码是其的绝对值按位求反
负数的补码等于其反码的尾数加1

按位异或（^）
System.out.print(5 ^ 9) 运算结果是12，具体运算如下
$\frac{0101}{1001}=1100$
运算规则：同假异真，就是说相同为0，不同为1
左移（<<）
System.out.print(4<<1) 运算结果是8，运算如下

4: 0100
8: 1000 (0100左移一位后得到01000，舍弃高位的0即1000)

右移（>>）
System.out.print(4>>1)运算结果是2

4: 0100
2: 0010 (0100右移一位后得到0010，舍弃高位的0即10)

无符号右移（>>>）
System.out.print(-5>>>2)结果是1073741822

-5的原码： 1000 0101
-5的补码： 1111 1011 
无符号右移后：0011...1111 1110(中间省略掉20个1)
这个应该是2的30次方减去2就是我们的运算结果

这个计算的原因是-5默认为int类型32位，有兴趣可以试试-5L（long类型）无符号右移2，会得到一个更大的值。

这些运算是计算机底层的运算，比如说程序5*2，我们写成5<<1效率会更高些。
除了位运算，我们比较常用的还有如=(赋值)运算，比较运算（>,<,==,!=）,逻辑运算（&&，|，！，^）,三目运算（? :）等。

Java也提供了加减乘除的算术运算，但是需要注意的是对于double和float浮点型运算时可能会失去精度，如1.2+1.9,得到的结果是3.0999999999999996,不必惊讶，不止Java，我们在谷歌的console中执行（JavaScript）,也是得到了这个结果。很多中语言都存在这个问题。为了更为精确的计算，Java提供了一个java.math包，专门作为算术计算的。上面这个我们换成BigDecimal.valueOf(1.2).add(BigDecimal.valueOf(1.9))就没有这个问题了。需要注意的是，这里不要使用BigDecimal的double类型构造器创建对象，否则还是会出现精度问题

再谈String

String对象可谓是面试官的宠儿，各种题目层出不穷，我们这里谈谈String对象。首先我们看下String对象在jdk源码的样子

image.png

由于篇幅有限，我们的图上只能看到类的修饰信息，看不到Java开发人员写的注释，我这里可以把一些关键信息贴出来下。

The  class represents character strings. 
All string literals in Java programs, such as  "abc", are
 implemented as instances of this class.
Strings are constant; their values cannot be changed after they
are created. String buffers support mutable strings.
Because String objects are immutable they can be shared.

不难看出，String是一个字符串对象，代表所有的字符串实例，创建后不能修改，所以可以共享。上面我们也说过，String对象赋值后，JVM会将该字符串缓存到常量池中，当下次使用的时候，直接从常量池获取。

String a = "helloworld";
String b = "hello"+"world";
String c = new String("helloworld");

这里面a==b，但是a！=c（这个比较容易理解，a为字符串直接量，c为字符串对象的地址）。我们将以上代码编译，打开class文件，发现结果是

image.png

我们可以这样理解，当编译器能确定字符串的时候，系统不会产生hello和 world的备份，直接产生helloworld，如果我们把hello放在一个变量e里面，然后将b改成String b = e+"world"; 这个时候编译结果就不一样了，a==b返回的就是false了。

问题升级

        String str2 = new String("str")+new String("01");
        str2.intern();
        String str1 = "str01";
        System.out.println(str2==str1);

首先我们了解下intern()方法，看源码解释：

Returns a canonical representation for the string object.
A pool of strings, initially empty, is maintained privately by the class
When the intern method is invoked,
 if the pool already contains a string equal to this {@code String} object as determined by the {@link #equals(Object)} method, then the string from the pool is returned. Otherwise, this {@code String} object is added to the pool and a reference to this {@code String} object is returned.

这个方法返回的是字符串的规范化形式（其实就是直接量），根据equals方法判断常量池中是否存在这个字符串，如果存在则，返回对象的引用，不存在，先将字符串缓存到常量池中然后返回该对象的引用。
jdk1.6中常量池在永久代，如果字符串在常量池中找不到会将字符串拷贝到常量池中。所以str2指向的应该还是原字符串，常量池中的是拷贝。str1指向的是常量池中的拷贝，所以返回false。
jdk1.7以上版本，（jdk1.8干脆常量池移到了堆中），如果字符串在常量池中找不到不再拷贝到常量池中，而会重新生成一个对原字符串的引用，因此，str2指向的就是原字符串，而str1指向的也是原字符串，因此，返回true。

尾声

本章节，我们了解了Java的基本数据类型和引用类型（一笔带过，面向对象的时候着重提及）和一些常用的运算。要知道，早期的计算机功能单一，只有计算功能，因此运算是最为核心的一块功能（虽然国内Java开发人员对于位运算并不是很熟练）。后面我们又提及了String类，分析了String类的特殊性，和常见的一些面试题，这些面试题其实都是基于Java内存模型的，需要多JVM较为深入才能理解，而不是记下答案就能应付过去的。下一个章节是面向对象，那个时候我们根据面向对象的思想再谈数据结构，再见。