为什么HashMap使用TreeNode而不是Comparable键？

我知道在Java 8中HashMap针对分布不均的hashCode进行了优化。并且在超过阈值的情况下，它重建从链接列表到树状结构中的节点。此外，它是stated，此优化不适用于不可比较的密钥（在leas性能没有改进）。在下面的例子中，我把不Comparable键进入HashMap为什么HashMap使用TreeNode而不是Comparable键？

import java.util.HashMap; 
import java.util.Map; 
import java.util.concurrent.TimeUnit; 
import java.util.stream.IntStream; 

class Main { 
    public static void main(String[] args) throws InterruptedException { 
     Map<Key, Integer> map = new HashMap<>(); 

     IntStream.range(0, 15) 
       .forEach(i -> map.put(new Key(i), i)); 

     // hangs the application to take a Heap Dump 
     TimeUnit.DAYS.sleep(1); 
    } 
} 

final class Key { 
    private final int i; 

    public Key(int i) { 
     this.i = i; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 
     Key key = (Key) o; 
     return i == key.i; 
    } 

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

但检查堆转储表明节点被重新组合成树。

我的问题是，为什么节点被重建成树，如果它不会提高性能和标准，在这种情况下的节点进行比较，找出其中的关键应该是正确的节点，并留下吗？

来源

2017-07-15 Artem Petrov

我认为你有点误解了答案的意思。 Comparable不是需要，它只是一个优化，可能在散列相等时使用 - 以决定将条目移动到左侧还是右侧（perfectly balanced red-black tree node）。后来如果按键是不是可比，那它会用System.identityHashcode。

弄清楚哪个键应该是正确的节点，并留下

它转到正确的 - 更大的键转到正确的，但随后的树可能需要平衡。 一般来说，你可以查找的Tree如何成为perfectly balanced red black tree确切的算法，如here

来源

2017-07-15 11:12:04 Eugene

AFAIK它不使用标识哈希代码，只是关键对象的哈希码。 –

@JornVernee It * does *。查看'HashMap'里面的'tieBreakOrder'方法 – Eugene

@Eugene这是散列码相同的情况下的回退（散列碰撞不一定是这种情况，尽管我猜这是在这个例子中）。如果你看看它在'putTreeVal'中的使用位置，你会发现它试图在这之前使用密钥的哈希码。 –

为什么HashMap使用TreeNode而不是Comparable键？

回答

相关问题