해시 맵의 생성자에서 노드 값 초기화 C++

Question

문자열로 저장되는 사용자 이름과 암호를 저장하는 해시 맵을 생성해야합니다. 이 해시 맵은 별도로 연결됩니다. 값을 추가하거나 값을 검색 할 때 정수를 반환하는 키에 해시 함수를 사용한다고 가정합니다.이 정수는 함수를 사용해야하는 버킷 인덱스를 제공합니다. 뭔가를 추가하는 경우 목록의 끝에 저장합니다.

그래서 (내 마음 속에) 해시 맵은 다음과 같이 보일 것이다 :

:

Bucket | List 
[0] -> nullptr 
[1] -> (key1/value1) -> (key2/value2) 
[2] -> (key3/value3) 

각 키/값 콤보 이런 내 헤더 파일에 변경 불가능한 구조를 가지고 노드, 기술적으로

struct Node 
{ 
    std::string key; 
    std::string value; 
    Node* next; 
}; 

내 추가 및 검색 기능이 기술적으로 작동하지만 내 생성자에서 내 해시 맵을 올바르게 초기화하여 이 아닌이 비 초기화 값으로 비교됩니다. 내 생성자가 지금 얼마나 이것은 : 문제는

HashMap::HashMap() 
    : hashTable{new Node*[initialBucketCount]}, amountOfBuckets{initialBucketCount}, sz{0} 
{ 
    for(int i = 0; i < amountOfBuckets; i++) { 
     hashTable[i] = nullptr; 
    } 
} 

, 내 추가 기능처럼, 뭔가를 비교할 때, 나는 조건부 점프를하고 나하고있어 말한다 Valgrind의에 오류가 있다는 것입니다 초기화되지 않은 값으로 이동하십시오. 예를 들어, 추가에이 일을 :

Node* current = hashTable[tableIndex]; 
if(current == nullptr) 
    return false; 

는 if(current == nullptr)가 초기화되지 않은 값을 참조하는 것을 말할 것이다.

hashmap 생성자에서 값을 제대로 초기화하는 방법은 무엇입니까? 특히 나는 목록의 시작 부분을 nullptr과 같은 값으로 비교하여 다음 목록을 다음 목록에 넣어야 할 위치를 결정할 수있는 함수에서 무언가를하고 싶습니다.

편집 : 다음은 모든 파일이 하나의 파일로 압축 된 것입니다.

/* HashMap.cpp */ 
namespace { 
    unsigned int hashFunc(const std::string& key) 
    { 
     unsigned int hashValue = 0; // what we end up returning 
     for(int i = 0; i < key.length(); i++) { // iterate through string 
      int letterIndex = key.at(i) - 96; // create an index for each ASCII char 
      hashValue = hashValue * 27 + letterIndex; 
     } 
     return hashValue; 
    } // end hashFunc 
} 
class HashMap 
{ 
public: 
    typedef std::function<unsigned int(const std::string&)> HashFunction; 
    static constexpr unsigned int initialBucketCount = 10; 

private: 
    struct Node 
    { 
     std::string key; 
     std::string value; 
     Node* next; 
    }; 
    HashFunction hasher; 
    Node** hashTable; 
    unsigned int amountOfBuckets; 
    unsigned int sz; 
public: 
    HashMap() 
    : hashTable{new Node*[initialBucketCount]}, amountOfBuckets{initialBucketCount}, sz{0} 
    { 
    for(int i = 0; i < amountOfBuckets; i++) { 
     hashTable[i] = nullptr; 
    } 
    } 
    HashMap(HashFunction hasher) 
    : hasher{hashFunc}, hashTable{new Node*[initialBucketCount]()}, amountOfBuckets{initialBucketCount}, sz{0} 
    { 
    for(int i = 0; i < amountOfBuckets; i++) { 
     hashTable[i] = nullptr; 
    } 
    } 
    HashMap(const HashMap& hm) 
    : hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz} 
    { 
     for(unsigned int i = 0; i < sz; i++) { 
      hashTable[i] = hm.hashTable[i]; 
     } // end for 
    } 
    ~HashMap() 
    { 
    for(unsigned int i = 0; i < amountOfBuckets; i++) { 
     Node* bucketNode = hashTable[i]; // store each hashtable list in a bucket node 
     while(bucketNode != nullptr) { 
      Node* deleteCurrent = bucketNode; // set current to the bucket node (head) 
      bucketNode = bucketNode->next; // delete current is on the first node, update head to second node 
      delete deleteCurrent; 
     } // end while 
    } // end for 
    // once done, delete hash table 
    delete[] hashTable; 
    } // end destructor 

    void add(const std::string& key, const std::string& value) 
    { 
    unsigned int hashedValue = hashFunc(key); // get hash value (unmodified by buckets) 
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index 
    if(contains(key) == true) { // if key is already in the hashtable 
     return; // exit program 
    } else { // otherwise, key is not in the hash table 
     Node* head = hashTable[tableIndex]; // head of the hash table, represents 
     Node* current = head; // set current to first node 
     if(current == nullptr) { // no nodes yet 
      // nothing in bucket 
      current = new Node(); // construct single node 
      current->key = key; // set key (username) 
      current->value = value; // set value (password) 
      current->next = head; // add value to head of list 
      hashTable[tableIndex] = current; // update current to point to front of list 
      return; // exit 
     } else { 
      while(current->next != nullptr) { 
       current = current->next; // advance to next node 
      } // end while 
      // currently at node we want to insert key/value at 
      current = new Node(); 
      current->key = key; // set key(username) 
      current->value = value; // set value (pw) 
      current->next = nullptr; // set next to point to nullptr 
     } // end inner if-else (creates node) 
    } // end outer if-else 
    } // end add 
    bool contains(const std::string& key) const 
    { 
    unsigned int hashedValue = hashFunc(key); // hash the key given to get an index 
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index 
    Node* current = hashTable[tableIndex]; 
    if(current == nullptr) { // if there are no nodes at given index 
     return false; 
    } else { // there are some nodes in the hash table 
     while(current != nullptr && current->key != key) { 
      current = current->next; 
     } // end while 
     if(current == nullptr) { // we reached the end of our linked list 
      return false; // couldn't find a value 
     } else { // we found the key provided 
      return true; 
     } 
    } // end if-else 
    } 
    std::string value(const std::string& key) const 
    { 
     if(contains(key) == true) { // found match 
      unsigned int hashedValue = hashFunc(key); // hash the key given to get an index 
      unsigned int tableIndex = getTableIndex(hashedValue); // get the table index 
      Node* current = hashTable[tableIndex]; 
      while(current != nullptr && current->key != key) { 
       current = current->next; 
      } 
      return current->value; // return value after traversal 
     } else { 
      return ""; // no match, return empty string 
     } 
    } 
}; // end class 
/* main.cpp */ 

