踩坑集锦之hashcode计算

2023-05-09 10:04:28 浏览数 (3)

踩坑集锦之hashcode计算

问题

需求: 针对java对象hashcode取余，计算出一个1-100之间的数字。

  • 这个需求很简单，或许大家很快就可以写出答案:
代码语言：javascript复制
targetObject.hashCode() % 100   1

但是这个答案存在问题，因为没有考虑到hashcode出现负数的情况，为什么hashcode会出现负数呢？

我们需要从hashcode的计算方式进行推导。

对象hashcode怎么计算出来的

在Java中，每个对象都有一个默认的hashCode()方法，它返回一个int类型的哈希码（hashcode），表示对象的散列值。

hashCode()方法的实现方式可以由具体的类自行决定，但通常情况下，它是根据对象的内部状态计算出来的。一个好的hashCode()实现应该具备以下特性：

  1. 对于同一个对象，多次调用hashCode()方法应该返回相同的值。
  2. 对于不同的对象，它们的hashCode()值应该尽可能地不同，以便于散列表等数据结构的高效操作。
  3. 如果两个对象的equals()方法返回true，那么它们的hashCode()方法返回的值应该相同。

通常情况下，hashCode()方法的实现都会使用对象的内部状态来计算出一个整数值。例如，如果一个对象包含多个字段，那么它的hashCode()方法可能会将这些字段的值组合起来计算出一个散列值。在计算散列值时，通常会使用位运算、乘法和异或等操作来混淆散列值，以增加哈希码的随机性和均匀性。

需要注意的是，hashCode()方法的实现方式可以因不同的JVM、不同的操作系统或不同的Java版本而有所不同。因此，在需要对哈希码进行散列操作的场景中，建议使用专业的哈希算法，如MD5或SHA等算法，以确保哈希码的唯一性和安全性。

HotSpot虚拟机是如何计算出对象hashcode的

在HotSpot虚拟机中，hashCode()方法的计算规则如下：

  1. 如果该对象的哈希码已经被计算出来，则直接返回该哈希码。
  2. 如果该对象的哈希码尚未被计算出来，则根据对象的内存地址计算出一个哈希码，并将其缓存起来。
  3. 如果该对象被标记为“轻量级锁”（Lightweight Locking），则哈希码的计算方式稍有不同。此时，哈希码由线程ID、对象头信息和对象的内存地址组成。

需要注意的是，由于哈希码是根据对象的内存地址计算出来的，因此在不同的JVM实例中，相同的对象可能具有不同的哈希码。此外，由于哈希码是缓存起来的，因此在对象的状态发生变化时，哈希码也不会自动更新，这可能会导致哈希表等数据结构无法正常工作。

为了避免这种问题，建议在实现hashCode()方法时，不要依赖于对象的内存地址或缓存的哈希码，而应该根据对象的内部状态计算出一个稳定的、唯一的哈希码，以确保对象在不同的JVM实例中都具有相同的哈希码，并且在对象状态发生变化时能够正确地更新哈希码。

如何根据对象内存地址计算出对象的hashcode

在HotSpot中，如果对象的哈希码尚未被计算出来，则根据对象的内存地址计算出一个哈希码。具体计算方式如下：

  1. 首先，将对象的内存地址右移4位（也就是除以16），以去掉低4位的偏移量。
  2. 然后，将去掉偏移量后的地址与一个固定的随机数进行异或运算，以增加哈希码的随机性和均匀性。
  3. 最后，将异或运算的结果作为对象的哈希码返回。

由于哈希码是根据对象的内存地址计算出来的，因此在不同的JVM实例中，相同的对象可能具有不同的哈希码。这可能会影响到一些基于哈希表的数据结构，如HashMap和HashSet等，因为这些数据结构的性能和正确性通常依赖于对象的哈希码。

为了避免这种问题，建议在实现hashCode()方法时，不要依赖于对象的内存地址或缓存的哈希码，而应该根据对象的内部状态计算出一个稳定的、唯一的哈希码，以确保对象在不同的JVM实例中都具有相同的哈希码，并且在对象状态发生变化时能够正确地更新哈希码。

可变对象加哈希缓存导致的错误问题

一个典型的例子是将可变对象放入哈希表中。如果哈希表的实现是基于对象的哈希码的，那么当可变对象的状态发生变化时，它的哈希码也会发生变化，但哈希表中存储的哈希码并不会自动更新。这样就会导致哈希表中的对象数量不稳定，甚至可能出现哈希冲突等问题。

下面是一个具体的例子：

代码语言：javascript复制
class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

public class Test {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        Person p = new Person("Tom", 20);
        set.add(p);
        System.out.println(set.contains(p)); // true
        p.age = 30;
        System.out.println(set.contains(p)); // false
    }
}

在这个例子中，我们创建了一个Person类，它有两个属性name和age，并且实现了hashCode()方法，该方法基于name和age属性的值计算出哈希码。然后，我们将一个Person对象加入到HashSet中，并检查该对象是否存在于HashSet中。这时，HashSet会根据对象的哈希码和相等性检查来查找该对象。

