为什么 HashSet 不能直接在内部使用位数组而不是 HashMap 来节省一些空间？

Question

我看到 Java 中的 HashSet 在内部使用 HashMap 来检查 HashSet 是否包含元素。它不能只使用位图来存储字符串的所有哈希结果吗？例如。字符串 abc 散列为 12 个索引，我们可以设置此索引以表明它存在。与 HashMap 相比，它会节省大量空间，因为我们不必在数据中存储实际的键。

Answer 1

如果 HashSet 仅用于 contains() 查找，那么这样的优化是可能的。它仍然很危险，因为散列冲突总是会发生。我认为您正在寻找的是布隆过滤器（请注意，布隆过滤器不会给出确切的答案，它只是排除漏报）。Hash Set 是一个集合，集合需要有可能检索存储的值。哈希是不可逆的，你不能从它的哈希中计算出原始字符串。