HashTable 实现 Get 和 Set 运算符重载

Question

我正在尝试实现 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;
  }
};

Answer 1

您的问题是您在 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 方法也有类似的问题。

Answer 2

在您的 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 答案的附录。我的代码仅说明了使用您的错误代码的问题，并非直接解决方案。

Answer 3

我同意 bpachev。因为这是 C++，你应该考虑使用模板来做这样的事情（消除混乱和重用）。使用模板类的开销很小，这个过程在编译时完成。

HashTable 实现 Get 和 Set 运算符重载

HashTable Implementation Get and Set Operator Overloading

c++

c++11

hashtable