String源码分析(1)--哈希篇

小鱼儿 2022-01-07 02:43 115阅读 0赞

> 本文基于JDK1.8，首发于公众号：**Plus技术栈**

让我们从一段代码开始

System.out.println("a" + "b" == "ab");
    System.out.println(new String("ab") == "ab");

上述代码中，第一行结果为True，第二行结果为False。两者结果不同的原因在于Java中的==符号判断的是对象是否相等，其实质上是比较两者的内存地址，很显然第一行两边指向同一对象，而第二行指向不同对象。

我们都知道String中判断字符串的字面值是否相等要用equals()方法而不是==，那么String类中equals()究竟是如何实现的呢？

String类会在后续文章中分为几个篇章来讲。本篇文章中主要深入String类中有关哈希的部分，主要有以下几个要点：

*  equals()方法的实现
 *  哈希值、字面值与内存地址之间的关系
 *  哈希碰撞与生日攻击

## equals()方法的实现 ##

**equals的实现**

String类属于“值类“。程序员在比较字符串时，希望知道它们在逻辑上是否相等，而不是想了解它们是否指向同一个对象.

值类仅仅是一个表示值的类，具有自己特有的“逻辑相等“概念（不同于对象等同的概念），因此为了满足比较的需求，String类需要覆盖Object类的equals()方法。

> 每个值至多只存在一个对象的“值类”不需要覆盖equals方法。如枚举类型

String的equals()实现如下：

public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

逻辑很简单，如果比较的两个字符串指向同一对象或者每个位置上的字符相等，则返回true。以上实现遵守了Object的规范\[JavaSE6\]：

*  自反性。对于任何非null的引用值x，x.equals(x)必须返回true。
 *  对称性。对于任何非null的引用值x和y，当且仅当y.equals(x)返回true时，x.equals(y)必须返回true。
 *  传递性。对于任何非null的引用值x、y和z，如果x.equals(y)返回true，并且y.equals(z)也返回true，那么x.equals(z)d也必须返回true。
 *  一致性。对于任何非null的引用值x和y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false

好吧，以上4条规范又让我想起大学被数学分析支配的恐惧。虽然恐惧，但是我们不能忽视这四条规定，否则我们的程序可能会莫名其妙的崩溃。

**hashcode的实现**

那么，在覆盖了Object.equals()方法之后是否就可以进行比较了呢？回答当然是不！

> 覆盖equals时总要覆盖hashCode

经常看源码的同学会发现，很多类中都有hash相关的变量，本篇文章涉及的String类中也有hashcode()方法，那么哈希到底是什么呢？

所谓哈希(hash)，**就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")**。它是软件常见运算之一。如果我们在覆盖了equals()方法之后没有覆盖hashcode()将会导致String类无法结合所有基于散列的集合一起正常运作，这样的集合包括HashMap、HashSet和Hashtable。

无法运作的原因在于我们违反了一条关键约定：**相等的对象必须具有相等的散列码(hash code)**。

一起看看String类中的hashcode()方法：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
        hash = h;
        }
        return h;
    }

一个String实例的hash值只与其内容有关。从代码实现来看，String类计算哈希值实际上就是通过公式(s代表字符串，n代表字符串长度)：

s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]

计算而来，即对字符串的每个取31的n-1次幂并累加。那么这个31是怎么来的呢

在Java Effective中有提及：

> 之所以选择31，是因为它是一个奇素数。如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算。使用素数的好处并不明显，但是习惯上都使用素数来计算散列结果。31有个很好的特性。即用移位和减法来代替乘法，可以得到更好的性能：31 \* i == (i << 5) - i。现代的VM可以自动完成这种优化。

一个好的散列函数通常倾向于“**为不相等的对象产生不相等的散列码**“。理想情况下，散列函数应该把集合中不相等的实例均匀地分布到所有可能的散列值上。

31是一个奇素数，如果使用非奇素数，非奇素数代表着乘以偶数会导致较少的位包含“变化”信息，即若低位变为零，乘完之后还是零。用偶数会失去一点“可变性”。结果是可能的哈希值分布较差。

除此之外。31可以保证比较少的哈希碰撞， 31i=32i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。

## 哈希值、字面值与内存地址之间的关系 ##

在hashcode()函数的源码实现可以看到，一个字符串实例的hash值仅与其内容有关。那么是否可以理解内容相同的两个字符串的哈希值一定相等呢？请看以下代码：

int a = "Aa".hashCode(); int b = "BB".hashCode();

a与b的值相等，都是2112。上面说到，哈希值就是不同的输入映射成独一无二的、固定长度的值。如果不同的输入得到了相同的哈希值，就发生了“**哈希碰撞**“(collision)。

像上面这种情况就发生了哈希碰撞，除了这种简单字符串之外，"柳柴"与"柴柕"，"志捘"与"崇몈"也会导致碰撞。两者的hashcode值分别为851553和786017。

我们可以总结一下：

*  哈希值相同的字符串，字面值不一定相同。
 *  字面值相同的字符串，哈希值一定相同。
 *  字面值相同的字符串，内存地址不一定相同。

## 哈希碰撞和与生日攻击 ##

**防止哈希碰撞**