试图理解哈希表中的代码在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只返回失败案件。声明为返回值的函数必须始终返回一个值。