如果哈希码计算超过整数最大限制会发生什么？

Question

这里是Java HashTable类中的hashCode()实现。如果哈希表中的元素数量很大，而哈希码超过了整数最大值-2,147,483,648到2,147,483,647怎么办？我假设哈希码将是正整数。

 public synchronized int hashCode() {

    int h = 0;
    if (count == 0 || loadFactor < 0)
        return h;  // Returns zero

    loadFactor = -loadFactor;  // Mark hashCode computation in progress
    Entry[] tab = table;
    for (int i = 0; i < tab.length; i++)
        for (Entry e = tab[i]; e != null; e = e.next)
            h += e.key.hashCode() ^ e.value.hashCode();
    loadFactor = -loadFactor;  // Mark hashCode computation complete

    return h;
}

- Akh

---

高于 int 类型（32 位）限制的位将被丢弃。 - nhahtdh

如果哈希表中的元素数量很大怎么办？这不用担心 - 哈希表需要处理冲突。没有要求也没有保证哈希码是唯一的（实际上，不能做出这样的保证）。 - Damien_The_Unbeliever

System.out.println("Are hashCodes always positive?".hashCode()); 输出 -835520151 ;) ，意思是“哈希码总是正数吗？” - Peter Lawrey

Answer 1

我认为哈希码将是正整数。

不，不一定。它们只是整数。它们肯定可以是负数，并且在计算哈希码时发生整数溢出也没问题。理想的哈希码将均匀地分布在其范围内 (int在这种情况下)。任何使用哈希码的东西都必须考虑到值可能为负数的可能性。

- Jon Skeet

---

如果我知道我的hashCode在某个小范围内，是否有办法告诉HashMap只为这个范围创建桶？这比为所有2^32个数字创建桶更有效率。 - banarun

@banarun：不，但是据我所知，桶并不仅仅通过查看范围来选择。除非你有具体证据表明这会导致问题，否则我不会担心它。 - Jon Skeet

如果例如，HashMap的容量大于（或等于）hashCode范围，则从hashCode到桶的一对一映射将是最有效的。但如果HashMap对整个整数范围进行桶分配，则情况就不同了。 - banarun

@banarun: 再次问一下，你有证据证明这实际上在你的应用程序中造成了问题吗？如果是这样，我建议你提出一个新问题，并提供一个完整的示例。（请指明你是否可以更改哈希算法...） - Jon Skeet

Answer 2

有时候整数溢出可能不适合您的需求。我说这是因为有时候。我仍然没有遇到过这种情况，但我想要防止它。

我会给你粘贴我用来生成哈希码的代码。我通常通过获取对象中的所有变量并将它们转换为字符串来进行计算。

public static int generateHashCode(String ... args)
{
    int length = 0;
    char[] cArray = null;
    if(args.length == 1) {
        length = args[0].length();
        cArray = args[0].toCharArray();
    }
    else {
        for(int i = 0; i < args.length; i++) {
            length += args[i].length();
        }

        cArray = new char[length];
        int incrementer = 0;
        for(int i = 0; i < args.length; i++) {
            String str = args[i];
            for(int j = 0; j < str.length(); j++) {
                cArray[incrementer] = str.charAt(j);
                ++incrementer;
            }
        }
    }

    int h = 0;
    for (int i = 0; i < cArray.length; i++) {
        h = 31*h + cArray[i];
    }

    return h;
}

- george_h