腾讯微群加入QQ群

 找回密码
 加入我们

!connect_header_login!

!connect_header_login_tip!

搜索
查看: 201|回复: 0

String的hashcode(java)

[复制链接]
发表于 2016-8-23 14:58:36 | 显示全部楼层 |阅读模式

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

我们知道,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. }  

注意到hashCode方法前面有个native的修饰符,这表示hashCode方法是由非java语言实现的,具体的方法实现在外部,返回内存对象的地址。


在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是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事件。

HashMap里重写的hashCode方法

Java代码  收藏代码
  1. public final int hashCode() {  
  2.     return (key==null   ? 0 : key.hashCode()) ^  
  3.             (value==null ? 0 : value.hashCode());  
  4.  } 
    (转载请注明出处:博彩通


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


http://blog.csdn.net/hengyunabc/article/details/7198533

0
0

转自:http://blog.csdn.net/haihaa/article/details/51452581?locationNum=1
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 加入我们

本版积分规则

QQ|手机版|Archiver|小黑屋|一起疯|苦咖啡 ( 新ICP备12000197号  

GMT+8, 2018-1-19 05:56 , Processed in 0.329154 second(s), 12 queries , Memcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表