Вставка узла в таблицу Ha sh с открытой адресацией [Оптимизация логики] - PullRequest
Новая
       83

Вставка узла в таблицу Ha sh с открытой адресацией [Оптимизация логики]

1 голос
/ 17 июня 2020

Я пытаюсь понять структуру данных, например, таблицу sh с открытой адресацией.
В настоящее время я читаю исходный код, предоставленный geekforgeeks , но у меня есть несколько вопросов по code.

Ниже приведена вставленная функция для inserting Node от geekforgeeks. 

//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, зачем вам проверять три условных оператора, так как

    • если slot inside the hash table is null ===> arr[hashIndex] != NULL
    • И если slot has the same key with the node that is going to be inserted ===> arr[hashIndex]->key != key
    • И если slot has the key of -1, which indicates the slot where node was deleted before = ==> arr[hashIndex]->key != -1

      Если бы я оптимизировал этот код, я бы проверил, достаточно ли slot is NULL or not.

  2. В строке 17 зачем увеличивать свойство size HashMap перед назначением узла слоту? ===> if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1) size++;
    Мне этот лог c кажется беспорядочным.
    Я бы предпочел, arr[hashIndex] = temp; size++;

С предположение geekforgeeks logi c хорошо написано, не могли бы вы объяснить мне, что why the logic for inserting the new node to a hash table with open addressing реализовано, как указано выше, конкретно по двум пунктам, которые я поднял?

1 Ответ

1 голос
/ 17 июня 2020

Три условия для наличия допустимого индекса:

  1. Объект с индексом NULL
  2. ИЛИ объект не равен NULL, но его ключ такой же, как и у объекта. один, который мы вставляем
  3. ИЛИ объект не равен NULL, но его значение ключа -1

Так как отрицание из all три условия, у нас нет действительного индекса, и l oop катится.

В строке 17: размер увеличивается только , если вставка не выполняется повторно использовать существующий индекс, чтобы узел был new (что означает, что применяется условие 1 или 3).

...