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

相关文章

  • Collections.sort in JDK6:MergeSort

           本文是对JDK6中Collections.sort方法的源码解析,也可以看作是对Comparison method violates its ge...

    高爽
  • Flex事件机制(二)

    上一篇简单的介绍了Flex的事件机制以及处理事件的四种方式,本篇的主要内容是利用自定义事件在父子组件之间传递数据。        在Flex开发中,很多时候需...

    高爽
  • Comparison method violates its general contract!

    背景 16号为了统一线上服务器运行环境,将两台服务器的Tomcat6+JDK6升级到Tomcat7+JDK7,本以为很简单的事情,升级后自己验证也没问题,没想到...

    高爽
  • 【数据分析与可视化】Python的input和output

    瑞新
  • 【数据分析与可视化】Pandas-Dataframe-IO操作

    瑞新
  • python练习题1

    题目:输入某年某月某日,判断这一天是这一年的第几天?  分析:以3月5日为例,应该先把前两个月的加起来,然后再加上5天即本年的第几天,特殊 情况,闰年且输入月份...

    py3study
  • 实用的位运算应用(r4笔记第97天)

    对于位运算,之前在一篇博文中分享了一下在c语言和oracle中的位运算实现 http://blog.itpub.net/23718752/viewspace-1...

    jeanron100
  • 小文’s blog — 方程整数解 –《蓝桥杯代码笔记1》

    神无月
  • String.hashcode 源码分析

    接触编程这么久了,一直会遇到某些高频词,例如,哈希。hashtable,hashmap,hashset等等等。都有hash一次。那什么是哈希值呢?百度本科解释是...

    用户2909867
  • bmp图像大小biSizeImage算法公式由来

    LPBITMAPINFOHEADER lpbmiHeader; // ... 计算BMP方法 法一:lpbmiHeader->biSizeImage = (cx...

    _gongluck

扫码关注云+社区

领取腾讯云代金券