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 条评论
登录 后参与评论

相关文章

来自专栏算法channel

Numpy|需要信手拈来的功能

这是一篇Numpy中经常使用的API的不完全总结,欢迎补充和指导。 01 类型转化 凡是使用Numpy的小伙伴,无不遇到类型转化这个问题,并且经常需要通过调试...

3073
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

37710
来自专栏青青天空树

取随机数

  常用于去随机数的函数为rand()(在stdlib.h头文件中,不同的编译器可能有不同),但是实际在使用这个函数时却发现每次程序运行产生的数都是一样的,这是...

812
来自专栏我是攻城师

在Scala里面如何使用正则处理数据

2825
来自专栏程序员互动联盟

【编程基础】C++ Primer快速学习之二:输入与输出

什么是输入输出,即Input-Output,缩写是很装B的IO?请看经典民间解释: C++语言的输入输出是指信息从外部输入设备(如键盘、磁盘等)向计算机内部(内...

3247
来自专栏深度学习之tensorflow实战篇

Python中的random模块用于生成随机数

Python中的random模块用于生成随机数。下面介绍一下random模块中最常用的几个函数。 random.random random.random(...

3307
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(四) ——Redis中的跳跃表

《Redis设计与实现》读书笔记(四) ——Redis中的跳跃表 (原创内容,转载请注明来源,谢谢) 一、概述 跳跃表(skiplist)是一种有序的数据结构,...

3354
来自专栏前端学习心得

ES6核心特性(三)----细说数组常用的方法

972
来自专栏程序员叨叨叨

8.1 函数第 8 章 函数与程序设计

通过第 5 章到第 7 章的阅读,我们已经知道了怎么声明变量(第 5 章),怎么写表达式和语句(第 6 章),怎么将输入 \ 输出参数绑定到语义词(第 7 章)...

782
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-03:控制流

0.概述 前面介绍了语言的演进以及一些基础概念后,从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述),大致如下7种: 顺序执...

18910

扫码关注云+社区