32位键和32位指向值存储的指针的哈希表大小是多少?
将会是2^32个插槽 * (4字节(键)+ 4字节(指向值的指针)) = 4 * 10^9 * (4 + 4) = 32GB吗?
我正在尝试理解哈希表的空间复杂度。
我认为你提出的问题不太准确。数据结构的空间复杂度指的是它占用的空间与元素数量的关系。例如,空间复杂度为O(1)
意味着无论你往里面放多少元素,数据结构始终只占用恒定的空间。而O(n)
则表示空间消耗随元素数量线性增长。
通常哈希表的空间复杂度为O(n)
。
所以回答你的问题:这取决于哈希表当前存储的元素数量,还有实际实现方式在现实世界中也会起作用。
哈希表最低的内存消耗下限为:(要存储的值的数量)*(每个值的大小)。因此,如果你想在哈希表中存储一百万个值,每个值占用4个字节,那么它至少需要消耗400万字节(大约4MB)的空间。通常真实世界的实现还需要更多的基础设施的内存,但同样地:这高度取决于实际的实现方法,只有通过测量才能确定。
哈希表的哈希函数值和插槽不匹配。哈希函数是通过大小远小于哈希函数范围的引用向量进行模运算得到的。由于该值是固定的,因此在空间复杂度计算中不予考虑。
因此,每个合理哈希表的空间复杂度为O(n)。
一般来说,这种方法非常有效。虽然键空间可能很大,但要存储的值的数量通常很容易预测。当然,数据结构开销对于功能接受的内存量通常是明显的。
这就是为什么哈希表如此普遍。它们经常为给定任务提供最佳的数据结构,将严格绑定的内存开销与优于log2n的时间复杂度混合在一起。我喜欢二叉树,但它们通常无法击败哈希表。
假设我们有一个天真的哈希表,其中桶的数量等于元素数量的两倍。也就是说,元素数量是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
至今为止,对于这个问题仍然没有完美的答案。我不确定所占用的空间大小。 根据我对这个问题的理解,大小是动态的,并随输入的大小而变化。
也就是说我们从一个随机数开始,哈希表的大小比哈希函数值小得多。然后我们插入输入。现在,当发生冲突时,我们动态地将哈希表大小加倍。 我认为这就是O(n)复杂度的原因。如果我错误了,请指正。