定义hashcode时使用31系数的原因

散列计算就是计算元素应该放在数组的哪个元素里。准确的说是放到哪个链表里面。按照Java的规则，如果你要想将一个对象放入HashMap中，你的对象的类必须提供hashcode方法，返回一个整数值。比如String类就有如下方法：

public int hashCode() {
    int h = hash;
    int len = count;
    if (h == 0 && len > 0) {
      int off = offset;
      char val[] = value; 

      for (int i = 0; i < len; i++) {
        h = 31*h + val[off++];
      }
      hash = h;
    }
    return h;
  }

注意上面的for循环，有点搞吧？我来举个例子，让你很容易明白它在搞什么名堂。比如有一个字符串“abcde”,采用31进制的计算方法来计算这个字符串的总和，你会写出下面的计算式子：

a*31^4+b*31^3+c*31^2+d*31^1+e*31^0.注意，这里的a,b,c,d或者e指的是它们的ASCII值。很有趣的循环，居然可以用来算N进制。这个循环可以抽出来单独作为计算进制的好工具：

public static void main(String[] args) {
    int[] a={1,0};
    System.out.println(calculate(2,a));
  } 

  private static int calculate(int radix,int[] a){
    int sum = 0;
    for(int i=0;i<a.length;++i){
      sum = sum*radix+a[i];
    }
    return sum;
  }

静态方法caculate接受radix作为进制基数，数组a模拟要计算的进制的数字，只是注意表面顺序需要一致。比如 01 二进制串，在数组中要按照{0,1}排列。上面的输出结果是1，符合01的真实值。

那么为什么选用31作为基数呢？先要明白为什么需要HashCode.每个对象根据值计算HashCode,这个code大小虽然不奢求必须唯一（因为这样通常计算会非常慢），但是要尽可能的不要重复，因此基数要尽量的大。另外，31*N可以被编译器优化为
左移5位后减1，有较高的性能。其实选用31还是有争议，参考这里。

认为这个东西还是会导致较多的重复，应该用更大的数字。所以，或许将来Java的实现中会有所变化。下面这篇文章介绍了两个结论：

1.基数要用质数

质数的特性（只有1和自己是因子）能够使得它和其他数相乘后得到的结果比其他方式更容易产成唯一性，也就是hash code值的冲突概率最小。

2.选择31是观测分布结果后的一个选择，不清楚原因，但的确有利。

另外，String.hashCode内部会缓存第一次计算的值，因为这是一个final（不可变）类，也就是String对象的内容是不会变的。这能够在多次put到HashMap的场合提高性能，不过似乎用处不多。

总结

以上就是本文关于定义hashcode时使用31系数的原因的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：

《重写hashCode()和equals()方法详细介绍》

《详解hashCode()和equals()的本质区别和联系》

《Java源码角度分析HashMap用法》

