If the generated random number to look for does not exist in hashtable array, then programm gets stuck in endless loop in function void hashSearch(),
whereas it should just get out of the loop and output that search item is not found. The exact place in code is where these to outputs are:
cout << "stuck in else loop \n"; and cout << "stuck in while loop end \n";.
I've googled around, but can't find similar examples.
#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";
}
Whereas it should just get out of the loop and output that search item is not found.
Search for cout << " stuck in else loop \n"; and cout << " stuck in while loop end \n";.
You want to stop your loop when you hit the end of the array: To that effect, you set the item to search for to zero:
if (searchInt == size2 - 1)
{
searchInt = 0;
cout << "if loop \n";
}
But in the loop control, you don't test that. You only test the array element at the current index for zero (not found) or the item to search (found):
while ((arr2[searchInt] != 0) && (arr2[searchInt] != randSearchItem)) ...
You need an additional test:
while ((searchInt != 0) && ...) ...
It took me a while to see that you want to code an open-address hastable where a zero marks unused slots. The hash value is just the number itself. Using zero as indicator for an empty slot is not ideal: You cannot store numbers whose hash code modulo the table size is zero.
I'd also code this with a non-void function where the return value is the index or some unambiguous value meaning "not found", perhaps -1. (Alternatively, you can return a pointer to the found item or NULL if the item isn't found -- after all, the index in the hash array is part of the hash table's internals and non concern to the caller.)
Then you can use early returns:
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!
}
But what do you do if there is no room for a further element when you have a hash code close to the array size? You will need to add extra space at the end or you'll need to wrap around. Perhaps that is what you wanted to achieve by setting the index back to zero. In your case, ther array is full, so there are no zeros that could serve as loop-breaking criterion. You will have to find another criterion. You could ensure that there are zeros by making the hash table 30% or so bigger than the number of entries. Or you could try to detect whether the index has come full circle to the original index.
As already pointed out to you in comments: Try to use function arguments and local variables rather than puttin everything into global space. Also, the chaining of function calls, where the last thing in a function is to call the next one is strange. It's probably better to put all sequential calls into main.