hash - 多维哈希的空间复杂度

Question

我想存储一个制表符分隔值的输入，其中 C1、C2、C3 和 C4 表示数据的列，并且有 N 行数据。如果是这样，我可以在哈希中进行查找以查看 C1、C2、C3、C4 的某些给定值是否存在。有人向我建议，在最坏的情况下，它的空间复杂度是 N ⁴。我想帮助制定一个明确的解释，说明为什么这是不正确的。

Answer 1

另一个人在想，如果您尝试存储 N × N 网格点，将有 N ⁴个点要存储。

但是如果你有 N 个点，那么你只是在存储一个哈希值。具有 N 个数据点的散列通常占用 O(N) 空间。（从技术上讲，它需要哈希表的大小加上数据空间，但人们通常动态地将哈希表的大小调整为与数据集大小相同的数量级。）