查看: 127|回复: 0

科普:String hashCode 方法为什么选择数字31作为乘子

[复制链接]

该用户从未签到

发表于 2019-11-4 10:38:39 | 显示全部楼层 |阅读模式
1. 背景

某天,我在写代码的时候,偶然中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现,发现并不是很复杂。但是我从源码中发现了一个希奇的数字,也就是本文的主角31。这个数字居然不是用常量声明的,所以没法从字面意思上推断这个数字的用途。后来带着疑问和好奇心,到网上去找资料查询一下。在看完资料后,默默的感叹了一句,原来是这样啊。那么到底是哪样呢?在接下来章节里,请大家带着好奇心和我揭开数字31的用途之谜。
2. 选择数字31的缘故原由

在详细说明 String hashCode 方法选择数字31的作为乘子的缘故原由之前,我们先来看看 String hashCode 方法是怎样实现的,如下:
  1. 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 hashCode 方法的实现,是不是很简单。实际上 hashCode 方法核心的计算逻辑只有三行,也就是代码中的 for 循环。我们可以由上面的 for 循环推导出一个计算公式,hashCode 方法注释中已经给出。如下:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
这里说明一下,上面的 s 数组即源码中的 val 数组,是 String 内部维护的一个 char 类型数组。这里我来简单推导一下这个公式:
  1. 假设 n=3i=0 -> h = 31 * 0 + val[0]i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]       h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]       h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]
复制代码
上面的公式包括公式的推导并不是本文的重点,大家了解了解即可。接下来来说说本文的重点,即选择31的理由。从网上的资料来看,一般有如下两个缘故原由:
第一,31是一个不大不小的质数,是作为 hashCode 乘子的优选质数之一。另外一些相近的质数,比如37、41、43等等,也都是不错的选择。那么为啥偏偏选中了31呢?请看第二个缘故原由。

第二、31可以被 JVM 优化,31 * i = (i

相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表