c++ - HashTable 实现 Get 和 Set 运算符重载

Question

我正在尝试实现一个基本 哈希表。我正在使用链表来解决冲突。

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