Java 8哈希表无法正常工作 [英] Java 8 Hash Map not working properly

查看：75
本文介绍了Java 8哈希表无法正常工作的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述



当HashMap键实现Comparable接口，但compareTo实现与equals不一致时，HashMaps：

p>


  • 增长得多，然后它们应该增长

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

  • 与这些元素相关的值可能会有所不同。 获取（键）结果取决于使用哪个键（即使键等于根据equals方法）。




我创建了一个小测试来重现问题（见下文）。测试总是通过Java 7（以及可能以前的版本）。 Java 8的测试总是失败（除非我从类中移除了Comparable接口）。

我不确定这是多么可修复，如果不是这样在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; 
 
私有HashMap< Person，Integer> personToAgeMap; 
 
 HashMapTest（）{
 personToAgeMap = new HashMap（）; 
 
 
 public static void main（String [] args）{
 HashMapTest objHashMap = new HashMapTest（）; 
 System.out.println（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 
 +\\\
Actual元素数量：+ personToAgeMap.size（））; 
 
 System.out.println（）; 
 System.out.println（覆盖地图，值为100 ..）; 
 putAllPeopleWithAge（personToAgeMap，100）; 
 System.out.println（personToAgeMap）; 
 System.out.println（Expected Number Of Elements：+ EXPECTED_NUMBER_OF_ELEMENTS 
 +\\\
Actual元素数量：+ 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（检查对应于age =+ age的值）; 
 StringBuilder sb = new StringBuilder（）; 
 
 int count = countAllPeopleUsingAge（personToAgeMap，age）; 
 System.out.println（人数与年龄+年龄+=+计数）; 
 $ b $ if if（EXPECTED_NUMBER_OF_ELEMENTS！= count）{
 sb.append（地图大小）.append（is wrong：）.append（expected）
 .append（EXPECTED_NUMBER_OF_ELEMENTS）.append（> actual<）
 .append（count）.append（> .\\\
）; （char name = MIN_NAME; name< = MAX_NAME; name ++）{
 Person key = new Person（name，age）; 
 
 
 
整数值= personToAgeMap.get（key）; 
 if（！expectedValue.equals（value））{
 sb.append（Unexpected value for）.append（key）.append（：）
 .append（expected <）。append（expectedValue）.append（> actual<）
 .append（value）.append（> .\\\
）; 
 
 
 
 if（sb.length（）> 0）{
 System.out.println（sb.toString（））; （char name = MIN_NAME; name< = MAX_NAME; 
）
} 
 
 void putAllPeopleWithAge（Map< Person，Integer> map，int age） name ++）{
 map.put（new Person（name，age），age）; 
 
 
 
 int countAllPeopleUsingAge（Map< Person，Integer> map，int age）{
 int counter = 0; （$ name）= 
（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（'\\\
'）; 
} 
 return sb.toString（）; 
} 
 
类Person实现了Comparable< Person> {
 char name; 
 int age; 
 
 public Person（char name，int age）{
 this.name = name; 
 this.age =年龄; 
} 
 
 //确保所有元素都在同一个桶中结束
 //除性能外，没有任何错误... 
 @Override 
 public int hashCode（）{
 return 0; 
} 
 
 //等于只有名字
 @Override 
 public boolean equals（Object other）{
 Person otherPerson =（Person）other; 
返回this.name == otherPerson.name; 
 
 
 public String toString（）{
 return name +[age =+ age +]; 
} 
 
 // compareTo与equals中的值不一致，它应该在
中确定//非排序集合
 @Override 
 public int compareTo（Person其他）{
 return this.age  -  other.age;


解决方案

HashMap文档说：


为了改善影响，当键是Comparable时，这个类可以使用键之间的比较顺序来帮助断开连接。


因此，如果使用比较顺序不一致的 Comparable 元素，以期望像这样的奇怪行为。



在Java 8中的 HashMap 的实现注释中也明确提到了这种行为：

  / * 
 *实现说明。 
 * 
 ... 
 *树箱（即元素都是TreeNode的箱子）是
 *，主要由hashCode命令排序，但在捆绑的情况下，如果两个
 *元素是相同的C类实现Comparable< C>，
 *类型，那么它们的compareTo方法用于排序。 （我们b $ b *保守地通过反射检查泛型类型来验证
 * this  - 参见可比较的类ClassFor）。 
 ...

这是在OpenJDK的以下更改中引入的： http： $ h
$ / $>

We're facing weird issues with how HashMap behaves since java 8.

When HashMap keys implement Comparable interface but compareTo implementation is inconsistent with equals then HashMaps:

  • grow much larger then they are supposed to grow

  • they contain several instances of equal elements

  • values attached to those elements might differ

  • get(key) result depends on which key is used (even if the keys are equal according to equals method).

I've created a small test to reproduce the problem (see below). The test always passes with Java 7 (and probably previous versions). The test always fails with Java 8 (unless I remove Comparable interface from the class).

I'm not sure how fixable this is and if it's not would it be possible to explicitly underline in javadoc that compareTo MUST be consistent with equals if the objects are to be used in hash-collections. 

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;
    }
   }
}

解决方案

The HashMap documentation says:

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

So if one uses Comparable elements with an inconsistent comparison order, one has to expect odd behavior like this.

The behavior is also explicitly mentioned in the implementation notes of HashMap in Java 8:

/*
 * 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). 
 ...

This was introduced in the following change in the OpenJDK: http://hg.openjdk.java.net/jdk8/jdk8/jdk/diff/d62c911aebbb/src/share/classes/java/util/HashMap.java#l1.73

这篇关于Java 8哈希表无法正常工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
Java开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