32位键和32位指向值存储的指针的哈希表大小是多少？
将会是2^32个插槽 * (4字节（键）+ 4字节（指向值的指针）) = 4 * 10^9 * (4 + 4) = 32GB吗？
我正在尝试理解哈希表的空间复杂度。
4个回答
20
我认为你提出的问题不太准确。数据结构的空间复杂度指的是它占用的空间与元素数量的关系。例如，空间复杂度为O(1)意味着无论你往里面放多少元素，数据结构始终只占用恒定的空间。而O(n)则表示空间消耗随元素数量线性增长。
通常哈希表的空间复杂度为O(n)。
所以回答你的问题：这取决于哈希表当前存储的元素数量，还有实际实现方式在现实世界中也会起作用。
哈希表最低的内存消耗下限为：（要存储的值的数量）*（每个值的大小）。因此，如果你想在哈希表中存储一百万个值，每个值占用4个字节，那么它至少需要消耗400万字节（大约4MB）的空间。通常真实世界的实现还需要更多的基础设施的内存，但同样地：这高度取决于实际的实现方法，只有通过测量才能确定。
- ChrisWue
2
但如果我需要估计一个哈希表占用多少空间...考虑到产生32位键的哈希函数...并且假设我在存储指向其他地方存储的值的指针，那我可以这样做吗？ - Megha Joshi - GoogleTV DevRel
非常感谢，真的很感激。我还有点困惑，我在另一个答案上添加了评论。 - Megha Joshi - GoogleTV DevRel
12
哈希表的哈希函数值和插槽不匹配。哈希函数是通过大小远小于哈希函数范围的引用向量进行模运算得到的。由于该值是固定的，因此在空间复杂度计算中不予考虑。
因此，每个合理哈希表的空间复杂度为O(n)。
一般来说，这种方法非常有效。虽然键空间可能很大，但要存储的值的数量通常很容易预测。当然，数据结构开销对于功能接受的内存量通常是明显的。
这就是为什么哈希表如此普遍。它们经常为给定任务提供最佳的数据结构，将严格绑定的内存开销与优于log2n的时间复杂度混合在一起。我喜欢二叉树，但它们通常无法击败哈希表。
- DigitalRoss
4
假设我有一个哈希表，当我创建它时，我不知道要存储多少元素...所以我没有指定容量。我猜默认的负载因子是0.75。现在我对我的第一个值进行哈希，它是一个字符串S，h(S)产生了一个键4294967294。我将这个键和一个4字节指针存储在我的哈希表中。此时...有没有办法估计它占用了多少内存？根据空间复杂度O(n)，它应该只占用4字节键+4字节值+对象本身的一些开销（头、填充等）。没有预先分配2^32个插槽..是这样吗？ - Megha Joshi - GoogleTV DevRel
1是的。一个典型的哈希表可能最初会作为一个包含100个（空）指针的数组开始，而安装的第一个值将指向像您描述的对象一样的对象。 - DigitalRoss
有没有办法计算通常需要多长时间来生成哈希值？（例如对于1 PB的数据） - Arash
@Arash 没有固定的答案。这取决于所使用的哈希函数、可用的 CPU 动力和 I/O 带宽。 - ChrisWue
2
假设我们有一个天真的哈希表，其中桶的数量等于元素数量的两倍。也就是说，元素数量是O(n)，那么桶的数量是O(2n)。
当元素数量超过可用桶数量的一半时，您需要创建一个新的桶数组，将大小翻倍，并将所有元素重新散列到新桶数组中的新位置。
386 public V put(K key, V value) {
387 if (key == null)
388 return putForNullKey(value);
389 int hash = hash(key.hashCode());
390 int i = indexFor(hash, table.length);
391 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392 Object k;
393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394 V oldValue = e.value;
395 e.value = value;
396 e.recordAccess(this);
397 return oldValue;
398 }
399 }
401 modCount++;
402 addEntry(hash, key, value, i);
403 return null;
404 }
768 void addEntry(int hash, K key, V value, int bucketIndex) {
769 Entry<K,V> e = table[bucketIndex];
770 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
771 if (size++ >= threshold)
772 resize(2 * table.length);
773 }
471 void resize(int newCapacity) {
472 Entry[] oldTable = table;
473 int oldCapacity = oldTable.length;
474 if (oldCapacity == MAXIMUM_CAPACITY) {
475 threshold = Integer.MAX_VALUE;
476 return;
477 }
479 Entry[] newTable = new Entry[newCapacity];
480 transfer(newTable);
481 table = newTable;
482 threshold = (int)(newCapacity * loadFactor);
483 }
488 void transfer(Entry[] newTable) {
489 Entry[] src = table;
490 int newCapacity = newTable.length;
491 for (int j = 0; j < src.length; j++) {
492 Entry<K,V> e = src[j];
493 if (e != null) {
494 src[j] = null;
495 do {
496 Entry<K,V> next = e.next;
497 int i = indexFor(e.hash, newCapacity);
498 e.next = newTable[i];
499 newTable[i] = e;
500 e = next;
501 } while (e != null);
502 }
503 }
504 }
参考:
Grepcode已经无法使用，您可以查看此处的openjdk存储库作为更好的参考： http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java
- joseph
0
至今为止，对于这个问题仍然没有完美的答案。我不确定所占用的空间大小。 根据我对这个问题的理解，大小是动态的，并随输入的大小而变化。
也就是说我们从一个随机数开始，哈希表的大小比哈希函数值小得多。然后我们插入输入。现在，当发生冲突时，我们动态地将哈希表大小加倍。 我认为这就是O(n)复杂度的原因。如果我错误了，请指正。
- Anshu Kandhari
1
1这是一个答案还是一个问题？ - Austin Henley
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接