原创

Java Hashing:从重写HashCode到可变对象

这是一篇关于hashCode方法,可变对象和内存泄漏问题的文章。

1. 重写 hashCode()equals() 的契约

每个 java 对象都有两个非常重要的方法,比如 hashCode()equals() 方法。这些方法旨在根据其特定的一般规则进行重写。
本文描述了为什么以及如何覆盖 hashCode() 方法,该方法在使用 HashMapHashSet 或任何 Collection 时保留 HashCode 的契约。

1.1 hashCode 契约

hashCode 的契约就是:

如果两个对象相等,那么调用两个对象的 hashCode() 方法一定会返回相同的 hash 值。

现在你应该想到的问题是:上述陈述是否应该永远是真的?

考虑一下这样一个事实,当我们为我们的类提供了一个正确的 equals 实现,那么如果我们不遵守上述规则会发生什么。

为了回答上面的问题,我们来考虑两个问题:

  1. 对象是相等的,但是返回了不同的 hashCode
  2. 对象不是相等的,但是它们却有相同的 hashCode

1.1.1 对象是相等的,但是返回了不同的 hashCode

当两个对象是相等的,但是返回了不同的 hashCode 会发生什么?你的代码会运行的很好。
除非你没有将对象存储在像 HashSetHashMap 这样的集合中,否则永远不会遇到麻烦。
但是当你将你的对象存储到上面提到的那种集合中的时候,在运行的时候可能会发生一些奇怪的问题。

为了更好的理解这个问题,你必须理解集合类中像 hashMap , HashSet 这样的数据结构是如何工作的。
这些集合类取决于您作为其中的键放置的对象,且必须遵守上述契约的事实。如果你没有遵循上面的契约,
并且尝试将对象存储在集合中,那么在运行期你将会得到一个奇怪并且不可预料的结果。

HashMap 为例子来说明。当你在 hashMap 中存储值的时候,这些值实际存储在一组桶中。每个桶都分配了一个用于识别它的号码。
当你在 HashMapput 一个值的时候,它就会在那些桶中存储数据。具体存储在哪个桶中,取决于你的对象所返回的 hashcode
换句话说,如果一个对象调用 hashCode() 方法返回了49,那么它就会存储在 HashMap 编号为49的这个桶中。

随后,当你尝试通过调用 contains(element) 方法去检查集合中是否包含该元素。 HashMap 首先会得到这个 elementhashCode
然后,它将查看与 hashCode 对应的存储桶。如果存储桶为空,则表示我们已完成,并且返回 false ,这意味着 HashMap 不包含该元素。

如果存储桶中有一个或多个对象,则它将使用您定义的 equals() 函数将 element 与该存储桶中的所有其他元素进行比较。

1.1.2 对象不是相等的,但是它们却有相同的 hashCode

hashCode 契约没有说明上述语句。因此,不同的对象可能返回相同的 hashCode 值,
但是如果不同的对象返回相同的 hashCode 值,则像 HashMap 这样的集合将无法正常使用。

1.2 为什么是存储桶?

您可以想象,如果放在 HashMap 中的所有对象都存储在一个大列表中,那么当您想要检查特定元素是否在 Map 中时,
您必须将输入与列表中的所有对象进行比较。通过使用存储桶,您现在只比较特定存储桶的元素,
并且任何存储桶通常只包含 HashMap 中所有元素的一小部分。

1.3 重写 hashCode 方法

编写一个好的 hashCode() 方法对于新类来说总是一项棘手的任务。

1.3.1 返回固定的值

您可以实现 hashCode() 方法,以便始终返回固定值,例如:

//bad performance 
@Override 
public int hashCode() { 
  return 1; 
}

上述方法满足所有要求,并根据哈希码合同被认为是合法的,但效率不高。
如果使用此方法,则所有对象将存储在同一个存储桶(即存储桶1)中,当您尝试确保特定对象是否存在于集合中时,它始终必须检查集合的整个内容。
另一方面,如果为您的类重写 hashCode() 方法,并且该方法违反了契约,则调用 contains() 方法可能会对集合中存在但在另一个存储桶中的元素返回 false

