资讯专栏INFORMATION COLUMN

java中的hashCode

cnTomato / 1136人阅读

摘要:相关的文章网上很多了写这个主要是按自己的思路进行记录是什么中的实现是一个本地方法生成一个表征当前对象实例的特征值具体的实现根据的实现可能会不同中实际计算的函数的实现如下为时是直接使用的内存地址但默认使用的是的随

hashcode相关的文章网上很多了, 写这个主要是按自己的思路进行记录

hashCode是什么

Object中的hashCode实现是一个本地方法, 生成一个表征当前对象实例的特征值.

public native int hashCode();

具体的实现根据jvm的实现可能会不同. JDK1.8中实际计算hashcode的get_next_hash函数的实现如下(src/share/vm/runtime/synchronizer.cpp)

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // This form uses an unguarded global Park-Miller RNG,
     // so it"s possible for two threads to race and generate the same RNG.
     // On MP system we"ll have lots of RW access to a global, so the
     // mechanism induces lots of coherency traffic.
     value = os::random() ;
  } else
  if (hashCode == 1) {
     // This variation has the property of being stable (idempotent)
     // between STW operations.  This can be useful in some of the 1-0
     // synchronization schemes.
     intptr_t addrBits = intptr_t(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     value = 1 ;            // for sensitivity testing
  } else
  if (hashCode == 3) {
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     value = intptr_t(obj) ;
  } else {
     // Marsaglia"s xor-shift scheme with thread-specific state
     // This is probably the best overall implementation -- we"ll
     // likely make this the default in future releases.
     unsigned t = Self->_hashStateX ;
     t ^= (t << 11) ;
     Self->_hashStateX = Self->_hashStateY ;
     Self->_hashStateY = Self->_hashStateZ ;
     Self->_hashStateZ = Self->_hashStateW ;
     unsigned v = Self->_hashStateW ;
     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
     Self->_hashStateW = v ;
     value = v ;
  }

  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

hashcode为4时是直接使用的内存地址, 但默认使用的是hashcode>=5的随机算法. 可以用JVM parameter -XX:hashCode来调整.
查了下, xor-shift scheme是弗罗里达州立大学一位叫做George Marsaglia的老师发明的使用位移和异或运算生成随机数的方法, 所以在计算机上运算速度非常快(移位指令需要的机器周期更少).有兴趣的可以去深入了解.

hashCode和equals方法

hashCode是由散列方法得来的, 所以不同对象按hashCode方法计算的散列值, 是可能相同的.
类似于存在两个不同串拥有相同的MD5值, 并且可能存在未知的其它串MD5值相同.

所以hashCode相同的对象, 并不一定是相等的, 需要通过equals方法比较.
如果两个对象的equals为true, 那么这两个对象的HashCode一定相同.

两个对象的hashCode值相同, 对于其作为hashmap的key没有影响, 即使映射到同一个槽中, 也可以通过对比key本身来进行区分.

equals需要满足数个性质:
自反性, 对称性, 传递性, 一致性.

对称性: 如果x.equals(y)返回是true,那么y.equals(x)也应该返回是true
自反性: x.equals(x)返回是true
传递性: 如果x.equals(y)返回是true,而且y.equals(z)返回是true,那么z.equals(x)也应该返回是true
一致性: 如果x.equals(y)返回是true,只要x和y内容一直不变, 那么x.equals(y)始终都返回都是true

这个其实也很好理解, 简单点思考可看作是两个数字在比较, 那么满足这些性质便是理所当然.

判断对象相等需要重写equals方法, 否则会调用Objectequals方法.

为什么重写equals方法, 通常需要重写hashCode方法?
假设现在有一个类Apple, 有两个属性color和weight. 比较两个Apple类的实例A和B是否相等(当然其中一个可能不是其实例), 实际等价于判断两者的两个属性是否都相等; 如果不重写hashCode方法, 当new一个新的Apple实例C, 将其color和weight属性设置成与B相同, 这就导致B.equals(C)时两者的hashCode不一致, 会产生理解上的混淆.

重写hashCode的经典方式是使用17和31散列码的实现:

public class Apple {
    private String color;
    private int weight;

    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof Apple)) {
            return false;
        }
        Apple apple = (Apple) o;
        return apple.color.equals(color) &&
                apple.weight == weight;
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + color.hashCode();
        result = 31 * result + weight;
        return result;
    }
}

