首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

hashcode 的功用

2012-08-31 
hashcode 的作用Java 对象 Hashcode 的作用是什么?可以联想数据结构的哈希表(散列表)、哈希函数。Object.has

hashcode 的作用

Java 对象 Hashcode 的作用是什么?可以联想数据结构的哈希表(散列表)、哈希函数。Object.hashCode() 就是一个哈希函数,用来计算散列值以实现哈希表这种数据结构。

看下哈希表结构:

hashcode 的功用

哈希表

在一个数组中存储对象时,通过 hashCode 得到的哈希值来计算数组的索引位置(通常是求余运算),然后根据这个索引位置进行存取。多个对象计算出来的索引位置相同(叫hash冲突)时,用链表保存。冲突怎么保证取到的就是自己呢?那么就要用到 Object.equals() 方法。

所以要把对象存储在像 hash table类似的数据结构(比如:HashSet)中,hashCode 与 equals 要成对实现。

Java Object hashCode api

返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。
hashCode 的常规协定是:
  • 在 Java 应用程序执行期间,在同一对象上多次调用?hashCode?方法时,必须一致地返回相同的整数,前提是对象上equals?比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。
  • 如果根据?equals(Object)?方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
  • 以下情况?是必需的:如果根据?equals(java.lang.Object)?方法,两个对象不相等,那么在两个对象中的任一对象上调用?hashCode?方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。

    实际上,由?Object?类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。(这一般是通过将该对象的内部地址转换成一个整数来实现的,但是 JavaTM?编程语言不需要这种实现技巧。)

    上面的协定来看,一个对象的状态(这些状态不一定是所有字段,根据业务来看)没有改变时,多次调用 hashCode 必定相等。但是不同的对象可以有相等的 hashCode,不过尽量使不同的对象有不相等的 hashCode 可以提高哈希表的性能。

    看下 Java Hashtable 的 get 与 put 实现:

    1. public?synchronized?V?get(Object?key)?{??
    2. ????Entry?tab[]?=?table;??
    3. ????int?hash?=?key.hashCode();??
    4. ????int?index?=?(hash?&?0x7FFFFFFF)?%?tab.length;??
    5. ????for?(Entry<K,V>?e?=?tab[index]?;?e?!=?null?;?e?=?e.next)?{??
    6. ????????if?((e.hash?==?hash)?&&?e.key.equals(key))?{??
    7. ????????return?e.value;??
    8. ????????}??
    9. ????}??
    10. ????return?null;??
    11. }??

    先根据 key.hashCode 找数组的索引位置 index,hash & 0x7FFFFFFF 保证是正数。然后顺着找 hash 和 equals 相等的。冲突链越长性能就越差。

    看 put 方法:

    1. public?synchronized?V?put(K?key,?V?value)?{??
    2. ????//?Make?sure?the?value?is?not?null??
    3. ????if?(value?==?null)?{??
    4. ????????throw?new?NullPointerException();??
    5. ????}??
    6. ??
    7. ????//?Makes?sure?the?key?is?not?already?in?the?hashtable.??
    8. ????Entry?tab[]?=?table;??
    9. ????int?hash?=?key.hashCode();??
    10. ????int?index?=?(hash?&?0x7FFFFFFF)?%?tab.length;??
    11. ????for?(Entry<K,V>?e?=?tab[index]?;?e?!=?null?;?e?=?e.next)?{??
    12. ????????if?((e.hash?==?hash)?&&?e.key.equals(key))?{??
    13. ????????V?old?=?e.value;??
    14. ????????e.value?=?value;??
    15. ????????return?old;??
    16. ????????}??
    17. ????}??
    18. ??
    19. ????modCount++;??
    20. ????if?(count?>=?threshold)?{??
    21. ????????//?Rehash?the?table?if?the?threshold?is?exceeded??
    22. ????????rehash();??
    23. ??
    24. ????????????tab?=?table;??
    25. ????????????index?=?(hash?&?0x7FFFFFFF)?%?tab.length;??
    26. ????}??
    27. ??
    28. ????//?Creates?the?new?entry.??
    29. ????Entry<K,V>?e?=?tab[index];??
    30. ????tab[index]?=?new?Entry<K,V>(hash,?key,?value,?e);??
    31. ????count++;??
    32. ????return?null;??
    33. }??

    先看是否有相同的,有就替换。然后数组空间不够,会重换分配空间并数据重新散列保存。最后在冲突链头上插入。

热点排行