1.3.2 Effective Java中的方法

Joshua BlochEffective Java 中提供了一个生成 hashCode() 值的指导方法:

  1. 存储一些常量非零值;比方说17,在一个名为 resultint 变量中。
  2. 对于对象中的每个重要字段 fequals() 考虑的每个字段),请执行以下操作:

a. 为字段 c 计算一个 int 类型的 hashCode

i. 如果值域是一个布尔类型值,计算 c=(f?1:0)

ii. 如果域是一个 byte , char , short , int ,计算 c=(int)f

iii.如果域是一个 long 类型,计算 c=(int)(f^(f>>>32)).

iv.如果域是一个 float 类型,计算 c=Float.floatToIntBits(f).

v.如果域是一个 double 类型,计算 long l = Double.doubleToLongBits(f) , c = (int)(l^(l>>>32))

vi.如果该字段是对象引用,则 equals() 为该字段调用 equals() 。计算 c = f.hashCode()

vii.如果域是一个数组,将其视为每个元素都是一个单独的字段。

也就是说,通过将上述规则应用于每个元素来为每个重要元素计算 hashCode

b.将步骤2.a中计算的 hashCode c 组合到结果中,如下所示: result = 37 * result + c;

  1. 返回结果值
  2. 查看生成的 hashCode() 并确保相等的实例具有相同的哈希码。

以下是遵循上述准则的类的示例

public class HashTest { 
    private String field1; 
    private short field2; 
    @Override 
    public int hashCode() { 
        int result = 17; 
        result = 37*result + field1.hashCode(); 
        result = 37*result + (int)field2; 
        return result; 
    }
}

您可以看到选择常数37。选择这个数字的目的是它是一个素数。我们可以选择任何其他素数。

1.3.3 Apache HashCodeBuilder

编写好的 hashCode() 方法并不总是那么容易。由于正确实现 hashCode() 可能很困难,如果我们有一些可重用的实现,将会很有帮助。
Jakarta-Commonsorg.apache.commons.lang.builder 包提供了一个名为 HashCodeBuilder 的类,旨在帮助实现 hashCode()方法。
通常,开发人员很难实现 hashCode() 方法,这个类旨在简化流程。

以下是为上述类实现 hashCode 算法的方法:

public class HashTest { 
    private String field1; 
    private short field2; 
    @Override 
    public int hashCode() { 
        return new HashCodeBuilder(83, 7) .append(field1) .append(field2) .toHashCode(); 
    } 
}

请注意,构造函数的两个数字只是两个不同的非零奇数 - 这些数字有助于避免跨对象的 hashCode 值的冲突。

如果需要,可以使用 appendSuper(int) 添加超类 hashCode()

您可以看到使用 Apache HashCodeBuilder 重写 HashCode() 是多么容易。

1.4 可变对象作为 key

一般建议您应该使用不可变对象作为 Collection 中的键。从不可变数据计算时, HashCode 效果最佳。
如果您使用可变对象作为键并更改对象的状态以便hashCode更改,那么存储对象将位于 Collection 中的错误存储桶中。
在实现 hashCode() 时,您应该考虑的最重要的事情是,无论何时调用此方法,它都应该在每次调用时为特定对象生成相同的值。
如果你有一个类似于一个对象的场景,当它被 put() 到一个HaspMap并在 get() 期间产生另一个值时会产生一个 hashCode()值,
在这种情况下,你将无法检索该对象。

因此,如果您的 hashCode() 依赖于对象中的可变数据,那么通过生成不同的 hashCode() ,更改这些数据肯定会产生不同的密钥。

看下面的例子:

