java - 调整大小后找不到哈希表中的旧元素？

Question

我正在为我的数据结构类创建自己的哈希表 adt，但遇到了一个问题。我使用以下函数对哈希表中的 (key,value) 条目进行哈希处理(键是字符串，值可以是任何数据类型，它是通用的):

private int hashCode(String key)
{
    final int constant = 37;
    int hash = 0;

    for(int i=0;i<key.length();i++)
    {
        hash+=(int)key.charAt(i) * Math.pow(constant,i);
    }
    return hash;
}
private int hash(String key)
{
    return hashCode(key) % capacity
}

使用线性探测插入到表中工作正常，但是如果我选择扩展表，哈希(键)函数将无法充分用于哈希表的 get(键)操作，因为容量已经改变(它会在表扩展名正确映射之前映射到不正确的位置)。有没有什么简单的方法可以编辑它，它考虑到哈希表的扩展，可以说是两倍。即:如果 loadfactor > 0.5 将表的容量增加 2*。

Answer 1

一般来说，当你重新哈希一个哈希表时，你需要遍历哈希表中的所有元素，并根据它们的哈希码重新分配它们，使它们最终位于正确的位置。这比正常调整大小要花费更多的时间，否则表格将无法正常工作。

另一种方法是使用不同的冲突解决方案，如 extendible hashing这是专门为避免在放置后移动东西而构建的，但考虑到线性探测散列在实践中的盲目速度有多快，我认为这种设置的减速可能不值得。