使用开放寻址在哈希 table 中插入节点 [优化逻辑]

Question

我正在尝试理解一种数据结构，散列 table 具有开放寻址。
我目前正在阅读 geekforgeeks 提供的源代码，但我对代码有一些疑问。

下面是 geekforgeeks 为 inserting Node 粘贴的函数。

//Function to add key value pair 
    void insertNode(K key, V value) 
    { 
        HashNode<K,V> *temp = new HashNode<K,V>(key, value); 

        // Apply hash function to find index for given key 
        int hashIndex = hashCode(key); 

        //find next free space  
        while(arr[hashIndex] != NULL && arr[hashIndex]->key != key  //// LINE 9 //////
               && arr[hashIndex]->key != -1) 
        { 
            hashIndex++; 
            hashIndex %= capacity; 
        } 

        //if new node to be inserted increase the current size 
        if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1)    //// LINE 17 //////
            size++; 
        arr[hashIndex] = temp; 
    }

问题

在第 9 行，你为什么要检查三个条件，being，
- if slot inside the hash table is null ===> arr[hashIndex] != NULL
- AND if slot has the same key with the node that is going to be inserted ===> arr[hashIndex]->key != key
- AND 如果slot has the key of -1, which indicates the slot where node was deleted before ===> arr[hashIndex]->key != -1
  
  如果我要优化这段代码，我相信检查 slot is NULL or not 是否已经足够了。
在第 17 行中，为什么要在将节点分配给槽之前增加 HashMap 的大小属性？ ===> if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1) size++;
在我看来，这个逻辑似乎很混乱。
我宁愿做，arr[hashIndex] = temp; size++;

假设geekforgeeks的逻辑写的很好，你能不能给我解释一下 why the logic for inserting the new node to a hash table with open addressing 是如何具体针对我提出的两点实现的？

Answer 1

索引有效的三个条件是：

索引处的对象为 NULL
OR 对象不为 NULL，但其键与我们插入的键相同
OR 对象不为 NULL，但其键值为 -1

由于所有三个条件的否定发生，我们没有有效的索引，循环继续。

第 17 行：如果插入不重用现有索引，则大小增加仅，因此节点为 new（这意味着条件 1 或3 个适用）。

使用开放寻址在哈希 table 中插入节点 [优化逻辑]

Inserting node in Hash table with open addressing [Optimizing the logic]

c++

hashtable

data-structures