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

希望这对您有所帮助!