試圖理解哈希表中的代碼在c + +

Question

我正在學習哈希表，並在另一個網站上找到此代碼，但無法理解插入（int鍵，int值）函數。 該函數運行良好，但我想知道是否有額外的代碼是不需要的，或者如果我不完全理解它。

具體地說，在函數結束的其他條件：

else 
{ 
    entry->value = value; 
} 

它似乎沒有以往任何時候都達到這個條件，當我使用不同的參數調用該函數。這是其餘的代碼。

#include<iostream> 
#include<cstdlib> 
#include<string> 
#include<cstdio> 
using namespace std; 
const int TABLE_SIZE = 128; 

class HashNode 
{ 
public: 
    int key; 
    int value; 
    HashNode* next; 
    HashNode(int key, int value) 
    { 
     this->key = key; 
     this->value = value; 
     this->next = NULL; 
    } 
}; 

class HashMap 
{ 
private: 
    HashNode** htable; 
    public: 
    HashMap() 
    { 
     htable = new HashNode*[TABLE_SIZE]; 
     for (int i = 0; i < TABLE_SIZE; i++) 
      htable[i] = NULL; 
    } 
    ~HashMap() 
    { 
     for (int i = 0; i < TABLE_SIZE; ++i) 
     { 
      HashNode* entry = htable[i]; 
      while (entry != NULL) 
      { 
       HashNode* prev = entry; 
       entry = entry->next; 
       delete prev; 
      } 
     } 
     delete[] htable; 
    } 
    /* 
    * Hash Function 
    */ 
    int HashFunc(int key) 
    { 
     return key % TABLE_SIZE; 
    } 

    /* 
    * Insert Element at a key 
    */ 
    void Insert(int key, int value) 
    { 
     int hash_val = HashFunc(key); 
     HashNode* prev = NULL; 
     HashNode* entry = htable[hash_val]; 
     while (entry != NULL) 
     { 
      prev = entry; 
      entry = entry->next; 
     } 
     if (entry == NULL) 
     { 
      entry = new HashNode(key, value); 
      if (prev == NULL) 
      { 
       htable[hash_val] = entry; 
      } 
      else 
      { 
       prev->next = entry; 
      } 
     } 
     else 
     { 
      entry->value = value; 
     } 
    } 

    /* Search Element at a key 
    */ 
    int Search(int key) 
    { 
     bool flag = false; 
     int hash_val = HashFunc(key); 
     HashNode* entry = htable[hash_val]; 
     while (entry != NULL) 
     { 
      if (entry->key == key) 
      { 
       cout << entry->value << " "; 
       flag = true; 
      } 
      entry = entry->next; 
     } 
     if (!flag) 
      return -1; 
    } 
}; 

int main() 
{ 
    HashMap hash; 
    hash.Insert(3, 7); 
    hash.Search(3); 
} 

任何澄清高度讚賞。

謝謝

Answer 1

while (entry != NULL) 

先

if (entry == NULL) 

沒有出路while (entry != NULL)循環，除非entry是NULL，低保else情況下是不可能的。

我相信在while循環測試，以查看密鑰是否已經存在是必需的。

while (entry != NULL) 
{ 
    if (entry->key == key) 
    { 
     break; 
    } 
    prev = entry; 
    entry = entry->next; 
} 

題外話：看看這個問題，並回答有關如何簡化代碼的建議：Using pointers to remove item from singly-linked list

例子：

/* 
* Insert Element at a key 
*/ 
void Insert(int key, int value) 
{ 
    int hash_val = HashFunc(key); 
    HashNode** nextPtr = &htable[hash_val]; // Get a pointer to next, not to the entry 
    // with a pointer to next we can keep going from next to next without 
    // ever needing a previous. 
    // pick up a whole bunch of extra dereferencing *nextPtr, but an 
    // optimizing compiler is great at dealing with that extra overhead. 
    while ((*nextPtr) != NULL) // loop until found or end 
    { 
     if ((*nextPtr)->key == key) // found key already in list 
     { 
      (*nextPtr)->value = value; // set value for key 
      return; // all done. 
     } 
     nextPtr = &(*nextPtr)->next; // keep looking 
    } 
    *nextPtr = new HashNode(key, value); // didn't find. Add new node to end. 
} 

附錄：Search只返回失敗案件。聲明爲返回值的函數必須始終返回一個值。