hashmap - 哈希表的空间复杂度是多少？

Question

具有 32 位 key 和 32 位指向单独存储的值的指针的哈希表的大小是多少？

它会是 2^32 个插槽 *(4 字节(键)+ 4 字节(指向值的指针))
= 4 * 10^9 * (4 + 4) = 32GB ？

我试图了解哈希表的空间复杂度。

Answer 1

哈希表不匹配哈希函数值和槽。散列函数是以比散列函数范围小得多的引用向量的大小为模计算的。因为这个值是固定的，所以在空间复杂度计算中不考虑。

因此，每个合理的哈希表的空间复杂度都是 O(n)。

一般来说，这很有效。虽然键空间可能很大，但要存储的值的数量通常很容易预测。当然，数据结构开销在功能上可接受的内存量通常是显而易见的。

这就是哈希表如此普遍的原因。它们通常为给定的任务提供最好的数据结构，将严格有界的内存开销与优于 log2 n 的时间复杂度混合在一起。我喜欢二叉树，但它们通常不会击败哈希表。