實現一個哈希表（重新掃描範圍錯誤）

Question

我在我的代碼中得到一個非常奇怪的錯誤。這個任務是針對我正在學習的課程，基本上我們正在學習如何實現一個哈希表。我得到的錯誤是當我嘗試重新散佈到更大的尺寸時。代碼的一部分給了我這個問題，我會更全面地解釋問題所在。

if(htable->size>=htable->cap) 
        { 
         cout<<htable->cap<<endl; 
         HashTable tempht=*htable; 
         delete htable; 
         htable=new HashTable((tempht.cap * 2) + 1); 



         for (size_t i=0; i<tempht.cap; i++) 
         { 

          Node* n=tempht.table[i]; 
          while (n!=NULL) 
          { 
           htable->add(n->item); 
           n=n->next; 
          } 
         } 
         if (htable->table[0]==NULL) 
         { 
          cout<<"HOORAY!"<<endl; 
         } 
        } 

        if (htable->table[0]==NULL) 
        { 
         cout<<"HOORAY!"<<endl; 
        } 
        else 
        { 
         cout<<htable->table[0]->item<<endl; 
        } 

htable是一個HashTable變量。在HashTable類中它包含一個數組Node*（節點只是我創建的包含字符串和指向鏈中下一項的指針的對象）。這部分代碼只是試圖重新映射到一個更大的表。我得到的問題是，一旦我退出第一個if語句，我的表的第一個值不再等於NULL（我正在運行的測試將表中沒有任何內容的表重新對一個表中仍然沒有任何內容，但有一個容量更大）。當我運行的代碼，第一htable->table[0]==NULL通行證，而第二個沒有，儘管那裏是沒有比if語句（我的預期的結果是，table[0]應該是NULL）退出其他變化。我最好的猜測是這是某種範圍的錯誤，但我真的不知道問題出在哪裏。任何幫助將不勝感激。

編輯：只是爲了澄清，初始哈希表的容量爲0（這是該項目的要求之一）。所以當我嘗試添加一個項目到表中時，這個if語句被執行（因爲大小是0並且上限是0，我們必須保持1的負載因子）。我可以證實，一旦表達到第一次和第二次「Hooray」檢查，htable->cap（這是數組的總容量）爲1，這應該是。唯一會被搞砸的是bucket 0（在這種情況下是唯一的bucket）。無論出於何種原因，它在退出if語句之前爲空，但在之後爲空。

我張貼我的整個HashTable課，讓我知道，如果你發現任何東西。

#pragma once 
#include <iostream> 
#include <string> 
#include <fstream> 
#include "Node.h" 
using namespace std; 
class HashTable 
{ 
public: 
    Node** table; 
    int size; 
    int cap; 
    HashTable (int c) 
    { 
     size=0; 
     cap=c; 
     table = new Node*[cap]; 

     if (cap>0) 
     { 

      for (size_t i=0; i<cap; ++i) 
      { 
       table[i]=NULL; 


      } 
     } 
    } 
    ~HashTable() 
    { 
     delete table; 
    } 
    size_t hash(string thing) 
    { 
     size_t total=0; 
     int asci; 
     char c; 
     size_t index; 

     for (size_t i=0; i<thing.length(); i++) 
     { 
      total=total*31; 
      c=thing[i]; 
      asci=int(c); 

      total=asci+total; 

     } 

     index=total%cap; 
        cout<<"index"<<index<<endl; 
      system("pause"); 

     return index; 
    } 
    void add(string thing) 
    { 


      size_t index; 
      index=hash(thing); 
         cout<<"index "<<index<<endl; 
      system("pause"); 
      Node* temp=table[index]; 
      if (temp==NULL) 
      { 
      cout<<"Here"<<endl; 
      system("pause"); 
      } 
      else 
      { 
          cout<<"Here2"<<endl; 
      system("pause"); 
         cout<<"temp"<<temp->item<<endl; 
      system("pause"); 
      } 
      Node* n = new Node(thing); 
      cout<<"n"<<n->item<<endl; 
      system("pause"); 
      if (temp==NULL) 
      { 

       table[index]=n; 
      } 
      else 
      { 
       while (temp->next!=NULL) 
       { 
        temp=temp->next; 
       } 
       temp->next=n; 
      } 

     size++; 
    } 
    Node* find(string search) 
    { 
     Node* n= NULL; 
     size_t index; 
     if(cap!=0) 
     { 
     index=hash(search); 
     Node* temp=table[index]; 
     while (temp!=NULL) 
     { 
      if (temp->item==search) 
      { 
       n=temp; 
       return n; 
      } 
     } 
     } 
     return n; 
    } 
    void remove (string thing) 
    { 
     if (find(thing)==NULL) 
     { 
      return; 
     } 
     else 
     { 
      size_t index; 
      index=hash(thing); 
      Node* temp=table[index]; 

      if (temp->item==thing) 
      { 
       table[index]=temp->next; 
       delete temp; 
      } 
      while (temp->next!=NULL) 
      { 
       if (temp->next->item==thing) 
       { 
        Node* temp2=temp->next; 
        temp->next=temp->next->next; 
        delete temp2; 
        break; 
       } 

      } 
     } 
     size--; 
    } 
    void print(ofstream &ofile) 
    { 

     for (size_t i=0; i<cap; i++) 
     { 
      Node* n=table[i]; 
      ofile<<"hash "<<i<<":"; 
      while (n!=NULL) 
      { 
       ofile<<" "<<n->item; 
       n=n->next; 
      } 
     } 
    } 

}; 

Answer 1

嗯，這是C++，而我更像是一個Java人，但我會採取一定的措施。

原來與後所有的

   HashTable tempht=*htable; 
       delete htable; 

塊的問題。

看到，第一行有表示，「從* htable複製所有成員進入tempht」。所以現在tempht和htable分享他們的表存儲，因爲表只是一個指向內存在建設分配的，你剛纔複製的指針。你想要它複製表內的節點，但它沒有這樣做。

所以，現在你有一個表相同的指針值兩個不同的哈希表對象。現在，當tempht被釋放時，析構函數在表指針上自由地調用，這有效地釋放了對象htable和tempht中的表數據。

你真正想要做的是寫一個拷貝構造函數，或做類似：

HashTable *tempht=htable; 
htable=new HashTable((tempht->cap * 2) + 1); 
for (size_t i=0; i<tempht->cap; i++) 
{ 

    Node* n=tempht->table[i]; 
    while (n!=NULL) 
    { 
     htable->add(n->item); 
     n=n->next; 
    } 
} 
if (htable->table[0]==NULL) 
{ 
    cout<<"HOORAY!"<<endl; 
} 
delete tempht; 

就能查看所有我真的做的是改變tempht一個指針，用它來指向老散列表，同時將所有節點從它複製到新的htable對象，然後刪除舊的散列表。