2

从java HashMap的源码中可以清楚的看出，当达到空间阈值时，它的空间扩大了两次。

我想到了一个用例，其中所有 6 个元素以链接方式存储在同一索引下。当第 7 个元素到达时，阈值为 7(10*.75) 的 HashMap(size 10) 得到扩展。这里实际上不需要扩展，因为所有都保存在一个索引下。

请赐教

        void addEntry(int hash, K key, V value, int bucketIndex)
        {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }

        void resize(int newCapacity)
        {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }

            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable);
            table = newTable;
            threshold = (int)(newCapacity * loadFactor);
        }
4

3 回答 3

3

你说没有必要调整大小，因为HashMap可以容纳这些条目。

然而，HashMap理想情况下应该提供恒定的访问时间（O(1)）。调整大小是为了尝试提供此访问时间。通过重新组织存储桶，对键的查找应该理想地引用只有一个值的存储桶（以避免遍历条目列表）。

在get()方法中你会发现这一行：

for (Entry<K,V> e = table[indexFor(hash, table.length)];

HashMap 是使用该indexFor()方法来识别桶，然后它会遍历桶以找到匹配的键。为了优化这一点，理想情况下迭代应该只发生一次（你不能避免桶查找）

这表明哈希码在理想情况下均匀分布在int范围 (2^31-1) 中。您可以将对象的哈希码设为常量（例如 1），但随后您会看到 HashMap 只能将所有条目转储到一个存储桶中，因此无法执行任何操作，从而影响性能。

于 2012-12-27T10:26:08.807 回答
1

这只是一个设计决定。可能是基于地图在检索和存储方面应该非常快的事实，如果您最终链接了这么多条目，性能将会受到影响。因此，重新散列可能会将您的项目分散到存储桶中，而不是将它们链接在一个存储桶中。

于 2012-12-27T10:30:22.137 回答
0

它是一种贸易。大小较小时位于同一桶中的所有元素将随着大小的增加而分散。这提高了性能。

于 2014-09-11T18:31:21.657 回答