По модулю создает плохой int для адресов в хэш-таблице? - PullRequest
Новая
       22

По модулю создает плохой int для адресов в хэш-таблице?

2 голосов
/ 28 февраля 2011

HELP! Я пытаюсь создать хэш-таблицу с использованием раздельного связывания. По какой-то неизвестной причине я не могу пройтись и найти все оригиналы, которые я загрузил. Я подозреваю, что функция по модулю дает мне плохие адреса иногда в обеих функциях. Сначала при создании хеш-таблицы создаются неправильные адреса в различном int, а затем иногда производится поиск неправильных адресов во второй функции, когда я пытаюсь просмотреть и подтвердить мой список, снова используя modulo. Хеш-таблица заполняется базовым случайным массивом чисел, а затем я сравниваю созданную хеш-таблицу с исходным случайным массивом 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, чтобы создать смехотворно длинный список для одного индекса массива, и все это было во второй функции, не пропуская ни одного узла. Вот почему я думаю, что адреса могут быть испорчены по модулю как в функции выше, так и в этой ниже. Это, очевидно, создает поддельные адреса, а затем вызывает неправильные. В конце концов, я так и не смог найти все свои int для случайного массива, помещенного в хэш-таблицу. Вот функция, которая снова использует модуль по модулю, а затем пытается пройти и сопоставить случайный массив с новой хэш-таблицей: 

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

Как всегда, спасибо заранее за любую помощь! Буду благодарен, если вы увидите, где я все испортил!

1 Ответ

1 голос
/ 01 марта 2011

Ну, я думаю, я просто костяная голова! Я использовал логическую переменную, чтобы проверить и было ли найдено совпадение в любой момент времени во время обхода. 

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