get（key）在哈希表的大小已经增长之后如何工作！

Question

如果一个Hashtable最初的大小为8，并且我们达到了负载因子，并且它的尺寸增加了一倍。如何得到仍然能够检索原始值...所以说我们有一个散列函数键（8）转换为12345作为我们修改了8的散列值，我们得到索引7 ...现在当散列表大小增长到16 ...对于关键（8）我们得到12345 ..如果我们将它改为16，我们将得到不同的答案！那么我该如何检索原始密钥（8）

Answer 1

这不是Java特定的 - 当散列表增长时（在我所知的大多数实现中），它必须重新评估所有哈希对象的关键字，并将它们放入新的正确存储桶中，水桶现在可用。

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

Answer 2

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

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

Answer 3

这是所有的实施依赖，但必要时会发生rehash。

Answer 4

看一下方法中的HashMap类的来源，该方法由resize()方法调用。

/** 
    * 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); 
      } 
     } 
    } 

此哈希表的实现，你可以按照准确每个条目是如何存储新（两倍大）存储阵列英寸新阵列的容量用于确定每个项目将被存储在哪个插槽中。按键的哈希码不会改变（它其实即使不重新计算，而是从每个Entry对象，它被保存在名为hash公共领域检索），什么样的变化是indexFor()调用的结果：

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

它采用散列码和新存储阵列的长度并返回新数组中的索引。

因此，客户对get()的新呼叫将通过同一个indexFor()呼叫，这也将使用新存储阵列的长度，并且一切都会好的。