Meg*_*Rel 11 hash hashtable hashmap
具有32位密钥和32位指针的哈希表的大小是多少？
它是2 ^ 32个插槽*(4个字节(键)+ 4个字节(指向值的指针))= 4*10 ^ 9*(4 + 4)= 32GB？
我试图了解哈希表的空间复杂性.
Chr*_*Wue 13
我想你问的是错误的问题.数据结构的空间复杂性表明它占据的空间相对于它所拥有的元素数量.例如,空间复杂性O(1)意味着无论您放入多少元素,数据结构都会消耗恒定的空间.O(n)意味着空间消耗随着其中元素的数量线性增长.
哈希表通常具有空间复杂度O(n).
所以回答你的问题:它取决于它当前存储的元素数量,以及现实世界中实际实现的元素数量.
哈希表的内存消耗的下限是:(要存储的值的数量)*(SizeOf a Value).因此,如果您想在哈希表中存储100万个值,每个值占用4个字节,那么它将消耗至少400万个字节(大约4MB).通常,现实世界的实现会为基础设施使用更多的内存,但同样:这在很大程度上取决于实际的实现,并且没有办法确定但是要测量它.
Dig*_*oss 10
散列表与散列函数值和插槽不匹配.以比散列函数范围小得多的参考向量的大小为模计算散列函数.由于此值是固定的,因此在空间复杂度计算中不予考虑.
因此,每个合理的哈希表的空间复杂度是O(n).
总的来说,这很好.虽然密钥空间可能很大,但存储的值的数量通常很容易预测.当然,功能上可接受的数据结构开销的内存量通常是显而易见的.
这就是哈希表无处不在的原因.它们通常为给定任务提供最佳数据结构,混合严格限制的内存开销,优于log 2 n时间复杂度.我喜欢二叉树,但他们通常不会打哈希表.