指向指针数组的C++指针(HashTable与LinkedList冲突处理)

Question

目标是使用数组来实现HashTable，该数组通过用指针实现的LinkedList来处理冲突。当我去插入时，我有点困惑，不知道为什么我会出错。我有以下几点：

课程：

struct Node {

  string key;
  int value;
  Node* next;

};

class HashTable{


  public:
    HashTable(int);
    //~Hash();
    void insert(string, int);
    void remove(string);

  private:
      Node** _table;
      int _table_size;
      int _hash(string);

};

方法：

HashTable::HashTable(int size): _table_size(size) {
  _table = new Node*[size];
}

int HashTable::_hash(string key) {
  int hashValue = 0;
  for (int i=0;i<key.length();i++) {
    hashValue = 37*hashValue+key[i];
  }

  hashValue %= _table_size;
  return hashValue;
}

void HashTable::insert(string key, int value){
  int hashValue = _hash(key);

  cout << _table[hashValue]->key << endl;
}

Main：

int main(int argc, char* argv[]) {

  HashTable* h = new HashTable(11);
  h->insert("test",4);
}

根据我的理解，键中的当前值应该是空的，不是吗？

Answer 1

_table = new Node*[size]创建一个size未初始化指针数组，因此_table[hashValue]->key是未定义的行为。

若要将整个数组初始化为NULL，请执行_table = new Node*[size]()。或者使用std::vector。

Answer 2

实际上还没有分配任何Node对象。

Node** node = new Node*[size];分配一组Node*，但不分配活动节点对象。