除此之外, 可以使用java.util.Objects去重写equalshashCode, 也可以使用Apache Commons Lang的LangEqualsBuilderHashCodeBuilder方法. 这两种方式也是对于17和31散列码思想的封装实现.

集合类的hashCode

AbstractSet中的实现, 对所有元素的hashCode对应的int值进行累加求和. 这样的话, 两个都包括"a", "b", "c"三个元素的HashSet, 不论添加次序, 其hashCode是一样的.

public int hashCode() {
        int h = 0;
        Iterator i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
        return h;
    }

AbstractList中的实现, 使用了31让结果更分散.

public int hashCode() {
        int hashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }

AbstractMap是遍历将每个entry的hashCode累加. 等等.

如果两个集合对象的hashCode相等, 完全无法说明这两个对象相等, 但如果不等, 说明这两个对象肯定是不等的. 可作为一个快速判断不等的方案.

缓存对象的hashCode

hashCode每次都是实时计算的, 虽然其是一个本地方法, 速度非常快, 如果有大量重复使用的场景, 可以考虑像Integer内部缓存int值为-128到127的对象一样进行缓存.

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69178.html

相关文章

  • 【码艺杂谈】Java中的相同与不同

    摘要:如果根据方法得到两个对象不相同,那么两个对象的方法的结果不一定不相同,我们可以利用这一点来提高散列表的性能。最后回到文章开头的问题,如何判断两个对象或值是否相同这个问题其实有两方面的含义,一方面是判断的方法,另一方面是判断的效率。 Java中有很多场景需要判断两个对象或者两个值,那么 判断是否相同的依据是什么? 如何判断是否相同呢? 为了解释这个问题,我们从Java语言的根说起,那...

    xingqiba 评论0 收藏0
  • 【金三银四】面试题之java基础

    摘要:中,任何未处理的受检查异常强制在子句中声明。运行时多态是面向对象最精髓的东西,要实现运行时多态需要方法重写子类继承父类并重写父类中已 1、简述Java程序编译和运行的过程:答:① Java编译程序将Java源程序翻译为JVM可执行代码--字节码,创建完源文件之后,程序会先被编译成 .class 文件。② 在编译好的java程序得到.class文件后,使用命令java 运行这个 .c...

    Yangyang 评论0 收藏0
  • 【金三银四】面试题之java基础

    摘要:中,任何未处理的受检查异常强制在子句中声明。运行时多态是面向对象最精髓的东西,要实现运行时多态需要方法重写子类继承父类并重写父类中已 1、简述Java程序编译和运行的过程:答:① Java编译程序将Java源程序翻译为JVM可执行代码--字节码,创建完源文件之后,程序会先被编译成 .class 文件。② 在编译好的java程序得到.class文件后,使用命令java 运行这个 .c...

    Barrior 评论0 收藏0
  • Java中的 equals() 和 hashCode() 契约

    摘要:我们使用调试器却发现在中已经存储了这个对象。中和有一个契约如果两个对象相等的话,它们的必须相等但如果两个对象的相等的话,这两个对象不一定相等。的结构能够快速找到一个对象,而不是进行较慢的线性查找。可以看作是数组的数组。 java.lang.Object类中有两个非常重要的方法: public boolean equals(Object obj) public int hashCode...

    rainyang 评论0 收藏0
  • 理解Java中HashMap的工作原理

    摘要:中的使用散列来高效的查找和存储值。理解中的方法是顶层对象中的方法因此中所有的对象都会带有方法。中给出了覆盖方法的最佳实践把某个非零的常数值比如保存在一个名为的类型中。 Java中的HashMap使用散列来高效的查找和存储值。HashMap内部使用Map.Entry的形式来保存key和value,使用put(key,value)方法存储值,使用get(key)方法查找值。 理解hashC...

    xiangchaobin 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<