即使哈希表的大小增加了，get(key) 如何工作！

Question

如果一个Hashtable最初的大小为8，当它达到负载因子时，它会增长两倍。但是get方法仍然能够检索原始值...假设我们有一个哈希函数key(8)转换为12345作为哈希值，我们将其模除8并得到索引7...现在当哈希表大小增长到16时...对于key(8)，我们仍然得到12345..如果我们将其模除16，我们会得到一个不同的答案！那么我如何检索原始的key(8)呢？

- phoenix

Answer 1

这并不是Java特有的问题 - 当哈希表增长时（在我所知道的大多数实现中），它必须重新评估所有哈希对象的键，并根据现在可用的桶数将它们放入其新的正确桶中。

这也是为什么调整哈希表大小通常被认为是一项“昂贵”的操作（与许多其他操作相比）- 因为它必须访问其中存储的所有项目。

- Damien_The_Unbeliever

Answer 2

用于查找值的哈希值来自键对象本身，而不是容器。

这就是为什么在 Map 中用作键的对象必须是不可变的原因。如果 hashCode() 改变了，您将无法再次找到您的键或值。

- duffymo

---

在他的例子中，哈希值没有改变。提问者想知道当Hashtable增长时如何找到相同的哈希值，因此其模数可能会改变，这意味着不太可能在同一个桶中找到相同的值。然而关于键是不可变的这一点非常好。我从未考虑过在哈希表/哈希映射中是否会丢失我的键值对。 - nicholas.hauschild

Answer 3

具体实现取决于实际情况，但在必要时会发生 重新散列。

- nicholas.hauschild

Answer 4

查看HashMap类的源代码，在由resize()方法调用的transfer()方法中。

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

在这个HashTable实现中，您可以精确地了解每个条目如何存储在新的（两倍大）存储数组中。新数组的容量用于确定每个项将存储在哪个插槽中。键的哈希码不会改变（实际上甚至不会重新计算，而是从名为hash的每个Entry对象的公共字段中检索出来），改变的是indexFor()调用的结果：

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

该函数接受哈希码和新存储数组的长度，并返回新数组中的索引。

因此，客户端对get()的新调用将通过相同的indexFor()调用进行，该调用还将使用新存储数组的长度，一切都会很好。

- Tom Tresansky