哈希表 - 链表数组 - C++

Question

我正在尝试通过使用链表数组（即创建链接列表）来创建哈希表。但是，我在向哈希表中插入值时遇到了困难。当我运行它时，我得到了这个：http://gyazo.com/3a28a70e66b3ea34e08223e5948f49c0.png 这是我的代码：

#include <iostream>
using namespace std;

class Node {
public:
  int num;
  Node * next;
};

class intHashTable {
private:
  int size;
  Node ** table;
public:
  intHashTable(int size);  // construct a new hash table with size elements
  ~intHashTable();     // delete the memory for all internal components
  void insert(int num);    // insert num into the hash table, no effect
               // if num is already in table
  void remove(int num);    // remove num from the hash table, no effect if not in table
  int lookup(int num);     // return 1 if num is already in table, 0 otherwise
  void print(void);        // print the elements of the hash table to the screen
};

// construct a new hash table with nelements elements
intHashTable::intHashTable(int nelements)
{
  size = nelements;
  table = new Node*[size];
  for ( int i = 0; i < size; i++ ) {
    table[i] = NULL;
  }
}

intHashTable::~intHashTable()
{
   for(int i=0; i<size; i++)
   {
      Node* temp = table[i];
      while(temp != NULL)
      {
         Node* next = temp->next;
         delete temp;
         temp = next;
      }
   }
   size = 0;
   delete[] table;
}

void intHashTable::insert(int num){
    int location = ((unsigned)num) % size;
    Node *runner = table[location];
    if(runner == NULL ){
    runner->num = num;
     }else{
        while(runner != NULL ){
            runner = runner->next;
        }
        runner->num = num;
    }
   }

int main(){
    intHashTable a (10);
    a.insert(2);
    return 0;
}

- user1965283

---

没有错误或警告。 - user1965283

在插入操作中，runner = table[location] 基本上是 NULL，不是吗？ - Reunanen

当您在调试器中运行时，没有错误、警告或方便的堆栈跟踪吗？ - Caribou

一条友好的 :) 建议 - 使用调试器将使你比不使用调试器的其他学生更有优势 - 这是我在面试中总是会问到的一些事情。 - Caribou

此外，你的姓名在屏幕截图中，如果这让你感到困扰，ayokunle。 - Peter Wood

Answer 1

在构建 intHashTable 后，table 的所有元素仍然是 NULL。但是，在 insert 函数中，一个元素被取消引用：

Node *runner = table[location];
runner = runner->next;

这会导致程序崩溃，因为对空指针进行解引用是不合法的。

- Reunanen

---

如果(runner == NULL){ runner->num = num; } - Caribou

@Caribou 最好的测试用例。 - UmNyobe

@user1965283：不是很确定 - 现在它会在Caribou指出的那一行崩溃。 - Reunanen

在 runner = new Node() 之后，runner 将永远不会是 NULL。 - Reunanen

@user1965283 Pukku值得感谢 - 他在我之前就发现了这个问题。 - Caribou

Answer 2

这里的逻辑是错误的。

int location = ((unsigned)num) % size;
Node *runner = table[location];

if(runner == NULL ) // if null u dereference it!
{
 runner->num = num;
}
else
{
  while(runner != NULL ) {  // u loop until null
    runner = runner->next;
  }
  runner->num = num;  // once u reach null u dereference it!
}

我建议改为：

首先为您的节点添加一个 ctor。

class Node {
public:
  int num;
  Node * next;

  Node( int _n ) : num(_n), next(NULL) { } 
};

然后

if ( runner != NULL )
{
   while ( runner->next != NULL )
   {
      runner = runner->next;
   }
   runner->next = new Node( num );
}
else
{
  table[location] = new Node( num ); 
}

- AndersK

Answer 3

Node *runner = table[location];
runner = runner->next;
if(runner == NULL )

你从未验证table[location]是否为空。但在构建哈希表时，节点表中没有任何节点（你将每个条目都设置为null）。

你的代码问题在于你从未考虑分配节点。你应该这样做：

Node* toInsert = new Node;
toInsert->next= NULL;
toInsert->num = num;

if(table[location]==NULL){
   table[location] = toInsert;  
}
else{
    Node *runner = table[location];
    while(runner->next != NULL){
         runner = runner->next;
    }
    runner->next = toInsert;
}

- UmNyobe

Answer 4

这段代码肯定不会工作：

if(runner == NULL ){
runner->num = num;

如果runner为NULL，则不应使用*或->对其进行引用。

- Mats Petersson