封闭地址哈希表。它们如何调整大小？

Question

阅读关于 跳跃式哈希 的内容并试图理解如何进行编码，我意识到在线性探测哈希表变体中，我们需要采用递归方法来调整大小，具体步骤如下：

1. 创建现有桶的备份数组

2. 分配所需容量的新数组

3. 遍历备份数组，并重新哈希每个元素以获取元素在新数组中的新位置，并将其插入新数组中
4. 完成后释放备份数组

代码结构应该如下：

public V put(Object key, Object value) {  
   //code  
   //we need to resize)
   if(condition){  
       resize(2*keys.length);  
       return put(key, value);  
   }
   //other code
}  

private void resize(int newCapacity) {  
  //step 1 
  //step 2  
  //go over each element  
  for(Object key:oldKeys) {
    put(key, value);  
  }  
}

我不喜欢这种结构，因为我们在调整大小时会递归调用put函数。
使用线性探测变体时，这是调整哈希表大小的标准方法吗？

- Cratylus

Answer 1

很好的问题！通常，在闭合地址哈希中，如跳跃哈希、布谷鸟哈希或静态完美哈希中，存在重新哈希失败的可能性，因此单个“重新哈希”步骤可能必须坐在一个循环中，尝试将所有内容分配到新表中，直到找到可行的方法为止。

您可能需要考虑使用三种方法-put，外部可见函数，rehash，内部函数和tryPut，它尝试添加元素，但可能会失败。然后，您可以实现以下功能，这些功能主要用于阐述，并且肯定可以进行一些优化：

public V put(Object key, Object value) {
    V oldValue = get(key);
    while (!tryPut(key, value)) {
        rehash();
    }
    return oldValue;
}

private void rehash() {
    increaseCapacity();

    boolean success;
    do {
       success = true;
       reallocateSpace();

       for (each old key/value pair) {
          if (!tryPut(key, value)) {
             success = false;
             break;
          }
       }
    } while (!success);
}

private boolean tryPut(Object key, Object value) {
   // Try adding the key/value pair using a
   // hashtable specific implementation, returning
   // true if it works and false otherwise.
}

这里不再存在奇怪的递归风险，因为tryPut不会调用其他任何东西。

希望这可以帮到你！

- templatetypedef

---

我不是在谈论泄漏问题。1）但是，如果您最终执行new Object [Integer.MAX_VALUE]，如果堆空间未正确配置，则会出现OOM，2）您将无法再向表中插入任何内容，并且从调整大小循环中找出这一点似乎有点奇怪。但这影响的是闭合寻址思想，而不是答案，我认为这非常启发人。 - Cratylus

@Cratylus 是的，你绝对需要改变哈希函数。Cuckoo哈希绝对需要这样做，FKS完美哈希表也是如此，如果我没记错的话，Hopscotch哈希也是如此。通常，这些数据结构假定您有一组可用的哈希函数，以便在需要重新哈希时，可以更改表大小或哈希函数的选择。不幸的是，这使得这些系统比简单的线性探测或链接哈希更难使用，因为您需要一个更智能的哈希函数。 - templatetypedef

@Cratylus 我在聊天中打了几段话。如果你有任何问题，请随时在那里问！ - templatetypedef

我更新了聊天！你的评论实际上非常有趣。 - Cratylus

我正在准备一个测试套件。如果你有时间给我指点一下，我会告诉你结果的。 - Cratylus