java - 如何计算 Java 中字符串列表中的冲突次数

Question

如何使用每个字符串的哈希码来计算字符串列表中的所有冲突对？

public class HashCollisions {
private static int strLength;
private static int colls;

public static void main(String[] args) {

    String[] strings ={"AaAaAa","AaAaBB","AaBBAa","AaBBBB"};

    strLength=strings.length;
    for (int i = 0; i < strLength - 1; i++) {
        for (int j = i + 1; j < strLength; j++) {
            if (hash(strings[i]) == hash(strings[j]) && !(strings[i].equals(strings[j]))) {
                    colls++;
            }
        }
    }

    System.out.println(colls);

}

private static byte hash(String s) {
    byte[] bytes = s.getBytes();
    byte result = bytes[0];

    for (int i = 1; i < bytes.length; i++) {
        result ^= bytes[i];
    }

    return result;
}

}

• 根据给定的输入，我应该检测碰撞对的计数:{0=[AaAaBB, AaBBAa], 32=[AaAaAa, AaBBBB]} 将为 2。
• 还有比 O(n^2) 更高效的其他解决方案吗？

Answer 1

您可以按 hashCode 对字符串列表进行分组，然后使用生成的映射。一旦给定键有多个值，就会出现 碰撞:

public static void main(String[] args) {
    List<String> strings = Arrays.asList("foo", "bar", "AaAa", "foobar",
            "BBBB", "AaBB", "FB", "Ea", "foo");
    Map<Integer, List<String>> stringsByHash = strings.stream()
            .collect(Collectors.groupingBy(String::hashCode));
    for (Entry<Integer, List<String>> entry : stringsByHash.entrySet()) {
        List<String> value = entry.getValue();
        int collisions = value.size() - 1;
        if (collisions > 0) {
            System.out.println(
                    "Got " + collisions + " collision(s) for strings "
                            + value + " (hash: " + entry.getKey() + ")");
        }
    }
}

打印:

Got 1 collision(s) for strings [foo, foo] (hash: 101574)
Got 1 collision(s) for strings [FB, Ea] (hash: 2236)
Got 2 collision(s) for strings [AaAa, BBBB, AaBB] (hash: 2031744)