散列表的空间复杂度是多少？ [英] What is the space complexity of a hash table?

问题描述

32位密钥和32位指针分别存储在哈希表中的大小是多少？

是2 ^ 32时隙* 4字节（key）* 4字节（指向值的指针）
= 4 * 10 ^ 6 * 4 * 4 = 64MB？

散列表。

解决方案

散列表与散列函数值和插槽不匹配。散列函数是以比散列函数范围小得多的参考矢量的大小来计算的。因为这个值是固定的，所以在空间复杂度计算中不考虑它。

因此，每个合理散列表的空间复杂度为O（n）。

一般来说，这可以很好地解决。虽然关键空间可能很大，但要存储的值的数量通常很容易预测。当然，数据结构开销在功能上可接受的内存数量通常很明显。

这就是哈希表如此无处不在的原因。它们通常为给定任务提供最好的数据结构，将严格限制的内存开销与log时间复杂度相比较。我喜欢二叉树，但他们通常不会打哈希表。

What is size of a hash table with 32 bit key and 32 bit pointers to values stored separately?

Is it going to be 2^32 slots * 4 Bytes (key) * 4 Bytes (pointers to values) = 4 * 10^6 * 4 * 4 = 64MB ?

I am trying to understand space complexity of hash tables.

解决方案

Hash tables don't match hash function values and slots. The hash function is computed modulo the size of a reference vector that is much smaller than the hash function range. Because this value is fixed, it is not considered in the space complexity computation.

Consequently, the space complexity of every reasonable hash table is O(n).

In general, this works out quite well. While the key space may be large, the number of values to store is usually quite easily predictable. Certainly, the amount of memory that is functionally acceptable for data structure overhead is typically obvious.

This is why hash tables are so ubiquitous. They often provide the best data structure for a given task, mixing strictly bounded memory overhead with better than log₂ n time complexity. I love binary trees but they don't usually beat hash tables.

这篇关于散列表的空间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！