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

Closed addressing hash tables. How are they resized?

阅读 hopscotch hashing 并试图理解它是如何编码的,我意识到在线性探测哈希 table 变体中,我们需要使用递归方法来调整大小,如下所示:

  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。
这是使用线性探测变体

时调整散列大小的标准方法 table

好问题!通常,在像跳房子哈希、布谷鸟哈希或静态完美哈希这样的封闭地址哈希中,重新哈希有可能失败,单个 "rehash" 步骤可能必须处于一个循环中,试图将所有内容分配到一个新的 table 直到找到可行的方法。

您可能需要考虑使用三种方法 - 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从不调用任何其他东西。

希望对您有所帮助!