Java HashMap碰撞攻击耗时过短，如何实现插入全碰撞字符串耗时超20秒

问题根因 #

你当前测试耗时远低于预期的核心原因是JDK 8及以上版本对HashMap做了红黑树优化：当单个哈希桶内的链表长度超过8且HashMap总容量大于64时，该桶的存储结构会自动从链表转为红黑树，插入的时间复杂度从链表的O(N)降到O(logN)，即便是17万条碰撞数据插入也能在几秒内完成。

解决方案 #

方案1：使用JDK 7及更早版本运行测试 #

JDK 7及更早版本的HashMap没有红黑树优化，所有碰撞节点全部以链表存储，插入17万条相同哈希值的字符串时，时间复杂度为O(N²)，实测耗时可轻松超过20秒。你不需要修改任何现有代码，直接更换JDK版本运行即可。

方案2：修改Java测试代码规避红黑树转换（适用于JDK 8+版本） #

HashMap只有在Key实现了Comparable接口时才会将碰撞链表转为红黑树，我们可以自定义Key类，固定返回相同的hashCode，且不实现Comparable接口，强制HashMap始终使用链表存储碰撞节点。
修改后的Java测试代码如下：

import java.util.*;

// 自定义Key类，不实现Comparable，固定hashCode
class CollisionKey {
    private final String content;

    public CollisionKey(String content) {
        this.content = content;
    }

    @Override
    public int hashCode() {
        // 替换为你生成的所有字符串统一的hash值即可
        return 3050920;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        CollisionKey that = (CollisionKey) o;
        return Objects.equals(content, that.content);
    }
}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<CollisionKey, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            map.put(new CollisionKey(s), s.hashCode());
        }
        System.out.println(map.size());
        sc.close();
    }
}

修改后运行测试，17万条数据插入耗时即可达到20秒以上，如果你需要更长耗时，可调整Python脚本的组合层数，生成更多碰撞字符串即可。

额外优化建议 #

如果你当前测试耗时还是不够长，可关闭JIT编译再运行Java程序，运行命令添加参数：java -XX:-TieredCompilation -Xint Main，关闭编译优化后运行速度会进一步下降。

内容的提问来源于stack exchange，提问作者Sai Suman Chitturi