两个哈希码相加会产生碰撞的概率有多大？

Question

如果在Java中添加了另外两个哈希码生成一个新的哈希码，那么发生碰撞的概率是多少？

例如：

Integer reportHashCode = reportFields.hashCode() + reportId.hashCode();

假设Java的哈希码是32位，我们可以忽略哈希码本身的普通冲突。

- Stenal P Jolly

---

哈希码在这种情况下被异或的原因是有道理的... - Eugene

我应该使用异或运算符而不是加法吗？ - Stenal P Jolly

我认为你的意思是“溢出”，而不是“碰撞”。 - SJuan76

哦！我完全没有考虑到这个问题。是的，这很可能会导致溢出，对吧？ - Stenal P Jolly

@StenalPJolly使用xor的另一个原因。但即使发生溢出，哈希映射/集合中使用的哈希码也不会受到影响。int的溢出仍然是int。 - Eugene

Answer 1

我建议在这里使用XOR运算符而不是加法，因为XOR具有50-50％的1和0分布。

- Eugene

---

此外，值得一看的是以下答案，其中更详细地解释了50-50%分配。https://dev59.com/RG025IYBdhLWcg3wpHl_ - SubOptimal

Answer 2

我们来尝试一下吧？以下程序将为您模拟这个过程。请注意，求和的两个加数是随机生成的，因此都有大约完整的整数范围概率。实际上，您相加的两个哈希码可能不会在整个整数空间上具有平坦的分布。该程序可以进行调整以模拟这种情况。

package hashcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class HashCode {
    // Number of test cases
    private static final int TEST_CASES = 10_000_000;
    public static void main(String[] args) {
        // Random number generator
        Random rand = new Random();
        // Map from integers (result hash codes) to a list of addend pairs that formed those hash codes
        Map<Integer, Set<Pair>> hashCodesToComposites = new HashMap<>();
        // Number of collissions
        int collisions = 0;
        // Running simulations
        for (int i = 0; i < TEST_CASES; ++i) {
            if (TEST_CASES / 4 == i) {
                System.out.println("25 %");
            }
            if (TEST_CASES / 2 == i) {
                System.out.println("50 %");
            }
            if ((TEST_CASES * 3) / 4 == i) {
                System.out.println("75 %");
            }
            // Generating addends as random integers
            int first = rand.nextInt();
            int second = rand.nextInt();
            // The pair; its hash code is the sum of the above
            Pair pair = new Pair(first, second);
            // Did it occur before?
            if (hashCodesToComposites.containsKey(pair.hashCode())) {
                // Getting the set of addend pairs that created this hash code
                Set<Pair> composites = hashCodesToComposites.get(pair.hashCode());
                // Checking if by any chance the two random numbers happened to be the same (almost negligible)
                if (!composites.contains(pair)) {
                    // Actual collision from different numbers
                    collisions++;
                    // Adding to the set of composites
                    composites.add(pair);
                } // Same numbers; doesn't count as collision
            } else {
                // First occurrence of this hash code
                Set<Pair> composites = new HashSet<>();
                composites.add(pair);
                hashCodesToComposites.put(pair.hashCode(), composites);
            }
        }
        // Results
        System.out.println("Test cases: " + TEST_CASES);
        System.out.println("Collisions: " + collisions);
        System.out.println("Probability: " + ((double) collisions / (double) TEST_CASES));
    }
    private static class Pair {
        final int first;
        final int second;
        final int hashCode;
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
            hashCode = first + second;
        }
        @Override
        public int hashCode() {
            return hashCode;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            final Pair other = (Pair) obj;
            return (this.first == other.first && this.second == other.second) || (this.first == other.second && this.second == other.first);
        }
    }
}

结果通常在0.00115左右。这意味着大约有0.115％的碰撞几率。我运行了下面的代码，以查找仅随机整数之间的碰撞概率。

package hashcode;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class HashCode2 {
    // Number of test cases
    private static final int TEST_CASES = 10_000_000;
    public static void main(String[] args) {
        // Random number generator
        Random rand = new Random();
        Set<Integer> hashCodes = new HashSet<>();
        // Number of collissions
        int collisions = 0;
        // Running simulations
        for (int i = 0; i < TEST_CASES; ++i) {
            if (TEST_CASES / 4 == i) {
                System.out.println("25 %");
            }
            if (TEST_CASES / 2 == i) {
                System.out.println("50 %");
            }
            if ((TEST_CASES * 3) / 4 == i) {
                System.out.println("75 %");
            }
            int next = rand.nextInt();
            if (hashCodes.contains(next)) {
                collisions++;
            } else {
                hashCodes.add(next);
            }
        }
        // Results
        System.out.println("Test cases: " + TEST_CASES);
        System.out.println("Collisions: " + collisions);
        System.out.println("Probability: " + ((double) collisions / (double) TEST_CASES));
    }
}

实际上，它们的概率差不多。只是略微低一些，但仍会四舍五入为0.115%。最后，我再次尝试了第一个程序，但是在Pair的hashCode方法中使用了异或运算而不是加法。结果呢？基本上又是一样的。因此，最终你可以期望得到非常接近于随机整数的碰撞率，对于两个哈希码的和与异或运算，前提是这两个哈希码被相加/异或的分布很好。

- G_H