Java 8 HashMap 无法正常工作

Question

自 Java 8 以来，我们正面临 HashMap 行为的奇怪问题。

当HashMap keys实现Comparable接口(interface)但是compareTo实现与equals不一致时HashMaps:

• 长得比他们应该长的大得多

• 它们包含多个相同元素的实例

• 附加到这些元素的值可能不同

• get(key) 结果取决于使用哪个键(即使键根据 equals 方法相等)。

我创建了一个小测试来重现该问题(见下文)。测试总是通过 Java 7(可能还有以前的版本)。使用 Java 8 时测试总是失败(除非我从类中删除 Comparable 接口(interface))。

我不确定这有多可修复，如果不能修复，是否可以在 javadoc 中明确强调如果要在哈希集合中使用对象，compareTo 必须与 equals 一致。

import java.util.HashMap;
import java.util.Map;

public class HashMapTest {
private static final char MIN_NAME = 'A';
private static final char MAX_NAME = 'K';
private static final int EXPECTED_NUMBER_OF_ELEMENTS = MAX_NAME - MIN_NAME    + 1;

private HashMap<Person, Integer> personToAgeMap;

HashMapTest() {
    personToAgeMap = new HashMap();
}

public static void main(String[] args) {
    HashMapTest objHashMap = new HashMapTest();
    System.out.println("Initial Size of Map: "
            + objHashMap.getPersonToAgeMap().size());
    objHashMap.whenOverridingEqualElements_thenSizeOfTheMapIsStable();
           objHashMap.whenGettingElementUsingPersonOfAge1_thenOverridenValuesAreReturned();
    objHashMap.whenGettingElementUsingPersonOfAge100_thenOverridenValuesAreReturned();
    objHashMap.whenGettingElementUsingPersonOfAge50_thenOverridenValuesAreReturned();
    objHashMap
            .whenGettingElementUsingPersonOfAgeMinus1_thenOverridenValuesAreReturned();
}

public HashMap<Person, Integer> getPersonToAgeMap() {
    return personToAgeMap;
}

public void whenOverridingEqualElements_thenSizeOfTheMapIsStable() {
    System.out.println("Adding elements with age 1..");
    putAllPeopleWithAge(personToAgeMap, 1);
    System.out.println(personToAgeMap);
    System.out.println("Expected Number Of elements: " + EXPECTED_NUMBER_OF_ELEMENTS
            + "\nActual Number of elements: " + personToAgeMap.size());

    System.out.println();
    System.out.println("Overwriting map, with value 100..");
    putAllPeopleWithAge(personToAgeMap, 100);
    System.out.println(personToAgeMap);
    System.out.println("Expected Number Of elements: " + EXPECTED_NUMBER_OF_ELEMENTS
            + "\nActual Number of elements: " + personToAgeMap.size());
    System.out.println();
}

public void whenGettingElementUsingPersonOfAge1_thenOverridenValuesAreReturned() {
    useAgeToCheckAllHashMapValuesAre(1, 100);
}

public void whenGettingElementUsingPersonOfAge100_thenOverridenValuesAreReturned() {
    useAgeToCheckAllHashMapValuesAre(100, 100);
}

public void whenGettingElementUsingPersonOfAge50_thenOverridenValuesAreReturned() {
    useAgeToCheckAllHashMapValuesAre(50, 100);
}

public void whenGettingElementUsingPersonOfAgeMinus1_thenOverridenValuesAreReturned() {
    useAgeToCheckAllHashMapValuesAre(-10, 100);
}

private void useAgeToCheckAllHashMapValuesAre(int age, Integer expectedValue) {
    System.out.println("Checking the values corresponding to age = " + age);
    StringBuilder sb = new StringBuilder();

    int count = countAllPeopleUsingAge(personToAgeMap, age);
    System.out.println("Count of People with age " + age + " =" + count);

    if (EXPECTED_NUMBER_OF_ELEMENTS != count) {
        sb.append("Size of the map ").append(" is wrong: ").append("expected <")
                .append(EXPECTED_NUMBER_OF_ELEMENTS).append("> actual <")
                .append(count).append(">.\n");
    }

    for (char name = MIN_NAME; name <= MAX_NAME; name++) {
        Person key = new Person(name, age);
        Integer value = personToAgeMap.get(key);
        if (!expectedValue.equals(value)) {
            sb.append("Unexpected value for ").append(key).append(": ")
                    .append("expected <").append(expectedValue).append("> actual <")
                    .append(value).append(">.\n");
        }
    }

    if (sb.length() > 0) {
        System.out.println(sb.toString());
    }
}

void putAllPeopleWithAge(Map<Person, Integer> map, int age) {
    for (char name = MIN_NAME; name <= MAX_NAME; name++) {
        map.put(new Person(name, age), age);
    }
}

    int countAllPeopleUsingAge(Map<Person, Integer> map, int age) {
     int counter = 0;
    for (char name = MIN_NAME; name <= MAX_NAME; name++) {
        if (map.containsKey(new Person(name, age))) {
            counter++;
        }
        }
       return counter;
    }

String getAllPeopleUsingAge(Map<Person, Integer> map, int age) {
    StringBuilder sb = new StringBuilder();
    for (char name = MIN_NAME; name <= MAX_NAME; name++) {
        Person key = new Person(name, age);
        sb.append(key).append('=').append(map.get(key)).append('\n');
    }
    return sb.toString();
   }

class Person implements Comparable<Person> {
    char name;
    int age;

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

     // Making sure all elements end up in the very same bucket
    // Nothing wrong with it except performance...
     @Override
    public int hashCode() {
        return 0;
     }

    // equals is only by name
     @Override
    public boolean equals(Object other) {
        Person otherPerson = (Person) other;
        return this.name == otherPerson.name;
     }

    public String toString() {
         return name + "[age=" + age + "]";
    }

    // compareTo is inconsistent with equals which should be OK in
    // non-sorted collections
    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }
   }
}

Answer 1

HashMap documentation说:

To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

因此，如果使用具有不一致比较顺序的 Comparable 元素，就必须预料到像这样的奇怪行为。

在 Java 8 中 HashMap 的实现笔记中也明确提到了该行为:

/*
 * Implementation notes.
 *
 ...
 * Tree bins (i.e., bins whose elements are all TreeNodes) are
 * ordered primarily by hashCode, but in the case of ties, if two
 * elements are of the same "class C implements Comparable<C>",
 * type then their compareTo method is used for ordering. (We
 * conservatively check generic types via reflection to validate
 * this -- see method comparableClassFor). 
 ...

这是在 OpenJDK 的以下更改中引入的:http://hg.openjdk.java.net/jdk8/jdk8/jdk/diff/d62c911aebbb/src/share/classes/java/util/HashMap.java#l1.73