I have a program that consists of two files, I have both a quadratic and linear probing function to resolve collisions while hashing and my Linear works fine but im not sure why the quadratic doesnt. I have the results that should be printed
Linear:
Hash table size: 8087
Number of collisions with a = 33: 6240629
Hash table size: 8087
Number of collisions with a = 37: 4817906
Hash table size: 8087
Number of collisions with a = 39: 6686453
Hash table size: 8087
Number of collisions with a = 41: 7423747Quadratic:
Hash table size: 8087
Number of collisions with a = 33: 1145326
Hash table size: 8087
Number of collisions with a = 37: 1182048
Hash table size: 8087
Number of collisions with a = 39: 1127766
Hash table size: 8087
Number of collisions with a = 41: 1152208
Instead, I get the following result for my output.
Hash table size : 8087
Number of collisions with a = 33: 1134428
Hash table size : 8087
Number of collisions with a = 37: 1166882
Hash table size : 8087
Number of collisions with a = 39: 1184105
Hash table size : 8087
Number of collisions with a = 41: 1159074
What Im talking about is the number of collisions. I need the values to match and they should because they are inputing the same code and both should be using quadratic probing. Below are my two files I would GREATLY appreciate any help. been stuck on this all day.
#include <iostream>
#include <fstream>
#include <string>
#include <cctype>
#include <sstream>
#include "HashType - Copy.h"
using namespace std;
void buildHashTable(ifstream& inFile, HashType<string>& hashTable, int type, int Prime) {
string word;
int length;
if (inFile.is_open()) {
while (inFile >> word) {
length = word.size();
for (int i = 0; i < length; ) {
unsigned char ch = word[i]; // Cast to unsigned char to handle characters safely
if (ch < ' ' || ispunct(ch)) { // Check for control characters and punctuation
word.erase(i, 1);
length = word.length(); // Update length after modifying the string
}
else {
++i; // Only increment if no deletion was made
}
}
if (type == 1) {
hashTable.InsertItemLinear(word, Prime);
}
if(type == 0){
hashTable.InsertItemQuadratic(word, Prime);
}
}
}
cout << "n" << "Hash table size : " << hashTable.GetSize() << endl;
cout << "Number of collisions with a = " << Prime << ": " << hashTable.GetCollisions() << endl;
hashTable.MakeEmpty();
hashTable.resetCollisions();
}
int main() {
for (int b : {33, 37, 39, 41}) {
ifstream inFile("hashText1.txt");
if (!inFile) {
cerr << "Error opening file." << endl;
return 1;
}
int primeSize;
string line;
if (getline(inFile, line)) {
stringstream ss(line);
ss >> primeSize;
}
HashType<string> hashTable(primeSize);
buildHashTable(inFile, hashTable, 0, b);
}
return 0;
}
#ifndef HASHTYPE_H
#define HASHTYPE_H
// File ItemType.h must be provided by the user of this class.
// ItemType.h must contain the following definitions:
// MAX_ITEMS: the maximum number of items on the list
// ItemType: generic data type
#include <string>
#include <cmath>
#include <iostream>
#include <bitset>
#include <vector>
const int MAX_ITEMS = 5;
using namespace std;
template<class ItemType>
class HashType
{
public:
HashType();
// Constructor
HashType(int s);
//Dynamic size constructor
void SetHashType(bool flag);
void MakeEmpty();
// Function: Returns the list to the empty state.
// Post: List is empty.
bool IsFull() const;
// Function: Determines whether list is full.
// Pre: List has been initialized.
// Post: Function value = (list is full)
int GetNumItems() const;
// Function: Determines the number of elements in list.
// Pre: List has been initialized.
// Post: Function value = number of elements in list
void RetrieveItem(ItemType item, bool& found);
// Function: Retrieves list element whose key matches item's key (if
// present).
// Pre: List has been initialized.
// Key member of item is initialized.
// Post: If there is an element someItem whose value matches
// item's value, then found = true and item contains the contents of
// the item if it is found.
// otherwise found = false and item is returned unchanged.
// List is unchanged.
void Insert(ItemType item);
// Function: Adds item to list and uses a linear probing technique to
// resolve collisions. If the flag is true, a random hash method will be used.
//If the flag is false, the division method will be used.
// Pre: List has been initialized.
// List is not full.
// item is not in list.
// Post: item is in list.
void DeleteItem(ItemType item);
// Function: Deletes the element whose key matches item's key.
// Pre: List has been initialized.
// Key member of item is initialized.
// One and only one element in list has a key matching item's key.
// Post: No element in list has a key matching item's key.
int Hash(ItemType item, int a) const;
//This is the hash function for this class. If the flag is true, a random hash method will be used.
//If the flag is false, the division method will be used.
unsigned long int GetCollisions() const;
//return the number of collisions that occured during the build of the hash table
template<class Item>
friend ostream& operator<<(ostream& out, const HashType<Item>& items);
void InsertItemLinear(ItemType Item, int Prime);
void InsertItemQuadratic(ItemType Item, int Prime);
int GetSize();
void resetCollisions();
private:
bool hashType; //false is division method, true is a random folding method. default is false.
unsigned long int numCollisions;
int numItems;
int size;
ItemType* info;
ItemType emptyItem = "";
};
template<class ItemType>
void HashType<ItemType>::resetCollisions() {
numCollisions = 0;
}
template<class ItemType>
int HashType<ItemType>::GetSize() {
return size;
}
template<class ItemType>
void HashType<ItemType>::SetHashType(bool flag){
hashType = flag;
}
template<class ItemType>
HashType<ItemType>::HashType()
{
hashType = false;
numCollisions = 0;
numItems = 0;
size = MAX_ITEMS;
info = new int[size];
for(int i = 0; i < size; i++)
info[i] = emptyItem;
}
template<class ItemType>
HashType<ItemType>::HashType(int s){
hashType = false;
numItems = 0;
numCollisions = 0;
size = s;
info = new ItemType[size];
for(int i = 0; i < size; i++){
info[i] = emptyItem;
}
}
template<class ItemType>
bool HashType<ItemType>::IsFull() const
{
return (numItems == size);
}
template<class ItemType>
int HashType<ItemType>::GetNumItems() const
{
return numItems;
}
template<class ItemType>
void HashType<ItemType>::MakeEmpty()
// Post: list is empty.
{
numItems = 0;
for(int i = 0; i < size; i++)
info[i] = emptyItem;
}
//Updated IT via Dale 1/31/2019
template<class ItemType>
void HashType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;
int startLoc;
startLoc = Hash(item);
location = startLoc;
do
{
if (info[location] == item || info[location] == emptyItem){
info[location] = -1;
numItems--;
return;
}
else
location = (location + 1) % size;
} while (location != startLoc);
if(location == startLoc){
cout << "Item to delete not found." << endl;
}
}
template<class ItemType>
int HashType<ItemType>::Hash(ItemType item, int a) const
// Post: Returns an integer between 0 and MAX_ITEMS -1.
{
//Complete code here
int hash = 0;
int n = item.length();
for (int i = 0; i < n; i ++)
hash = a * hash + item.at(i);
return abs(hash % size);
return 0;
}
template<class ItemType>
unsigned long int HashType<ItemType>::GetCollisions() const{
return numCollisions;
}
template<class ItemType>
void HashType<ItemType>::Insert(ItemType item)
// Post: item is stored in the array at position item.Hash()
// or the next free spot.
{
if(numItems/size > 0.70){
//rehash//resize
}
int location;
location = Hash(item);
info[location] = item;
numItems++;
}
template<class ItemType>
void HashType<ItemType>::RetrieveItem(ItemType item, bool& found)
{
int location;
int startLoc;
bool moreToSearch = true;
startLoc = Hash(item);
location = startLoc;
do
{
if (info[location] == item || info[location] == emptyItem)
moreToSearch = false;
else
location = (location + 1) % size;
} while (location != startLoc && moreToSearch);
found = (info[location] == item);
if (found)
item = info[location];
}
template<class Item>
ostream& operator<<(ostream& out, const HashType<Item>& items){
out << "[ ";
for(int i = 0; i < items.numItems; i++){
if(i == 0)
out << items.info[i];
else
out << ", " << items.info[i];
}
out << " ]" << endl;
return out;
}
template<class ItemType>
void HashType<ItemType>::InsertItemLinear(ItemType Item, int Prime){
int index = Hash(Item, Prime);
while (info[index] != emptyItem) {
numCollisions++;
index = (index + 1) % size;
}
info[index] = Item;
}
template<class ItemType>
void HashType<ItemType>::InsertItemQuadratic(ItemType Item, int Prime){
int index = Hash(Item, Prime);
int i = 0;
while (info[index] != emptyItem) {
numCollisions++;
i++;
index = (index + i * i) % size;
}
info[index] = Item;
}
#endif
since I use the same hash function for linear and that works I dont think thats the problem. I had a similar issue with linear probing where the values were slightly off and solved it by changing my method for sorting through the file to input words. Im assuming that something similar will be the solution THANKS
Jhgg Fvubh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.