해시 테이블 구현 (rehash scope error)

Question

내 코드에 매우 이상한 오류가 나타납니다. 이 임무는 제가 택한 클래스를위한 것이고 본질적으로 우리는 해시 테이블을 구현하는 방법을 배우고 있습니다. 나가 얻고있는 과실은 나가 큰 크기에 시도하고 rehash 때이다. 여기에 코드의 일부가 나에게 문제를주고, 나는 그 문제가 무엇인지 더 자세히 설명 할 것이다.

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; 
        } 

htableHashTable는 가변적이다. HashTable 클래스에는 배열 Node*이 들어 있습니다 (노드는 문자열과 체인의 다음 항목에 대한 포인터가 포함 된 객체입니다). 코드의이 부분은 단순히 더 큰 테이블로 다시 해쉬하려고합니다. 내가 겪고있는 문제는 일단 첫 번째 if 문을 종료하면 내 테이블의 첫 번째 값은 더 이상 NULL과 같지 않습니다. (실행중인 테스트는 테이블에 아무 것도없는 테이블을 다시 해시합니다. 더 큰 용량). 코드를 실행할 때 첫 번째 htable->table[0]==NULL이 전달되지만 두 번째는 수행하지 않습니다. if 문을 종료하는 것 외에는 변경 사항이 없습니다 (내 예상 결과는 table[0]이 NULL이어야 함). 내 생각에 일종의 범위 지정 오류가 있지만 솔직히 문제가 어디에 있는지 알 수 없습니다. 어떤 도움이라도 대단히 감사하겠습니다.

편집 : 명확히하기 위해 초기 해시 테이블의 용량은 0입니다 (이는 프로젝트 요구 사항 중 하나입니다). 그래서 테이블에 항목을 추가하려고하면이 if 문이 실행됩니다 (크기가 0이고 뚜껑이 0이므로로드 계수 1을 유지해야합니다). 테이블이 첫 번째 및 두 번째 "만세"체크에 도달하면 htable->cap (배열의 총 용량)이 1이어야한다는 것을 확인할 수 있습니다. 엉망이되는 유일한 것은 버킷 0 (이 경우 유일한 버킷)입니다. 어떤 이유로 든 if 문을 종료하기 전에는 null이지만 after는 종료하지 않습니다.

내 전체 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++, 그리고 좀 더 자바 사람이야,하지만 난 그것을 자상 할게요.

문제 모든 후의

   HashTable tempht=*htable; 
       delete htable; 

블록 함께 낸다.

첫 번째 줄에는 "htable에서 모든 멤버를 tempht로 복사"라고 나와 있습니다. 그래서 이제는 테이블과 테이블이 건설시 할당 된 메모리 포인터이기 때문에 temft와 htable은 테이블 메모리를 공유합니다. 포인터을 복사했습니다. 테이블 안의 노드를 복사하길 원했지만 그렇게하지는 않았다.

이제 테이블에 동일한 포인터 값을 가진 두 개의 다른 HashTable 개체가 있습니다. 이제 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 객체로 복사하는 동안 다음 이전 Hashtable을 삭제합니다.