在哈希表中插入具有开放寻址的节点[优化逻辑]

Question

我试图理解一个数据结构，哈希表与开放寻址。

我目前正在阅读怪人提供的源代码，但我对代码有几个问题。

下面是来自极客的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; 
    } 

问题

1. 在第9行，你为什么要检查三个条件，

- 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 if `slot has the key of -1, which indicates the slot where node was deleted before` ===> `arr[hashIndex]->key != -1`

如果要优化这段代码，我相信检查slot is NULL or not是否已经足够了。

​

1. 在第17行中，为什么要在将节点分配给时隙之前增加HashMap的size属性？===> if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1) size++; 在我看来，这个逻辑似乎很混乱。 我宁愿这样做，arr[hashIndex] = temp; size++;

假设极客健忘者的逻辑写得很好，你能不能向我解释一下，why the logic for inserting the new node to a hash table with open addressing是按照我刚才提到的两点具体实现的？

Answer 1

有一个有效索引的三个条件是：

1. 索引处的对象为空。
2. 或者对象不是NULL，但它的键与我们要插入的那个相同
3. 或者对象不是空的，但是它的键值是-1。

由于所有三个条件都被否定，所以我们没有一个有效的索引，循环继续进行。

在第17行中:只有当插入不重用现有索引时，大小才会增加，因此节点是new (这意味着适用条件1或3)。