Scribd
Upload
55 views2 pages

Mid-Square Hashing Implementation

The document presents a C++ implementation of a Mid-Square Hashing class, which includes methods for initializing a hash table, inserting keys, and displaying the table contents. The hash function squares the key and extracts the middle digits to determine the index for insertion. It also handles basic collision detection by indicating when an index is already occupied, but does not implement collision resolution strategies.

Uploaded by

sandeep.chitalkar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
55 views2 pages

Mid-Square Hashing Implementation

The document presents a C++ implementation of a Mid-Square Hashing class, which includes methods for initializing a hash table, inserting keys, and displaying the table contents. The hash function squares the key and extracts the middle digits to determine the index for insertion. It also handles basic collision detection by indicating when an index is already occupied, but does not implement collision resolution strategies.

Uploaded by

sandeep.chitalkar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include <iostream>

#include <cmath>
using namespace std;

class MidSquareHashing {
private:
int* hashTable; // Array to store hash table values
int tableSize; // Size of the hash table

public:
// Constructor to initialize hash table with a given size
MidSquareHashing(int size) {
tableSize = size;
hashTable = new int[tableSize]; // Dynamically allocate memory for the
array
for (int i = 0; i < tableSize; i++) {
hashTable[i] = -1; // Initialize all values to -1 (empty slots)
}
}

// Mid-Square hash function


int hash(int key) {
// Step 1: Square the key
long long squaredKey = (long long)key * key;

// Step 2: Extract the middle digits of the squared result


int numDigits = to_string(squaredKey).length();
int middleDigitsCount = numDigits / 2;

// Extract the middle digits


long long divisor = pow(10, middleDigitsCount);
int middleDigits = (squaredKey / divisor) % tableSize;

return middleDigits; // Return the index within the table size


}

// Insert a key into the hash table


void insert(int key) {
int index = hash(key); // Calculate the index using the mid-square method
if (hashTable[index] == -1) {
hashTable[index] = key; // Insert the key if the index is empty
cout << "Inserted " << key << " at index " << index << endl;
} else {
cout << "Collision occurred at index " << index << ", cannot insert "
<< key << endl;
// This basic implementation doesn't handle collisions
}
}

// Display the hash table


void display() {
cout << "Hash Table:" << endl;
for (int i = 0; i < tableSize; i++) {
if (hashTable[i] != -1) {
cout << "Index " << i << ": " << hashTable[i] << endl;
} else {
cout << "Index " << i << ": Empty" << endl;
}
}
}

// Destructor to free dynamically allocated memory


~MidSquareHashing() {
delete[] hashTable;
}
};

int main() {
int size, numKeys, key;

// Get the size of the hash table from the user


cout << "Enter the size of the hash table: ";
cin >> size;

// Create an object of MidSquareHashing with the specified size


MidSquareHashing msh(size);

// Get the number of keys to insert from the user


cout << "Enter the number of keys to insert: ";
cin >> numKeys;

// Insert keys into the hash table


for (int i = 0; i < numKeys; i++) {
cout << "Enter key " << i + 1 << ": ";
cin >> key;
[Link](key);
}

// Display the hash table contents


[Link]();

return 0;
}

You might also like