java - 封闭寻址哈希表。它们是如何调整大小的？

Question

正在阅读 hopscotch hashing并试图理解它是如何成为代码的，我意识到在线性探测哈希表变体中，我们需要一种递归方法来调整大小，如下所示:

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 inside resize。
这是使用线性探测变体时调整哈希表大小的标准方法吗

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 从不调用任何其他东西。

希望这对您有所帮助!