c++ - 模数为哈希表中的地址创建错误的 int？

Question

帮助!我正在尝试使用单独链接创建哈希表。由于某种未知原因，我似乎无法遍历并找到我加载的所有原始 int。我怀疑模函数有时会在两个函数中给我错误的地址。首先在创建哈希表时在 assorted int 上创建错误地址，然后有时在第二个函数中搜索错误地址，同时尝试再次使用模遍历和确认我的列表。哈希表由一个基本的随机数字数组填充，然后我将创建的哈希表与原始的随机 int 数组进行比较。这是我认为罪魁祸首造成我所有麻烦的原因，但我不能 100% 确定:

address = randARRAY[key] % MAX_KEYS;

这里是使用分离链创建哈希表的函数。我通常有 MAX_KEYS = 5000，tbSIZE = 8989，这比 75% 负载因子大约 55% 更好:

void separateCHAINING(int *randARRAY,int tbSIZE,TABLE *head[]){
  int key = 0,
    address = 0,
    collisions = 0,
    newONE = 0;
  randARRAY[MAX_KEYS + 1] = 0;
  TABLE *newADDRESS[tbSIZE];
  newADDRESS[tbSIZE] = new TABLE();

  for(int a = 0; a < tbSIZE; a++){
    newADDRESS[a] = NULL;
    head[a] = NULL;
  }

  while(randARRAY[key] != 0){
    address = randARRAY[key] % MAX_KEYS;
    newADDRESS[address] = new TABLE;
    newADDRESS[address]->key = randARRAY[key];
    if(head[address] != 0){
      newADDRESS[address]->next = head[address]->next;
      head[address]->next = newADDRESS[address];
      collisions++;
    }
    else{
      newADDRESS[address]->next = head[address];
      head[address] = newADDRESS[address]; 
      newONE++;   
    }
    key++;  
  }
  cout << "total collisions: " << collisions << endl;
  cout << "new: " << newONE << endl;
  cout << "added: " << collisions + newONE << endl;
  cout << "key: " << key << endl;
}

此创建的数据似乎已顺利通过。我使用 gdb 在一个数组索引上创建了一个长得离谱的列表，它都在第二个函数中，没有遗漏任何节点。这就是为什么我认为地址可能在上面的函数和下面的这个函数中被取模搞砸了。这显然是在创建虚假地址，然后稍后再调用错误的地址。最后，我永远无法找到放入哈希表中的随机数组的所有整数。这是再次使用模数然后尝试遍历随机数组并将其与新哈希表匹配的函数:

void tableTWO_MATCH(int *randARRAY,TABLE *HT_TWO[]){
  int key = 0,
    address = 0,
    match = 0,
    nomatch = 0;
  randARRAY[MAX_KEYS + 1] = 0;

  while(randARRAY[key] != 0){
    address = randARRAY[key] % MAX_KEYS;
    while(HT_TWO[address]->next != NULL && HT_TWO[address]->key != randARRAY[key]){         
      HT_TWO[address] = HT_TWO[address]->next;
    }//end second while 
    if(HT_TWO[address]->key == randARRAY[key]){
      match++;

    }//end if
    if(HT_TWO[address]->key != randARRAY[key]){
      nomatch++;            
    }//end if
    key = key + 1;
    address = 0;

  }//end outer while
  cout << "match: " << match << endl;
  cout << "not match: " << nomatch << endl;
  cout << "key: " << key << endl;
}

一如既往地提前感谢您的任何帮助!如果您能看到我搞砸的地方，我将不胜感激!

Answer 1

好吧，我想我只是个白痴!我使用一个 bool 变量来检查并查看是否在遍历期间的任何时间点找到了匹配项。

if(HT_TWO[address]->key == randARRAY[key]){
          found = true;
        }   

我试图匹配遍历过匹配项的节点，但结果很差。无论如何，这就是我使用 boolen 更改验证的方式。感谢您的帮助!

void tableTWO_MATCH(int *randARRAY,TABLE *HT_TWO[]){
  int key = 0,
    address = 0,
    match = 0,
    nomatch = 0;
  bool found = false;
  randARRAY[MAX_KEYS + 1] = 0;

  while(randARRAY[key] != 0){
    address =  HASH(randARRAY[key],MAX_KEYS);
    if(HT_TWO[address]->key == randARRAY[key]){
      match++;
    }
    else{
      while(HT_TWO[address]->next != NULL){         
    HT_TWO[address] = HT_TWO[address]->next;
    if(HT_TWO[address]->key == randARRAY[key]){
      found = true;
    }     
      }//end second while 
      if(found == false){
    nomatch++;
      }

    }
    key = key + 2;      
  }//end outer while
  cout << "not match: " << nomatch << endl;
  cout << "key: " << key << endl;
}