Java编程:String 类中 hashCode() 方法详解

###hash 的定义
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Java 中 hash 值的含义

  1. hash 值主要是用来在散列存储结构中确定对象的存储地址的,提高对象的查询效率,如HashMap、HashTable等;
  2. 如果两个对象相同,那么这两个对象的 hash 值一定相等;
  3. 如果要重写对象的 equals 方法,那么尽量重写对象的 hashCode 方法;
  4. 两个对象的 hash 值相等,并不一定表示两个对象相同。

String中的 hashCode

在了解了 hash 值的含义后,在进行 hash 计算的时候,我们希望尽量减小生产重复 hash 值的概率,使得数据更离散一些,如果重复 hash 值太多,散列存储结构中同一 hash 值映射的对象也会很多,导致降低查询效率。而且 equals() 计算的准确性也会降低。

接下来分析 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;
}

在介绍 hashCode() 之前,我们先了解一下该方法中使用到的属性。

value:是一个 private final 修饰的 char 数组,String 类是通过该数组来存在字符串的。

private final char value[];

hash:是一个 private 修饰的 int 变量,用来存放 String 对象的 hashCode。

private int hash; 

接下来分析 hashCode() 的实现逻辑如下:

###判定条件分析

如果 hash 值不等于 0,且 value.length 大于 0,则进行 hash 值计算;这里包含两个条件:
第一个判定条件:

h == 0

为什么 h == 0 时进行 hashCode()计算呢?h 是一个 int 类型的值,默认值为 0,因此 0 可以表示可能未执行过 hash 计算,但不能表示一定未执行过 hash 计算,原因是我们现在还不确定 hash 计算后是否会产生 0 值;

执行 hash 计算后,会不会产生值为 0 的 hash呢?根据 hash 的计算逻辑,当 val[0] = 0 时,根据公式 h = 31 * h + val[i]; 进行计算, h 的值等于 0。

val[0] = 0 怎么解释呢?查看 ASCII 表发现, null 的 ASCII 值为 0 。显然 val[0]中永远不可能存放 null,因此 hash 计算后不会产生 0 值, h == 0 可以作为是否进行过 hash 计算的判定条件。

ASCII表

另一个判定条件:

value.length > 0

也就是说,如果字符串的长度为 0 ,不进行 hash 计算。

###计算公式分析

接下来我们来分析 hash 计算公式:

char val[] = value;
for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
}

我们模拟一下 hash 的计算步骤:

String name = "liu";

value = {'l', 'i', 'u'};
hash = 0;
value.length = 3;

//执行逻辑:
val = value;
val[0] = "l";
val[1] = "i";
val[2] = "u";

h = 31 * 0 + l = l;

h = 31 * (31 * 0 + l) + i = 31 * l + i;

h = 31 * (31 * (31 * 0 + l) + i) + u = 31 * 31 * l + 31 * i + u;

推导出的数学公式如下:

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

为什么是 31 呢,为什么不是 32 呢?因为 31 是一个素数。什么是素数,为什么选择素数?

素数又称质数:指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。

根据素数的特性,与素数相乘得到的结果比其他方式更容易产生唯一性,也就是说产生 hash 值重复的概率比较小。

素数有很多,为什么是 31 呢?

31 的二进制为: 11111,占用 5 个二进制位,在进行乘法运算时,可以转换为 (x << 5) - x

这里需要考虑乘法的因素,在 Java 中如果相乘的数字太大会导致内存溢出问题,从而导致数据丢失。

大数相乘会造成内存溢出,17 也是素数,那为什么不是 17 呢?

我也蒙圈了。

关于 31 大致总结一下:

  1. 31 是一个素数,与素数相乘得到的结果比其他方式更容易产生唯一性。
  2. Java 中如果相乘的数字太大会导致内存溢出问题,从而导致数据丢失。

基于以上两方面的考虑这个因子的值。

###参考资料

  1. Why does Java’s hashCode() in String use 31 as a multiplier
  2. 为什么在定义hashcode时要使用31这个数呢?
  3. 关于hashcode 里面 使用31 系数的问题
  • 39
    点赞
  • 77
    收藏
    觉得还不错? 一键收藏
  • 9
    评论
Java中,hashCode()是Object类的一个方法,返回对象的哈希码。哈希码是由对象的存储地址或者其他信息计算得到的一个int类型的整数。 在Java中,哈希码经常被用来实现数据结构中的散列表。在散列表中,每个对象都有一个对应的哈希码,通过哈希码可以快速定位到对象存储的位置,从而实现快速的查找、插入和删除等操作。 Java中的hashCode()方法的默认实现是返回对象的存储地址的一个int类型的整数表示,即对象的内存地址。但是,不同的JVM实现可能会有不同的实现方式。 在实际开发中,我们可以根据对象的属性计算哈希码,以实现更好的散列表性能。具体来说,我们需要注意以下几点: 1. hashCode()方法的返回值应该尽可能地分散,避免不同的对象产生相同的哈希码。这可以通过使用对象的不同属性进行计算来实现。 2. 如果两个对象的equals()方法返回true,那么它们的hashCode()方法应该返回相同的值。这可以确保这两个对象在散列表中的位置是相同的。 3. hashCode()方法的返回值应该在对象的生命周期中保持不变。如果对象的属性发生变化,那么它的哈希码也应该发生变化。 总之,hashCode()方法Java中是非常重要的一个方法,我们可以根据对象的属性计算哈希码,以实现更好的散列表性能。同时,我们需要注意hashCode()方法实现要尽可能地分散,避免不同的对象产生相同的哈希码,同时也要保证hashCode()方法的返回值在对象的生命周期中保持不变。

“相关推荐”对你有帮助么?

  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
提交
评论 9
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值