深入 HashCode 方法
CSDN Blog推出文章指数概念,文章指数是对Blog文章综合评分后推算出的,综合评分项分别是该文章的点击量,回复次数,被网摘收录数量,文章长度和文章类型;满分100,每月更新一次。
Go deep into HashCode
为什么HashCode对于对象是如此的重要?
一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的
Hash算法相比还不能叫真正的算法,它如何实现它,不仅仅是程序员的编程水平问题,
而是关系到你的对象在存取是性能的非常重要的关系.有可能,不同的HashCode可能
会使你的对象存取产生,成百上千倍的性能差别.
我们先来看一下,在JAVA中两个重要的数据结构:HashMap和Hashtable,虽然它们有很
大的区别,如继承关系不同,对value的约束条件(是否允许null)不同,以及线程安全性
等有着特定的区别,但从实现原理上来说,它们是一致的.所以,我们只以Hashtable来
说明:
在java中,存取数据的性能,一般来说当然是首推数组,但是在数据量稍大的容器选择中,
Hashtable将有比数组性能更高的查询速度.具体原因看下面的内容.
Hashtable在存储数据时,一般先将作为key的对象的HashCode和0x7FFFFFFF做与操作,因为一个
对象的HashCode可以为负数,这样操作后可以保证它为一个正整数.然后以Hashtable的
长度取模,得到值对象在Hashtable中的索引.
index = (o.hashCode() &; 0x7FFFFFFF)%hs.length;
这个值对象就会直接放在Hashtable的第index位置,对于写入,这和数组一样,把一个对象
放在其中的第index位置,但如果是查询,经过同样的算法,Hashtable可以直接通过key得到index,
从第index取得这个值对象,而数组却要做循环比较.所以对于数据量稍大时,Hashtable的
查询比数据
具有更高的性能.
虽然不同对象有不同的hashcode,但不同的hashCode经过与长度的取余,就很可能产生相同的index.
极端情况下会有大量的对象产生一个相同的索引.这就是关系Hashtable性能问题的最重要的
问题:
Hash冲突.
常见的Hash冲突是不同key对象最终产生了相同的索引,而一种非常甚至绝对少见的Hash冲突
是,如果一组对象的个数大过了int范围,而HashCode的长度只能在int范围中,所以肯定要
有同一组的元素有相同的HashCode,这样无论如何他们都会有相同的索引.当然这种极端
的情况是极少见的,可以暂不考虑,但是对于同的HashCode经过取模,则会产中相同的索引,
或者不同的对象却具有相同的HashCode,当然具有相同的索引.
事实上一个设计各好的HashTable,一般来说会比较平均地分布每个元素,因为Hashtable
的长度总是比实际元素的个数按一定比例进行自增(装填因子一般为0.75)左右,这样大多
数的索引位置只有一个对
象,而很少的位置会有几个元素.所以Hashtable中的每个位置存
放的是一个链表,对于只有一个对象是位置,链表只有一个首节点(Entry),Entry的next为
null.然后有hashCode,key,value属性保存了该位置的对象的HashCode,key和value(对象
本身),如果有相同索引的对象进来则会进入链表的下一个节点.如果同一个索引中有多个
对象,根据HashCode和key可以在该链表中找到一个和查询的key相匹配的对象.
从上面我看可以看到,对于HashMap和Hashtable的存取性能有重大影响的首先是应该使该
数据结构中的元素尽量大可能具有不同的HashCode,虽然这并不能保证不同的HashCode
产生不同的index,但相同的HashCode一定产生相同的index,从而影响产生Hash冲突.
对于一个象,如果具有很多属性,把所有属性都参与散列,显然是一种笨拙的设计.因为对象
的HashCode()方法几乎无所不在地被自动调用,如equals比较,如果太多的对象参与了散列.
那么需要的操作常数时间将会增加很大.所以,挑选哪些属性参与散列绝对是一个编