String的hashcode(java)

喜欢ヅ旅行 2021-06-24 15:57 402阅读 0赞

hashCode就是我们所说的散列码，使用hashCode[算法][Link 1]可以帮助我们进行高效率的查找，例如HashMap，说hashCode之前，先来看看Object类。

Java程序中所有类的直接或间接父类，处于类层次的最高点。在Object类里定义了很多我们常见的方法，包括我们要讲的hashCode方法，如下

Java代码

1.  public final native Class<?> getClass();  
2.  public native int hashCode();  
3.  public boolean equals(Object obj) \{  
4.    return (this == obj);  
5.  \}   
6.  public String toString() \{  
7.   return getClass().getName() + "@" +  Integer.toHexString(hashCode());  
8.  \}

在 java的很多类中都会重写equals和hashCode方法，这是为什么呢？最常见的String类，比如我定义两个字符相同的字符串，那么对它们进 行比较时，我想要的结果应该是相等的，如果你不重写equals和hashCode方法，他们肯定是不会相等的，因为两个对象的内存地址不一样。

String类的重写的hashCode方法

Java代码

1.  public int hashCode() \{  
2.      int h = hash;  
3.      if (h == 0) \{  
4.          int off = offset;  
5.          char val\[\] = value;  
6.          int len = count;  
7.    
8.              for (int i = 0; i < len; i++) \{  
9.                  h = 31\*h + val\[off++\];  
10.             \}  
11.             hash = h;  
12.         \}  
13.         return h;  
14.     \}

1、这段代码究竟是什么意思？

其实这段代码是这个数学表达式的实现

Java代码

1.  s\[0\]\*31^(n-1) + s\[1\]\*31^(n-2) + ... + s\[n-1\]

s\[i\] 是string的第i个字符，n是String的长度。那为什么这里用31，而不是其它数呢?《Effective Java》是这样说的：之所以选择31，是因为它是个奇素数，如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算。使用素数的 好处并不是很明显，但是习惯上都使用素数来计算散列结果。31有个很好的特性，就是用移位和减法来代替乘法，可以得到更好的性能：31\*i==(i<<5)-i。现在的VM可以自动完成这种优化。

2、它返回的hashCode有什么特点呢？

可 以看到，String类是用它的value值作为参数来计算hashCode的，也就是说，相同的value就一定会有相同的hashCode值。这点也 很容易理解，因为value值相同，那么用equals比较也是相等的，equals方法比较相等，则hashCode一定相等。反过来不一定成立。它不 保证相同的hashCode一定有相同的对象。

一个好的hash函数应该是这样的：为不相同的对象产生不相等的hashCode。

在 理想情况下，hash函数应该把集合中不相等的实例均匀分布到所有可能的hashCode上，要想达到这种理想情形是非常困难的，至少java没有达到。 因为我们可以看到，hashCode是非随机生成的，它有一定的规律，就是上面的数学等式，我们可以构造一些具有相同hashCode但value值不一 样的，比如说：Aa和BB的hashCode是一样的。

说 到这里，你可能会想，原来构造hash冲突那么简单啊，那我是不是可以对HashMap函数构造很多<key,value>不都一样，但具有 相同的hashCode，这样的话可以把HashMap函数变成一条单向链表，运行时间由线性变为平方级呢？虽然HashMap重写的hashCode方 法比String类的要复杂些，但理论上说是可以这么做的。这也是最近比较热门的Hash Collision DoS事件。

Java代码

1.  public final int hashCode() \{  
2.      return (key==null   ? 0 : key.hashCode()) ^  
3.              (value==null ? 0 : value.hashCode());    
    
4.   \}   
    （转载请注明出处：\[url=http://www.k8764.com\]博彩通\[/url\]

总结：字符串hash函数，不仅要减少冲突，而且要注意相同前缀的字符串生成的hash值要相邻。

[Link 1]: http://lib.csdn.net/base/31

发表评论取消回复

表情：

评论列表（有 0 条评论，402人围观）

还没有评论，来说两句吧...

相关阅读

相关 java String的经典问题(new String() ,String )

先来看一个例子，代码如下： 1.public class Test { public static void main(String[] arg

痛定思痛。/ 2022年08月08日 15:49/ 0 赞/ 164 阅读

相关转为String类型的java.toString() ,(String),String.valueOf的区别

转自：http://blog.csdn.net/springk/article/details/6414017 在[Java][]项目的实际开发和应用中，常常需要用到将对象转

╰半橙微兮°/ 2022年06月13日 01:41/ 0 赞/ 160 阅读

相关 String 和 new String()的区别

Java基础原理栈区存引用和基本类型，不能存对象，而堆区存对象。==是比较地址，equals()比较对象内容。 String是char\[\] 数组。 String的

港控/mmm°/ 2022年05月24日 14:10/ 0 赞/ 185 阅读

相关 (String)、toString、String.valueOf的区别

在Java项目的实际开发和应用中，常常需要用到将对象转为String这一基本功能。本文将对常用的转换方法进行一个总结。常用的方法有（String）要转换的对象，Object

忘是亡心i/ 2022年04月15日 03:37/ 0 赞/ 260 阅读

相关 [C#] String与string的区别

C\是区分大小写的，但是我却发现C\中同时存在String与string，于是我很困惑，于是我上网搜索了一下，于是我了解了一些小知识。 MSDN中对string的说明：str

怼烎@/ 2022年03月30日 19:39/ 0 赞/ 171 阅读

相关 Java的String.valueOf(String)和String a + "" 的效率

float a= 125F; 那么String s = ""; s = String.valueOf(a); 和 String s = ""; s = a + "";

「爱情、让人受尽委屈。」/ 2022年03月29日 01:58/ 0 赞/ 354 阅读

相关 String,String Buffer,String Build

可变性　简单的来说：String 类中使用 final 关键字字符数组保存字符串，`private　final　char　value[]`，所以 String 对象是不可

﹏ヽ暗。殇╰゛Y/ 2022年03月08日 21:28/ 0 赞/ 194 阅读

相关 (String)、toString、String.valueOf的区别

在Java项目的实际开发和应用中，常常需要用到将对象转为String这一基本功能。本文将对常用的转换方法进行一个总结。常用的方法有（String）要转换的对象，

r囧r小猫/ 2022年03月01日 10:37/ 0 赞/ 236 阅读

相关 c# String ,String[] 和 List<String>之间的转换

C\对字符串进行处理时，经常需要进行String,String\[\]和List<String>之间的转换本文分析一下它们的差异和转换一. 　　1. String

川长思鸟来/ 2022年01月06日 12:29/ 0 赞/ 560 阅读

相关 string[] 和List<string>的区别

一直对string\[\]和List<string>定义不怎么清楚，特地总结一下： string\[\]数组里面是存放string型的值，List<string

爱被打了一巴掌/ 2021年10月08日 07:30/ 0 赞/ 489 阅读