C ++ Функция хеширования застряла в бесконечном цикле «else» и «while»

Question

Если сгенерированное случайное число для поиска не существует в массиве хеш-таблиц, то программа застревает в бесконечном цикле в функции void hashSearch(), тогда как она должна просто выйти из цикла и вывести, что элемент поиска не найден. Точное место в коде - где эти выходные данные: cout << "stuck in else loop \n"; и cout << "stuck in while loop end \n";.

Я гуглил, но не могу найти похожие примеры.

#include <iostream>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#include <chrono>
using namespace std;
int arr [1000];
int arr2 [1000];
int randArrayInt, n, randSearchItem, searchInt, address, size2;
void printZeroArr();
void linearSentinelSearch();
void printHashArray();
void hashSearch();
int main ()
{
    srand (time(nullptr));  //initialize random seed:
    n = rand() % 900 + 100; //random integer number from 100 - 1000, length of the array
    //n = rand() % 10; // random number in the range 1-10 for sanity tests, length of the array
    //randSearchItem = rand() % 10 + 1;
    randSearchItem = rand() % 900 + 100; //this is the number to search for
    cout << "Array length is " << n << endl;
    cout << "[";
    for (int i = 0; i <= n; i++)
    {
        randArrayInt = rand() % 900 + 100;
        //randArrayInt = rand() % 10 + 1; // generate random 1-10 number for for sanity tests
        arr[i] = randArrayInt;   // insert into array position the generated random number
        cout<< " " << arr[i];  // print out array element at current loop position
    }
    cout << " ]\n" << endl;
    printZeroArr();
}

void printZeroArr()
{
    size2 = n + 1; //length of hashed array
    cout << "This is the random key to search for in array: " << randSearchItem << endl;
    cout << "This is the size2 length " << size2 << endl;
    cout << "This is the hasharray with zeros" << endl;
    cout << "[";
    for (int i = 0; i <= size2; i++)
    {
        arr2[i] = 0;   // insert into hasharray number 0
        cout<< " " << arr2[i];  // print out hasharray element at current loop position
    }
    cout << " ]\n" << endl;
    linearSentinelSearch();
}

void linearSentinelSearch()
{
    auto start = std::chrono::high_resolution_clock::now();
    arr[n + 1] = randSearchItem;
    //cout << "testing arr[n + 1] is " << arr[n + 1] << endl;
    int i = 0;
    while (arr[i] != randSearchItem) i++;
    if (i == n + 1)
        cout << "Sentinel search did not found the searchitem in random array" << "\n" << endl;
    else
        cout << "Searchitem found in array with linearsearch at position " << i << "\n" << endl;
    auto finish = std::chrono::high_resolution_clock::now();
    chrono::duration<double> elapsed = finish - start;
    cout << "Elapsed time: " << elapsed.count() << " s\n";
    printHashArray();
}

void printHashArray()
{
    //cout << "printing out 'address' value, or the modulo result: " << endl;
    //cout << "[";
    for (int i = 0; i <= n; i++)
    {
        address = arr[i] % size2;
        //cout << " " << address;
        while (arr2[address] != 0)
        {
            if (address == size2 - 1)
            {
                address = 0;
            } else
            {
                address++;
            }
        }
        arr2[address] = arr[i];
    }
    //cout << " ]\n" << endl;
    cout << "This is the hasharray with hashitems" << endl;
    cout << "[";
    for (int i = 0; i <= size2; i++)
    {
        cout << " " << arr2[i];
    }
    cout << " ]\n" << endl; hashSearch();
}

void hashSearch()
{
    auto start = std::chrono::high_resolution_clock::now();
    int searchInt = randSearchItem % size2;
    while ((arr2[searchInt] != 0)  && (arr2[searchInt] != randSearchItem))
    {
        if (searchInt == size2 - 1)
        {
            searchInt = 0;
            cout << "if loop \n";
        }
        else
        {
            searchInt++;
            cout << " stuck in else loop \n";
        }
        cout << " stuck in while loop end \n";
    }
    if (searchInt == 0) {
        cout << "Search item not found using hashSearch" << endl;
    } else {
        cout << "Search item " << randSearchItem << " found using hashSearch at position " << searchInt << " in arr2." << endl;
    }
    auto finish = std::chrono::high_resolution_clock::now();
    chrono::duration<double> elapsed = finish - start;
    cout << "Elapsed time: " << elapsed.count() << " s\n";
}

Принимая во внимание, чтоон должен просто выйти из цикла и вывести, что элемент поиска не найден. Искать cout << " stuck in else loop \n"; и cout << " stuck in while loop end \n";.

Answer 1

Вы хотите остановить цикл, когда вы дойдете до конца массива: для этого вы устанавливаете элемент для поиска равным нулю:

    if (searchInt == size2 - 1)
    {
        searchInt = 0;
        cout << "if loop \n";
    }

Но в элементе управления цикла вы непроверить это. Вы проверяете только элемент массива с текущим индексом на ноль (не найден) или элемент для поиска (найден):

while ((arr2[searchInt] != 0)  && (arr2[searchInt] != randSearchItem)) ...

Вам необходим дополнительный тест:

while ((searchInt != 0)  && ...) ...

ItМне потребовалось некоторое время, чтобы понять, что вы хотите написать код с открытым адресом, где ноль обозначает неиспользуемые слоты. Хэш-значение - это просто само число. Использование нуля в качестве индикатора для пустого слота не является идеальным: вы не можете хранить числа, хеш-код которых по модулю равен размеру таблицы.

Я бы также кодировал это с помощью функции non-void, где возвращаемое значение - этоindex или какое-то однозначное значение, означающее «not found», возможно -1. (В качестве альтернативы, вы можете вернуть указатель на найденный элемент или NULL, если элемент не найден - в конце концов, индекс в массиве хеш-функции является частью внутренних элементов хеш-таблицы и не имеет отношения к вызывающей стороне.)

Тогда вы можете использовать ранние возвраты:

int hashSearch(const int *arr2, int size2, int item)
{
    int i = item % size2;

    for (; i < size2; i++) {
        if (arr2[i] == -1) break;            // -1 indicated unused space
        if (arr2[i] == item) return i;       // return index of item
    }

    return -1;     // not found!
}

Но что вы будете делать, если нет места для дополнительного элемента, когда у вас есть хэш-код, близкий к размеру массива? Вам нужно будет добавить дополнительное пространство в конце или вам нужно будет обернуться вокруг. Возможно, именно этого вы хотели добиться, установив индекс на ноль. В вашем случае массив заполнен, поэтому нет нулей, которые могли бы служить критерием разрыва цикла. Вам нужно будет найти другой критерий. Вы можете убедиться, что есть нули, сделав хеш-таблицу примерно на 30% больше, чем количество записей. Или вы можете попытаться определить, прошел ли индекс полный круг по отношению к исходному индексу.

Как уже отмечалось в комментариях: попробуйте использовать аргументы функций и локальные переменные, а не помещать все в глобальное пространство. Кроме того, цепочка вызовов функций, когда последним в функции является вызов следующего, странная. Вероятно, лучше поместить все последовательные вызовы в main.