接着，我们修改该对象的age属性，然后再次检查该对象是否存在于HashSet中。由于age属性的变化导致哈希码的变化，所以HashSet无法正确地查找该对象，最终返回了false。这个问题的根本原因是，Person对象的哈希码是基于对象的属性计算出来的，而属性值的变化会导致哈希码的变化，从而破坏了哈希表的正确性。

如何解决

为了解决上面提到的哈希冲突等问题，可以采用以下两种方法：

  1. 不要将可变对象放入哈希表中。如果需要将可变对象作为哈希表的键值，可以考虑将对象中不可变的部分作为哈希码的计算因子，或者使用其他的数据结构来代替哈希表。
  2. 重写hashCode()和equals()方法。在重写hashCode()方法时，要保证对象的哈希码是不变的；在重写equals()方法时，要保证相等的对象具有相等的哈希码。这样，当可变对象的状态发生变化时，其哈希码也会自动更新，从而保证了哈希表中对象的正确性。

下面是上面提到的Person类的修订版，我们将其改为不可变的类，并重写了hashCode()和equals()方法：

代码语言：javascript复制
class Person {
    private final String name;
    private final int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
}

public class Test {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        Person p = new Person("Tom", 20);
        set.add(p);
        System.out.println(set.contains(p)); // true
        p = new Person("Tom", 30);
        System.out.println(set.contains(p)); // false
    }
}

在这个修订版中，Person类被改为了不可变的类，即name和age属性被声明为final，从而保证了对象的不变性。同时，重写了hashCode()和equals()方法，其中hashCode()方法的计算只依赖于不可变的属性，而equals()方法也只比较不可变的属性。这样，当Person对象的状态发生变化时，其哈希码也不会变化，从而保证了哈希表中对象的正确性。

hashcode的取值范围

在Java中，Object类的hashCode()方法返回的值是一个32位的整数，它可以是任何整数，包括负数和零。

通常情况下，hashCode()方法返回的值都是根据对象的内部状态计算出来的，因此对于不同的对象，它们的hashCode()值也应该不同。但是，由于hashCode()方法的实现方式可能会因不同的JVM、不同的操作系统或不同的Java版本而有所不同，因此在某些情况下，hashCode()方法可能返回负数。

如果hashCode()方法返回负数，那么在使用该值进行位运算或其他计算时，就需要特别注意。在进行位运算时，需要使用& 0x7FFFFFFF将负数转换为正数，以确保计算结果的正确性。

& 0x7FFFFFFF 这个操作有什么作用

& 0x7FFFFFFF 是一个按位与操作符，它的作用是将targetObject.hashCode()的符号位置零，以确保结果为正数。

在Java中，hashCode()方法返回的是一个32位的整数值，它的最高位表示符号位，如果该位为1，则表示该值为负数，否则表示该值为非负数。因此，如果hashCode()返回的值为负数，那么进行位与操作的结果就是将最高位的1变为0，即将符号位变为0，从而得到一个非负数的结果。

在这段代码中，使用0x7FFFFFFF对hashCode()进行位与操作，相当于将二进制表示中最高位的1变为0，因为0x7FFFFFFF的二进制表示为0111 1111 1111 1111 1111 1111 1111 1111。这个操作可以确保位与运算的结果为正数，从而保证了结果的正确性。

实例演示

假设targetObject.hashCode()返回的值是-123456789，也就是它的二进制表示为1111 1111 1001 1101 1101 0001 1101 0011（其中最高位为符号位，值为1表示负数）。

进行按位与操作& 0x7FFFFFFF时，先将0x7FFFFFFF转换为二进制表示，即0111 1111 1111 1111 1111 1111 1111 1111。然后按位与运算，将两个二进制数对应位上的数字进行逻辑与运算。结果如下：

代码语言：javascript复制
  1111 1111 1001 1101 1101 0001 1101 0011 (targetObject.hashCode())
& 0111 1111 1111 1111 1111 1111 1111 1111 (0x7FFFFFFF)
结果:  0111 1111 1001 1101 1101 0001 1101 0011

可以看到，按位与运算的结果是一个非负数，其二进制表示为0111 1111 1001 1101 1101 0001 1101 0011，即2147483659，它是原来负数的补码表示形式。

然后，对这个结果进行模运算% 100，得到59，即将结果映射到0到99的范围内。

最后，将结果加1，得到60，即将结果映射到1到100的范围内，这就是该代码段的最终结果。

最终解决方案

经过上面的分析，最终可以得出下面这行代码作为答案:

代码语言：javascript复制
(targetObject.hashCode() & 0x7FFFFFFF) % 100   1

先对对象的hashCode进行位与运算，将结果的符号位置零，以确保结果为正数，然后对结果取模得到介于0和99之间的数值，最后加上1以将结果转换为介于1和100之间的整数。

缓存 数据结构 hashcode 对象 二进制

1 人点赞