使用Integer作为Java中HashMap的键

Question

最近我一直在寻找hashCode()Java API 中方法的良好实现,并查看Integer源代码.没想到,但hashCode()刚刚返回支持的int价值.

public final class Integer ... {
private final int value;
...
    public int hashCode() {
        return Integer.hashCode(value);
    }
    public static int hashCode(int value) {
        return value;
    }

这很奇怪,因为有很多论文和页面以及专门用于解决这个问题的软件包 - 如何设计好的哈希函数来分配值.

最后我得出了这个结论:

Integer是与键一起使用的最差数据类型候选者HashMap,因为所有连续键都将位于一个bin/bucked中.就像上面的例子一样.

Map<Integer, String> map = HashMap<>();

for (int i = 1; i < 10; i++) {
    map.put(Integer.valueOf(i), "string" + i);
}

有两个问题,谷歌搜索时没有找到答案:

1. 我对Integer数据类型的结论是否正确？
2. 万一这是真的,为什么Integer's hashCode()在使用电源操作,素数,二进制移位时,方法不能以某种棘手的方式实现？

Answer 1

当与HashMap一起使用时,Integer是键的最差数据类型候选者,因为所有连续键都将位于一个bin中

不,这种说法是错误的.

事实上,实行Integer的hashCode()是最好的实现.它将每个Integer值映射到唯一hashCode值,这样可以减少将不同键映射到同一个存储桶的机会.

有时简单的实现是最好的.

从Javadoc中hashCode()的Object类:

根据java.lang.Object.equals(java.lang.Object)方法,如果两个对象不相等,则不需要在两个对象中的每一个上调用hashCode方法必须生成不同的整数结果.但是,程序员应该知道为不等对象生成不同的整数结果可能会提高哈希表的性能.

Integer是少数几个实际上保证不等对象会有所不同的类之一hashCode().

Answer 2

除了@Eran的答案之外，JavaHashMap还具有针对“坏哈希函数”的保护（虽然Integer.hashCode()不是，但仍然如此）。

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

因此，在使用 HashMap 时，整数的“简单哈希”实际上会有所不同。