hashcode的作用_jdbc hibernate区别_java hashcode相同(12)

index = (o.hashCode() & 0x7FFFFFFF)%hs.length;

这个对象就会直接放在Hashtable的第index位置,对于写入,这和数组一样,把一个对象

放在其中的第index位置,但如果是查询,经过同样的算法,Hashtable可以直接从第index

取得这个对象,而数组却要做循环比较.所以对于数据量稍大时,Hashtable的查询比数据

具有更高的性能.

既然可以根据HashCode直接定位对象在Hashtable中的位置,那么为什么Hashtable

要用key来做映射呢(为了一些思维有障碍的人能看到懂我加了一句话:而不是直接放value呢)

?这就是关系Hashtable性能问题的最重要的问题:Hash冲突.

常见的Hash冲突是不同对象最终产生了相同的索引,而一种非常甚至绝对少见的Hash冲突

是,如果一组对象的个数大过了int范围,而HashCode的长度只能在int范围中,所以肯定要

有同一组的元素有相同的HashCode,这样无论如何他们都会有相同的索引.当然这种极端

的情况是极少见的,可以暂不考虑,但对于相同的HashCode经过取模,则会产中相同的索引,

或者不同的对象却具有相同的HashCode,当然具有相同的索引.

所以对于索引相同的对象,在该index位置存放了多个对象,这些值要想能正确区分,就要依

靠key本身和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比较,如果太多的对象参与了散列.

那么需要的操作常数时间将会增加很大.所以,挑选哪些属性参与散列绝对是一个编程水平

的问题.

从实现来说,一般的HashCode方这样:

return Attribute1.HashCode() + Attribute2.HashCode()...[+super.HashCode()],

我们知道,每次调用这个方法,都要重新对方法内的参与散列的对象重新计算一次它们的

HashCode的运算,如果一个对象的属性没有改变,仍然要每次都进行计算,所以如果设置一

个标记来缓存当前的散列码,只要当参与散列的对象改变时才重新计算,否则调用缓存的

hashCode,这可以从很大程度上提高性能.

默认的实现是将对象内部地址转化为整数作为HashCode,这当然能保证每个对象具有不同

的HasCode,因为不同的对象内部地址肯定不同(废话),但java语言并不能让程序员获取对

象内部地址,所以,让每个对象产生不同的HashCode有着很多可研究的技术.

如何从多个属性中采样出能具有多样性的hashCode的属性,这是一个性能和多样性相矛

盾的地方,如果所有属性都参与散列,当然hashCode的多样性将大大提高,但牺牲了性能,

而如果只有少量的属性采样散列,极端情况会产生大量的散列冲突,如对"人"的属性中,如

果用性别而不是姓名或出生日期,那将只有两个或几个可选的hashcode值,将产生一半以上

的散列冲突.所以如果可能的条件下,专门产生一个序列用来生成HashCode将是一个好的选

择(当然产生序列的性能要比所有属性参与散列的性能高的情况下才行,否则还不如直接用

所有属性散列).

如何对HashCode的性能和多样性求得一个平衡,可以参考相关算法设计的书,其实并不一定

要求非常的优秀,只要能尽最大可能减少散列值的聚集.重要的是我们应该记得HashCode对

于我们的程序性能有着生要的影响,在程序设计时应该时时加以注意.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-36492-12.html