Why hashcode 31?

前几天被人问到了hashcode如何实现,说实话,真的是没有自己写过,通常情况下都会通过IDE自动生成,惭愧。今天研究了下hashcode的生成原理,首先看一下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;
    }

       核心的算法就是中间的for循环,假如字符串是"abcde",那最终的hash值应该是31(31(31(31a+b) + c) + d) + e,扩号展开为a*31^4+b*31^3+c*31^2+d*31^1+e*31^0,设字符串的长度为n,那最终的计算公式为:s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1],这实际上就是31进制数转成10进制数的算法。那为什么要用31作为基数呢?        我想可能有几点原因:31首先是一个素数,与素数相乘运算后,能降低hashcode碰撞的概率;31其次是一个特殊的值(32-1),32的二进制是100000,31的二进制是011111,31*N = N << 5 - N,运算速度会快。        普通类覆盖hashCode方法也可以使用类似的算法,如:

@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result
				+ ((firstname == null) ? 0 : firstname.hashCode());
		result = prime * result
				+ ((lastname == null) ? 0 : lastname.hashCode());
		result = prime * result
				+ ((nickname == null) ? 0 : nickname.hashCode());
		return result;
	}

       属性如果是引用类型,要与其hashCode运算,属性如果是byte、short、int类型,要与其值运算,属性如果是float、double、long,要经过特殊运算,可以参考对应封装类的hashCode方法实现。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang中Interface类型详解

文 | Zuozuohao 共 14470 字,阅读需 36 分钟 本文章翻译自《Let's learn Go》的“Interfaces: the awesom...

34110
来自专栏AI科技评论

开发 | TensorFlow全新的数据读取方式:Dataset API入门教程

AI科技评论按:本文作者何之源,该文首发于知乎专栏AI Insight (https://zhuanlan.zhihu.com/ai-insight),AI科技...

3095
来自专栏Golang语言社区

Golang中Interface类型详解

本文章翻译自《Let's learn Go》的“Interfaces: the awesomesauce of Go”一节 原文地址:http://go-boo...

3868
来自专栏柠檬先生

jQuery 效果使用

.hide()   隐藏匹配的元素。   .hide()     这个方法不接受任何参数。   .hide([duration][,comp...

1999
来自专栏挖掘大数据

处理海量数据的10种常见方法

本文将介绍10种处理海量数据问题的常见方法,也可以说是对海量数据的处理方法进行一个简单的总结,希望对你有帮助。

20410
来自专栏AI研习社

TensorFlow全新的数据读取方式:Dataset API入门教程

Dataset API是TensorFlow 1.3版本中引入的一个新的模块,主要服务于数据读取,构建输入数据的pipeline。 此前,在TensorFlow...

3393
来自专栏海天一树

小朋友学C++(10):子类构造函数调用父类构造函数

从哲学层面来看,子类会继承父类除private以外的所有成员。 因为构造函数是公有的,所以理所当然地会被子类继承。 程序1: #include <iostrea...

2686
来自专栏xingoo, 一个梦想做发明家的程序员

二分搜索技术

分治法的基本思想:将一个规模为n的问题,分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归的解这些子问题,然后将各个子问题的解合并得到原问题的解...

1829
来自专栏Golang语言社区

Golang中Interface类型详解

本文章翻译自《Let's learn Go》的“Interfaces: the awesomesauce of Go”一节 原文地址:http://go-bo...

3427
来自专栏数据结构与算法

1570. [POJ3461]乌力波

★☆   输入文件:oulipo.in   输出文件:oulipo.out 简单对比 时间限制:1 s   内存限制:256 MB 【题目描述】 法国作家乔治·...

2857

扫码关注云+社区