乐趣区

Java中的HashCode

什么是 hashcode

hashcode 即哈希码, 是方便用于查找而使用的一种方法

1. 假如内存中有这样的位置 0  1  2  3  4  5  6  7 , 当我要存储一个对象时, 我就要把这个对象放在 8 个位置之一, 如果不用 hashcode 而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法, 但如果用 hashcode 那就会使效率提高很多.

2. 我们这个对象中有个字段叫 ID, 那么我们就定义我们的 hashcode 为 ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的 ID 为 9,9 除 8 的余数为 1,那么我们就把该类存在 1 这个位置,如果 ID 是 13,求得的余数是 5,那么我们就把该类放在 5 这个位置。这样,以后在查找该类时就可以通过 ID 除 8 求余数直接找到存放的位置了

3. 如果两个对象的 hashcode 一样, 则存储在同一个内存位置, 那该如何查找呢, 这个时候就需要 equals 方法了, 也就是说,我们先通过 hashcode 来判断两个类是否存放某个桶里,但这个桶里可能有很多对象,那么我们就需要再通过 equals 来在这个桶里找到我们要的对象

4. 一般在重写 equals 方法的同时, 还要重写 hashcode 方法, 要在一块内存区域里找东西,就必须先找到这块内存区域, 然后再在这块内存区域里寻找对象.

hashcode 的一般约定

在 Java 应用程序中,任何时候对同一对象多次调用 hashCode 方法,都必须一直返回同样的整数,对它提供的信息也用于对象的相等比较,且不会被修改。这个整数在两次对同一个应用程序的执行不中不需要保持一致。

如果两个对象通过 equals(Object) 方法来比较相等,那么这两个对象的 hashCode 方法必须产生同样的整型结果。

如果两个对象通过 equals(Object) 方法比较结果不等,这两个对象的 hashCode 不必产生同不整型结果。然而,开发者应该了解对不等的对象产生不同的整型结果有助于提高哈希表的性能。

hashcode 的计算方法

计算原则:

  • 一致性原则

当存储对象时, 对对象的某一个字段计算完 hashcode 后, 将对象放入响应的内存区域中, 如果有字段产生了变化,哈希码也应该允许变化(对于可变类来说,这往往是不可避免的),依赖哈希的数据结构并未准备应付这种情况。哈希码用于确定一个元素的桶,但是如果哈希相关的字段发生变化,并不会立即重新计算哈希码,而且内部的数组也不会更新。这就意味着,再对一个相等的对象甚至同一个对象的查询会失败!这个数据结构会计算当前的哈希码,这个哈希码与实例存入时的哈希码并不相同,这直接导致找错了桶。
小结: 不要用可变的字段来计算哈希码.

  • 性能

哈希码可能最终会在每次调用 equals 的时候计算,这可能正好发生在代码中性能极为关键的部分,所以考虑性能是很有意义的。相比之下 equals 的优化空间就非常小。
除非是使用了复杂的算法,或者使用的字段非常非常多,组合他们哈希码的计算成本可以忽略不计,因为这不可避免。但是应该考虑是否所有字段都需要包含在计算中!尤其应该以审视的眼光来看待集合,例如计算列表和集合中所有元素的哈希码。需要根据不同的情况来考虑是否需要它们参与计算。
如果性能是关键,使用 Object.hash 就可能不是最好的选择,因为它会为可变参数创建数组。
一般的优化原则是:谨慎处理!使用一个公共哈希算法的,可能需要放弃集合,并在分析可能的改进之后进行优化。

  • 碰撞
  • 计算 hash
退出移动版