如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • java 中HashCode重复的可能性

    java 中HashCode重复的可能性 今天有同事提议用String的hashcode得到int类型作为主键.其实hashcode重复的可能性超大,下面是java的缺省算法: public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++];

  • 详解Java中hashCode的作用

    详解Java中hashCode的作用 以下是关于HashCode的官方文档定义: hashcode方法返回该对象的哈希码值.支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表. hashCode 的常规协定是: 在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改.从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致. 如果根据

  • 探索Java中的equals()和hashCode()方法_动力节点Java学院整理

    equals()和hashCode()区别?  equals():反映的是对象或变量具体的值,即两个对象里面包含的值--可能是对象的引用,也可能是值类型的值.  hashCode():计算出对象实例的哈希码,并返回哈希码,又称为散列函数.根类Object的hashCode()方法的计算依赖于对象实例的D(内存地址),故每个Object对象的hashCode都是唯一的:当然,当对象所对应的类重写了hashCode()方法时,结果就截然不同了. 之所以有hashCode方法,是因为在批量的对象比

  • Java中的hashcode方法介绍

    哈希表这个数据结构想必大多数人都不陌生,而且在很多地方都会利用到hash表来提高查找效率.在Java的Object类中有一个方法: public native int hashCode(); 根据这个方法的声明可知,该方法返回一个int类型的数值,并且是本地方法,因此在Object类中并没有给出具体的实现. 为何Object类需要这样一个方法?它有什么作用呢?今天我们就来具体探讨一下hashCode方法. 一.hashCode方法的作用 对于包含容器类型的程序设计语言来说,基本上都会涉及到has

  • Java 中HashCode作用_动力节点Java学院整理

    Java 中HashCode作用_动力节点Java学院整理

    第1 部分 hashCode的作用 Java集合中有两类,一类是List,一类是Set他们之间的区别就在于List集合中的元素师有序的,且可以重复,而Set集合中元素是无序不可重复的.对于List好处理,但是对于Set而言我们要如何来保证元素不重复呢?通过迭代来equals()是否相等.数据量小还可以接受,当我们的数据量大的时候效率可想而知(当然我们可以利用算法进行优化).比如我们向HashSet插入1000数据,难道我们真的要迭代1000次,调用1000次equals()方法吗?hashCod

  • 浅谈Java中的hashcode方法（推荐）

    哈希表这个数据结构想必大多数人都不陌生,而且在很多地方都会利用到hash表来提高查找效率.在Java的Object类中有一个方法: public native int hashCode(); 根据这个方法的声明可知,该方法返回一个int类型的数值,并且是本地方法,因此在Object类中并没有给出具体的实现. 为何Object类需要这样一个方法?它有什么作用呢?今天我们就来具体探讨一下hashCode方法. 一.hashCode方法的作用 对于包含容器类型的程序设计语言来说,基本上都会涉及到has

  • java中重写equals和重写hashCode()

    java中重写equals和重写hashCode()

    java中重写equals和重写hashCode() 记得在刚上初一的时候,第一堂数学课学的是集合,那时候我知道了集合是不允许重复元素存在的. hashCode 方法用于散列集合的查找,equals 方法用于判断两个对象是否相等. 为什么重写了 equals 方法,还要重写 hashCode 方法? 因为如果只重写了 equals 方法,两个对象 equals 返回了true,但是如果没有重写 hashCode 方法,集合还是会插入元素.这样集合中就出现了重复元素了. 接下来详细分析,以 Has

  • java中重写equals()方法的同时要重写hashcode()方法(详解)

    java中重写equals()方法的同时要重写hashcode()方法(详解)

    object对象中的 public boolean equals(Object obj),对于任何非空引用值 x 和 y,当且仅当 x 和 y 引用同一个对象时,此方法才返回 true: 注意:当此方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码.如下: (1) 当obj1.equals(obj2)为true时,obj1.hashCode() == obj2.hashCode()必须为true (2) 当obj

  • 定义hashcode时使用31系数的原因

    散列计算就是计算元素应该放在数组的哪个元素里.准确的说是放到哪个链表里面.按照Java的规则,如果你要想将一个对象放入HashMap中,你的对象的类必须提供hashcode方法,返回一个整数值.比如String类就有如下方法: public int hashCode() { int h = hash; int len = count; if (h == 0 && len > 0) { int off = offset; char val[] = value; for (int i =

  • BootStrap.css 在手机端滑动时右侧出现空白的原因及解决办法

    BootStrap.css 在手机端滑动时右侧出现空白的原因及解决办法

    最近的一个项目 前台使用了 bootstrap.css + angularjs, 后台只处理数据(用的php,处理结果直接 json_encode($arr),非常爽).一直在Chrome的仿真机测试非常完美, 没有进行真机测试.完成后,到手机测试时傻了,左右滑动页面时,竟然出现了一个 空白的竖条(如下图所示).判断是margin-right 设置的长度所致,检查css,并没有相关代码.看来问题出现在了 bootstrap .虽然不影响 程序的使用,但是感觉非常别扭,一定要修复它. 检查页面,发

  • javascript定义变量时带var与不带var的区别分析

    本文实例分析了javascript定义变量时带var与不带var的区别.分享给大家供大家参考.具体分析如下: 直接看实例里说明: 复制代码 代码如下: <script language="javascript" type="text/javascript"> var abc=89;//带var,表示全局变量 function test(){  var abc=80;//在函数内部,如果不带var,表示使用函数外全局变量:带上var,表示新定义一个全局变量

  • Python定义函数时参数有默认值问题解决

    这篇文章主要介绍了Python定义函数时参数有默认值问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 在定义函数的时候,如果函数的参数有默认值,有两种类型的参数,一种是整数,字符串这种不可变类型,另一种是列表这种可变类型,对于第一种情况没有什么特殊的地方,但是对于可变类型,有一个微妙的小陷阱. 可变类型以及小陷阱: def append_item(item, list1=[]): list1.append(item) return lis

  • 浅谈JavaScript中定义变量时有无var声明的区别

    前段时间回答了一个关于定义变量时使用关键字var与否的区别,总结回顾一下. 1.在函数作用域内 加var定义的变量是局部变量,不加var定义的就成了全局变量. 使用var定义: var a = 'hello World'; function bb(){ var a = 'hello Bill'; console.log(a); } bb() //'hello Bill' console.log(a); //'hello world' 不使用var定义: var a = 'hello World'

  • javascript定义变量时加var与不加var的区别

    一.外部的为全局,内部的为局部变量. 二.加var为局部变量(在方法内),不加var为全局变量(当方法内有一次使用后) 复制代码 代码如下: <script type="text/javascript"> var golbe="global"; test(); function test(){      var local="local";     document.write(golbe);     document.write(l

  • Vue注册组件命名时不能用大写的原因浅析

    这段时间一直在弄vue,当然也遇到很多问题,这里就来跟大家分享一些注册自定义模板组件的心得. 首先"VUE注册组件命名时不能用大写"其实这句话是不对的,但我们很多人开始都觉得是对的,因为大家都踩过大写命名的坑 下面我们来看个例子: <div id="app"> <myTemplate></myTemplate> </div> <script> Vue.component('myTemplate',{ tem

  • Vue动态设置图片时src不生效的原因及解决方法

    Vue动态设置图片时src不生效的原因及解决方法

    目录 原因分析 解决方法 import和require的区别 原因分析 在vue项目中动态设置img的src时,图片会加载失败.我们可以先看个例子. <template> <div> <h1>动态设置图片</h1> <div> <h5>图片一</h5> <img :src=" logoFlag === 'vue' ? '../assets/vue-logo.png' : '../assets/react-l

  • js类定义函数时用prototype与不用的区别示例介绍

    一直在使用js编写自以为是面向对象的方法,遇到一个问题,就是定义一个方法,如下: 复制代码 代码如下: function ListCommon2(first,second,third) { this.First=function () { alert("first do"+first); } } ListCommon2.do1=function(first) { // this.First(); alert("first do"+first); } ListComm

  • MySQL删除表时I/O错误的原因分析与解决

    MySQL删除表时I/O错误的原因分析与解决

    问题现象 最近使用sysbench测试MySQL,由于测试时间较长,写了一个脚本按prepare->run->cleanup的顺序在后台跑着.跑完后察看日志发现一个问题,MySQL服务的错误日志中出现多条类似以下信息的报错: [ERROR] InnoDB: Trying to do I/O to a tablespace which does not exist. I/O type: read, page: [page id: space=32, page number=57890], I/O

随机推荐