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

相关文章

来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

2648
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3284
来自专栏Linyb极客之路

UML类图(上):类、继承和实现

对于一个程序员来说,在工作的开始阶段通常都是别人把东西设计好,你来做。伴随着个人的成长,这个过程将慢慢变成自己设计一部分功能来实现,自己实现。如果要自己设计,无...

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

小米OJ刷题日志

$f[i][j]$表示第一个队列匹配到了$i$位置,第二个队列匹配到了$j$位置是否可行

3382
来自专栏前端说吧

JS-用js的for循环实现九九乘法表以及其他算数题等

3256
来自专栏java初学

top K 问题

39616
来自专栏我是攻城师

使用位运算替代模运算

3075
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

1382
来自专栏owent

PKU POJ 1720 SQUARES 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1720

391
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

2817

扫码关注云+社区