HashTable 实现 Get 和 Set 运算符重载
HashTable Implementation Get and Set Operator Overloading
我正在尝试实现 basic 哈希表。我正在使用链表来解决冲突。
我的 get 和 set 方法给我带来了很多麻烦,我不太确定问题出在哪里。我相信我正确地超载了运营商。我认为当我追加到我的链接列表时会出现问题。
class HashTable {
struct Node{
int key;
int value;
Node *next;
};
Node **table;
int hash_func(int key) const {
return key % TABLE_SIZE;
}
public:
HashTable() {
table = new Node*[TABLE_SIZE]();
for (int i = 0; i < TABLE_SIZE; ++i)
table[i] = nullptr;
}
int& operator[](int const key) {
int h_key = hash_func(key);
while(table[h_key]) {
table[h_key] = table[h_key]->next;
}
table[h_key] = new Node;
table[h_key]->key = key;
table[h_key]->next = table[h_key];
return table[h_key]->value;
}
int operator[](int const key) const {
int h_key = hash_func(key);
while (table[h_key]) {
if (table[h_key]->key == key) {
return table[h_key]->value;
}
table[h_key] = table[h_key]->next;
}
return 0;
}
};
您的问题是您在 get 和 set 方法的 while
循环中覆盖 数据。
当您执行 table[h_key] = table[h_key]->next;
时,您 将永久丢失 最初存储在位置 h_key
的任何内容。相反 使用占位符,像这样:
Node * curr = table[h_key];
while (curr->next)
{
curr = curr->next;
}
Node * new_node = new Node;
new_node->key = key;
curr->next = new_node;
您的 get 方法也有类似的问题。
在您的 setter 中,您想在末尾插入一个新元素。所以首先你找到这样的结尾:
while(table[h_key]) {
table[h_key] = table[h_key]->next;
}
但是,你设置了:
table[h_key]->next = table[h_key];
相反,您必须设置:
table[h_key]->next = nullptr;
否则,你在循环中的条件不起作用。
将此答案视为@bpachev 答案的附录。我的代码仅说明了使用您的错误代码的问题,并非直接解决方案。
我同意 bpachev。因为这是 C++,你应该考虑使用模板来做这样的事情(消除混乱和重用)。使用模板 类 的开销很小,这个过程在编译时完成。
我正在尝试实现 basic 哈希表。我正在使用链表来解决冲突。
我的 get 和 set 方法给我带来了很多麻烦,我不太确定问题出在哪里。我相信我正确地超载了运营商。我认为当我追加到我的链接列表时会出现问题。
class HashTable {
struct Node{
int key;
int value;
Node *next;
};
Node **table;
int hash_func(int key) const {
return key % TABLE_SIZE;
}
public:
HashTable() {
table = new Node*[TABLE_SIZE]();
for (int i = 0; i < TABLE_SIZE; ++i)
table[i] = nullptr;
}
int& operator[](int const key) {
int h_key = hash_func(key);
while(table[h_key]) {
table[h_key] = table[h_key]->next;
}
table[h_key] = new Node;
table[h_key]->key = key;
table[h_key]->next = table[h_key];
return table[h_key]->value;
}
int operator[](int const key) const {
int h_key = hash_func(key);
while (table[h_key]) {
if (table[h_key]->key == key) {
return table[h_key]->value;
}
table[h_key] = table[h_key]->next;
}
return 0;
}
};
您的问题是您在 get 和 set 方法的 while
循环中覆盖 数据。
当您执行 table[h_key] = table[h_key]->next;
时,您 将永久丢失 最初存储在位置 h_key
的任何内容。相反 使用占位符,像这样:
Node * curr = table[h_key];
while (curr->next)
{
curr = curr->next;
}
Node * new_node = new Node;
new_node->key = key;
curr->next = new_node;
您的 get 方法也有类似的问题。
在您的 setter 中,您想在末尾插入一个新元素。所以首先你找到这样的结尾:
while(table[h_key]) {
table[h_key] = table[h_key]->next;
}
但是,你设置了:
table[h_key]->next = table[h_key];
相反,您必须设置:
table[h_key]->next = nullptr;
否则,你在循环中的条件不起作用。
将此答案视为@bpachev 答案的附录。我的代码仅说明了使用您的错误代码的问题,并非直接解决方案。
我同意 bpachev。因为这是 C++,你应该考虑使用模板来做这样的事情(消除混乱和重用)。使用模板 类 的开销很小,这个过程在编译时完成。