int main() 
{ 
    // initialize test 
    HashMap test1; 
    std::cout << "TEST 1 HASHMAP OBJECT CREATED" << std::endl; 
    // add some values 
    std::string key1 = "Alex"; 
    std::string value1 = "password1"; 
    std::string key2 = "Danielle"; 
    std::string value2 = "password2"; 
    std::cout << "strings have been created" << std::endl; 
    // add to hash map 
    test1.add(key1, value1); 
    test1.add(key2, value2); 
    std::cout << "Keys and values have been added to hash map" << std::endl; 
    // does key1 contain the word "hi"? no, should return false (0) 
    std::cout << "Hash map contains word hi?: " << test1.contains("hi") << std::endl; 
    // does key2 contain word "Danielle"? yes, should return true (1) 
    std::cout << "Hash map contains word Danielle?: " << test1.contains("Danielle") << std::endl; 
    // copy constructor test 
    HashMap test2{test1}; 
    test2.add("Chicken", "lizard1"); 
    std::cout << "Password for user Chicken: " << test2.value("Chicken") << std::endl; 
    HashMap test3 = test2; 
    // pw should stay lizard1 (doesn't work rn) 
    std::cout << "Password for user Chicken after copy: " << test3.value("Chicken") << std::endl; 
    // check to see if we get value 
    std::cout << "Password for user " << key1 << ": " << test1.value(key1) << std::endl; 
    std::cout << "Password for user " << key2 << ": " << test1.value(key2) << std::endl; 
    // should return empty string 
    std::cout << "Test of incorrect password for invalid user INVALID: " << test1.value("lol") << std::endl; 
    return 0; 
} 

Answer 1

당신은

// initialize each node to nullptr from the array of buckets to nullptr 

의 ctor 기본의 의견에 쓰기 그리고 완전히 다른 뭔가를 진행합니다. 그리고 그 다른 것은 완전히 잘못되었습니다. 모든 노드 ptrs가 동일한 노드를 가리 키도록 초기화합니다. 즉, 파괴시 동일한 노드를 여러 번 삭제하고 충돌하고 태우는 것을 의미합니다.

경고도 수정하십시오.

업데이트 명백한 오류를 수정 한 후 새로운 버전의 코드에는 손상된 복사본 생성자와 할당 연산자가 있습니다.

hashTable[i] = hm.hashTable[i]; 

두 개의 해시 테이블이 데이터 요소를 공유하게됩니다. 공유하지 않고 복사하고 싶습니다. 그리고 sz 버킷이 아닌 모든 버킷을 복사하려고합니다 (sz을 업데이트하지 않지만 다른 문제가 있음).