public class Employee { 
    private String name; 
    private int age; 
    public Employee() { } 
    public Employee(String name, int age) { 
        this.name = name; 
        this.age = age; 
    } 
    public String getName() { 
        return name; 
    }
    public void setName(String name) {
        this.name = name;
    }   
     public int getAge() { 
        return age; 
    } 
    public void setAge(int age) { 
         this.age = age; 
     } 
     @Override 
    public boolean equals(Object obj) { 
     //Remember: Some Java gurus recommend you avoid using instanceof 
        if (obj instanceof Employee) { 
            Employee emp = (Employee)obj; 
            return (emp.name == name && emp.age == age); 
        } 
        return false; 
     } 
     @Override 
    public int hashCode() { 
        return name.length() + age; 
     } 
     public static void main(String[] args) { 
         Employee e = new Employee("muhammad", 24); 
         Map<Object, Object> m = new HashMap<Object, Object>(); 
         m.put(e, "Muhammad Ali Khojaye"); 
         // getting output System.out.println(m.get(e)); e.name = "abid"; 
            // it fails to get System.out.println(m.get(e)); e.name = "amirrana"; 
            // it fails again System.out.println(m.get(new Employee("muhammad", 24)));
     } 
}

因此,您可以在上面的示例中看到我们如何获得一些不可预测的结果。
您可以使用 Joshua Recipe 或使用 HashCodeBuilder 类重写 hashCode() 来轻松修复上述问题。

这是一个例子:

1.4.1 示例建议:

@Override public int hashCode() {
    int result = 17; 
    result = 37*result + name.hashCode(); 
    result = 37*result + age; 
    return result; 
}

1.4.2 使用HashCodeBuilder

@Override
public int hashCode() { 
    return new HashCodeBuilder(83, 7).append(name).append(age).toHashCode(); 
}

1.4.3 可变字段作为键的另外一个例子

让我们来看一下这个例子:

public class HashTest {
    private int mutableField;
    private final int immutableField; 
    public HashTest(int mutableField, int immutableField) { 
        this.mutableField = mutableField; 
        this.immutableField = immutableField; 
    } 
    public void setMutableField(int mutableField) { 
        this.mutableField = mutableField; 
    } 

    @Override 
    public boolean equals(Object o) { 
        if(o instanceof HashTest) { 
            return (mutableField == ((HashTest)o).mutableField) && (immutableField == ((HashTest)o).immutableField); 
        }else { 
            return false; 
        } 
    }

    @Override 
    public int hashCode() { 
        int result = 17; result = 37 * result + this.mutableField; 
        result = 37 * result + this.immutableField; 
        return result; 
    } 
    public static void main(String[] args) { 
        Set<HashTest> set = new HashSet<HashTest>(); 
        HashTest obj = new HashTest(6622458, 626304); 
        set.add(obj); System.out.println(set.contains(obj)); 
        obj.setMutableField(3867602); 
        System.out.println(set.contains(obj)); 
    }
}

更改可变字段后,计算出的 hashCode 不再指向旧存储桶,而 contains() 返回 false.
我们可以使用这些方法中的任何一种来解决这种情况.

  • 从不可变数据计算时,Hashcode 是最佳的;因此,请确保只有不可变对象才能用作 Collections 的键。
  • 使用我们的第一种技术实现 hashCode() ,即返回一个常量值但你必须意识到它会杀死桶机制的所有优点。
  • 如果你需要 hashCode 方法中包含的可变字段,那么你可以在创建对象时计算和存储哈希值,每当你更新可变字段时,你必须先从集合中删除它( set / map ),然后将它添加回
    更新后的集合。

1.5 内存泄漏与HashCode和Equal

如果未实现 equals()hashcode() ,则 Java 应用程序中可能会发生内存泄漏。
考虑下面的一个小代码示例,其中如果未实现 equals()hashcode() ,则 HashMap 保持引用处于活动状态。
结果, HashMap 通过重复添加相同的键而不断增长,最后抛出 OutOfMemoryError

public class HashcodeLeakExample { 
    private String id; 
    public HashcodeLeakExample(String id) { 
        this.id = id; 
    } 
    public static void main(String args[]) { 
        try { 
            Map<HashcodeLeakExample, String> map = new HashMap<HashcodeLeakExample, String>(); 
            while (true) { 
                map.put(new HashcodeLeakExample("id"), "any value"); 
            } 
        } catch (Exception ex) { 
            ex.printStackTrace(); 
        }
    } 
}
正文到此结束