Hashtable AddEntry 分离链分段错误

Question

我的分离链接哈希 Table 对象出现分段错误。

bool hashTable::addNode(int id, string information){
bool inserted = false;  
int position = hash(id);
cout << &hashtable[position]<<endl;
if(hashtable[position]==NULL){
    hashtable[position]->data.id = id;
    hashtable[position]->data.information = information;
    hashtable[position]->next = NULL;
    inserted = true;
} else {
    Node* current = new Node;
    current = hashtable[position];
    while(current!=NULL){
        if(id < hashtable[position]->data.id){
            current->data.id = id;
            current->data.information = information;
            current->next = hashtable[position];
            hashtable[position] = current;
            inserted = true;
        } else if(id < current->data.id){
            current->data.id = id;
            current->data.information = information;
            current->next = hashtable[position]->next;
            hashtable[position]->next = current;
            inserted = true;
        } else if(current->next==NULL){
            Node *temp;
            temp->next = NULL;
            temp->data.id = id;
            temp->data.information = information;
            current->next = temp;
            inserted = true;
        } 
        current = current->next;                
    
    }
}
return inserted;

}

本质上，我有一个头指针数组来处理单独的链接，但是 addNode 中的分段错误让我一头雾水。明确地说，我首先调用 public AddEntry，它为数组中的每个单独的 LinkedList 调用 AddNode。

#ifndef HASH_H
#define HASH_H

#include <iostream>
#include <string>
#include "data.h"

using std::string;
using std::cout;
using std::endl;

#define SIZE 15

class hashTable{
public:
    hashTable();
    ~hashTable();

    bool addEntry(int id, string information);
    string getEntry(int id);
    bool removeEntry(int id);
    int getCount();
    void displayTable();

private:
    bool removeNode(int id, int position);
    bool addNode(int id, string information);
    int count = 0;
    Node* hashtable = new Node[SIZE]; //array of head pointers
    int hash(int id);
};

#endif

对不起，如果我没有说这是最好的，这是我第一次使用 Stack Overflow。

Answer 1

您的代码中有几个地方看起来您使用的地址运算符 & 不正确。让我们从这个开始：

if (&hashtable[position] == NULL) {
   ...
}

我完全明白你在这里想做什么 - 你想说“如果索引 position 处的插槽包含空指针。”然而，这并不是这段代码实际做的。这表示“如果内存中 hashtable[position] 所在的位置本身就是一个空指针。”这是不可能的 - hashtable[position] 指的是数组中的一个槽 - 所以这个 if 语句永远不会触发。

在这里画图可能有助于更好地了解正在发生的事情。例如，假设您有一个空散列 table，如下所示：

 +-------+       +------+------+------+------+     +------+
 |       |------>| null | null | null | null | ... | null |
 +-------+       +------+------+------+------+     +------+
 hashtable

这里的hashtable[position]指的是hashtable指向的数组中索引position处的指针。对于空散列 table，hashtable[position] 的计算结果将是 NULL，因为这是该槽中指针的内容。另一方面，&hashtable[position] 指的是这样的东西：

                    &hashtable[position]
                        +-------+
                        |       |
                        +-------+
                            |
                            v
 +-------+       +------+------+------+------+     +------+
 |       |------>| null | null | null | null | ... | null |
 +-------+       +------+------+------+------+     +------+
 hashtable

这里，&hashtable[position]指向数组中的一个指针。虽然指针 &hashtable[position] 指向的是空指针，但 它本身不是空指针 ，因为它指向内存中的有效对象。

更改代码以读取

if (hashtable[position] == NULL) {
     ...
}

正确表达了“如果 hashtable 数组中索引 position 处的条目不是空指针。”的想法。

您的代码在其他几个地方也存在类似的错误。仔细阅读您的内容并着眼于以下问题：我想要 指针存储在数组中的某个索引 处，还是我想要 内存中的位置该指针恰好存在？

Hashtable AddEntry 分离链分段错误

Hashtable AddEntry Separate Chaining Segmentation Fault

c++

data-structures

hashtable

chaining