Modulo erzeugt Bad Int für Adressen in der Hash-Tabelle?

Question

HILFE! Ich versuche, eine Hashtabelle mit Separate Chaining zu erstellen. Aus irgendeinem unbekannten Grund kann ich nicht scheinen zu durchlaufen und finden alle ursprünglichen int ich geladen. Ich vermute, dass die Modulo-Funktion mir manchmal in beiden Funktionen falsche Adressen liefert. Zuerst werden bei der Erstellung der Hashtabelle falsche Adressen für verschiedene Ints erzeugt, und dann werden in der zweiten Funktion manchmal die falschen Adressen gesucht, während ich versuche, meine Liste mit modulo erneut zu durchlaufen und zu bestätigen. Die Hash-Tabelle wird durch ein einfaches Zufallsfeld von Zahlen gefüllt und dann vergleiche ich die erstellte Hash-Tabelle mit dem ursprünglichen Zufallsfeld von int. Hier ist, was ich glaube, der Übeltäter verursacht alle meine Probleme, aber ich kann nicht 100% sicher sein:

address = randARRAY[key] % MAX_KEYS;

Und hier ist die Funktion zur Erstellung der Hashtabelle mit Separate Chaining. Ich habe in der Regel MAX_KEYS = 5000, tbSIZE = 8989, was besser als 75% ist Lastfaktor irgendwo um 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;
}

Diese erstellten Daten werden offenbar ohne Probleme weitergeleitet. Ich habe gdb verwendet, um eine lächerlich lange Liste auf einem Array-Index zu erstellen und es war alles da in der zweiten Funktion ohne fehlende Knoten. Deshalb denke ich, dass die Adressen durch Modulo sowohl in der obigen als auch in der folgenden Funktion verfälscht werden könnten. Dadurch werden offenbar falsche Adressen erzeugt und später die falschen aufgerufen. Am Ende bin ich nie in der Lage, alle meine int für das zufällige Array in der Hash Table zu finden. Hier ist die Funktion, die modulo wieder verwendet und dann versucht, zu durchlaufen und passen die zufällige Array gegen die neue Hash-Tabelle:

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;
}

Wie immer danke ich Ihnen im Voraus für jede Unterstützung! Ich werde dankbar sein, wenn Sie sehen können, wo ich bin durcheinander!

Answer 1

Nun, ich bin wohl einfach ein Holzkopf! Ich habe eine boolesche Variable verwendet, um zu prüfen, ob zu irgendeinem Zeitpunkt während des Durchlaufs eine Übereinstimmung gefunden wurde.

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

Ich habe versucht, Knoten abzugleichen, die über ihre Übereinstimmung hinausgegangen sind, und habe schlechte Ergebnisse erhalten. Jedenfalls ist dies, wie ich meine Überprüfung mit boolen statt geändert. Vielen Dank für eure Hilfe, Leute!

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;
}