走在架构师的大道上 Jack.Wang's home

Java, C++, linux c, C#.net 技术,软件架构,领域建模,IT 项目管理 Dict.CN 在线词典, 英语学习, 在线翻译

BlogJava 首页 新随笔 联系 聚合 管理
  195 Posts :: 3 Stories :: 728 Comments :: 0 Trackbacks
为什么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,这样无论