C++でハッシュテーブルコードを理解しようとしています

Question

ハッシュテーブルを学習していて、別のWebサイトでこのコードが見つかりましたが、Insert（int key、int value）関数の理解に問題があります。 この関数はうまくいきますが、不要なコードがあるか、それとも完全に理解していないのか不思議です。

具体的には、関数の最後に、他の条件：

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) 

の前にありがとうentryがelseケースが不可能であることを保証する、NULLでない限りwhile (entry != NULL)ループの外方法はありません。

私は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のみ失敗に返します場合。値を返すと宣言された関数は常に値を返す必要があります。