给定了一个完美的散列函数，计算包含

Question

给定一组完整的散列函数S，可以计算S中包含的整数，即如果整数不在S中，可以在不读取散列表本身，如果一个整数是S，你能不告诉散列表吗？假设我们有一个最小的完美散列函数。所以哈希表的大小是n，S的大小是m，n = m。我很抱歉，如果这是显而易见的。

Answer 1

不，您不能，因为完美的散列函数会将每个可能的整数映射到索引。

您可以做的是：对于每个密钥，仅存储一些附加信息，例如该密钥的哈希码的最后几位。这样，你可以说（以一个可配置的概率;它取决于你存储多少数据）整数是否为可能在集合中。这与bloom过滤器基本相同（您可以获得误报，但不会产生误报）。