Muhammad Usman
23F-0570
CS-4A
Task1:
#include <iostream>
using namespace std;
class HashTable {
private:
int* table;
int size;
int count;
int strategy; // 1 = Linear, 2 = Quadratic, 3 = Double Hash
public:
HashTable(int initialSize, int collisionStrategy) {
size = initialSize;
count = 0;
strategy = collisionStrategy;
table = new int[size];
for (int i = 0; i < size; i++)
table[i] = -1;
~HashTable() {
delete[] table;
}
int hash(int key) { return key % size; }
int secondHash(int key) { return 7 - (key % 7); }
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
int nextPrime(int n) {
while (!isPrime(n)) n++;
return n;
bool loadFactorExceeded() {
return (count * 100 / size) > 70;
void rehash() {
int oldSize = size;
int* oldTable = table;
size = nextPrime(2 * size);
table = new int[size];
for (int i = 0; i < size; i++) table[i] = -1;
count = 0;
for (int i = 0; i < oldSize; i++) {
if (oldTable[i] != -1)
insert(oldTable[i]);
delete[] oldTable;
void insert(int key) {
if (loadFactorExceeded())
rehash();
int index = hash(key);
int i = 0;
int newIndex;
while (true) {
if (strategy == 1)
newIndex = (index + i) % size;
else if (strategy == 2)
newIndex = (index + i * i) % size;
else
newIndex = (index + i * secondHash(key)) % size;
if (table[newIndex] == -1) {
table[newIndex] = key;
count++;
break;
i++;
}
}
void display() {
for (int i = 0; i < size; i++) {
cout << i << ":";
if (table[i] != -1)
cout << table[i];
else
cout << "-";
cout << "\t";
if ((i + 1) % 5 == 0 || i == size - 1)
cout << endl;
};
class Tester {
public:
void run() {
int keys[] = { 17, 26, 15, 9, 11, 43, 75, 19, 35, 45, 55, 9, 10, 21, 61, 23 };
int n = sizeof(keys) / sizeof(keys[0]);
cout << "Linear Probing:\n";
HashTable linear(15, 1);
for (int i = 0; i < n; i++) [Link](keys[i]);
[Link]();
cout << "\nQuadratic Probing:\n";
HashTable quadratic(15, 2);
for (int i = 0; i < n; i++) [Link](keys[i]);
[Link]();
cout << "\nDouble Hashing:\n";
HashTable doubleHash(15, 3);
for (int i = 0; i < n; i++) [Link](keys[i]);
[Link]();
};
int main() {
Tester t;
[Link]();
system("pause");
return 0;
}
Task2:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int d) {
data = d;
next = nullptr;
};
class ChainingHash {
private:
Node** table;
int size;
int count;
public:
ChainingHash(int s) {
size = s;
count = 0;
table = new Node * [size];
for (int i = 0; i < size; i++)
table[i] = nullptr;
~ChainingHash() {
for (int i = 0; i < size; i++) {
Node* curr = table[i];
while (curr) {
Node* temp = curr;
curr = curr->next;
delete temp;
delete[] table;
int hash(int key) {
return key % size;
void insert(int key) {
int idx = hash(key);
Node* newNode = new Node(key);
newNode->next = table[idx];
table[idx] = newNode;
count++;
void display() {
for (int i = 0; i < size; i++) {
cout << i << ": ";
Node* curr = table[i];
while (curr) {
cout << curr->data << " -> ";
curr = curr->next;
cout << "NULL" << endl;
}
};
class BucketHash {
private:
int** table;
int size;
int bucketSize;
int count;
public:
BucketHash(int s, int bSize = 3) {
size = s;
bucketSize = bSize;
count = 0;
table = new int* [size];
for (int i = 0; i < size; i++) {
table[i] = new int[bucketSize];
for (int j = 0; j < bucketSize; j++)
table[i][j] = -1;
~BucketHash() {
for (int i = 0; i < size; i++)
delete[] table[i];
delete[] table;
int hash(int key) {
return key % size;
void insert(int key) {
int idx = hash(key);
for (int i = 0; i < bucketSize; i++) {
if (table[idx][i] == -1) {
table[idx][i] = key;
count++;
return;
cout << "Bucket full at index " << idx << ", cannot insert key " << key << endl;
void display() {
for (int i = 0; i < size; i++) {
cout << i << ": ";
for (int j = 0; j < bucketSize; j++) {
if (table[i][j] != -1)
cout << table[i][j] << " ";
else
cout << "- ";
cout << endl;
};
class Tester {
public:
void run() {
int keys[] = { 17, 26, 15, 9, 11, 43, 75, 19, 35, 45, 55, 9, 10, 21, 61, 23 };
int n = sizeof(keys) / sizeof(keys[0]);
cout << "Chaining:\n";
ChainingHash chain(10);
for (int i = 0; i < n; i++) [Link](keys[i]);
[Link]();
cout << "\nBucketing (3 buckets per slot):\n";
BucketHash bucket(10, 3);
for (int i = 0; i < n; i++) [Link](keys[i]);
[Link]();
};
int main() {
Tester t;
[Link]();
system("pause");
return 0;
}
Task3:
#include <iostream>
using namespace std;
class Node {
public:
int key;
string value;
Node* prev;
Node* next;
Node(int k, string v) {
key = k;
value = v;
prev = next = nullptr;
};
class HashTable {
private:
Node** table;
int size;
int hash(int key) {
return key % size;
public:
HashTable(int s) {
size = s;
table = new Node * [size];
for (int i = 0; i < size; i++)
table[i] = nullptr;
~HashTable() {
for (int i = 0; i < size; i++) {
Node* curr = table[i];
while (curr) {
Node* temp = curr;
curr = curr->next;
delete temp;
delete[] table;
void insert(int key, string value) {
int idx = hash(key);
Node* head = table[idx];
Node* curr = head;
while (curr) {
if (curr->key == key) {
cout << "Key " << key << " already exists. Use update.\n";
return;
curr = curr->next;
Node* newNode = new Node(key, value);
newNode->next = head;
if (head != nullptr)
head->prev = newNode;
table[idx] = newNode;
}
string get(int key) {
int idx = hash(key);
Node* curr = table[idx];
while (curr) {
if (curr->key == key)
return curr->value;
curr = curr->next;
return "Key not found.";
void update(int key, string newValue) {
int idx = hash(key);
Node* curr = table[idx];
while (curr) {
if (curr->key == key) {
curr->value = newValue;
cout << "Key " << key << " updated.\n";
return;
curr = curr->next;
cout << "Key not found.\n";
void remove(int key) {
int idx = hash(key);
Node* curr = table[idx];
while (curr) {
if (curr->key == key) {
if (curr->prev)
curr->prev->next = curr->next;
else
table[idx] = curr->next;
if (curr->next)
curr->next->prev = curr->prev;
delete curr;
cout << "Key " << key << " removed.\n";
return;
curr = curr->next;
cout << "Key not found.\n";
void display() {
cout << "\nHash Table:\n";
for (int i = 0; i < size; i++) {
cout << i << ": ";
Node* curr = table[i];
while (curr) {
cout << "[" << curr->key << ":" << curr->value << "] <-> ";
curr = curr->next;
cout << "NULL\n";
}
};
int main() {
HashTable ht(10);
[Link](15, "Apple");
[Link](25, "Banana");
[Link](35, "Cherry");
[Link](45, "Date");
[Link]();
cout << "\nRetrieve key 25: " << [Link](25) << endl;
[Link](25, "Blueberry");
cout << "Retrieve updated key 25: " << [Link](25) << endl;
[Link](35);
[Link]();
[Link](15, "Grapes");
system("pause");
return 0;
}
Task4:
#include <iostream>
using namespace std;
class MyHashMap {
private:
struct Node {
int key, value;
Node* next;
Node(int k, int v) : key(k), value(v), next(nullptr) {}
};
Node** table;
int capacity;
int count;
float loadFactorThreshold;
int customHash(int key) {
key = ((key >> 3) ^ (key * 31));
return (key % capacity + capacity) % capacity;
void resize() {
int oldCapacity = capacity;
capacity *= 2;
Node** oldTable = table;
table = new Node * [capacity];
for (int i = 0; i < capacity; i++) table[i] = nullptr;
count = 0;
for (int i = 0; i < oldCapacity; i++) {
Node* curr = oldTable[i];
while (curr) {
put(curr->key, curr->value);
Node* toDelete = curr;
curr = curr->next;
delete toDelete;
}
delete[] oldTable;
public:
MyHashMap() {
capacity = 10;
count = 0;
loadFactorThreshold = 0.75;
table = new Node * [capacity];
for (int i = 0; i < capacity; i++)
table[i] = nullptr;
~MyHashMap() {
for (int i = 0; i < capacity; i++) {
Node* curr = table[i];
while (curr) {
Node* temp = curr;
curr = curr->next;
delete temp;
delete[] table;
void put(int key, int value) {
if ((float)(count + 1) / capacity > loadFactorThreshold)
resize();
int index = customHash(key);
Node* curr = table[index];
while (curr) {
if (curr->key == key) {
curr->value = value;
return;
curr = curr->next;
Node* newNode = new Node(key, value);
newNode->next = table[index];
table[index] = newNode;
count++;
int get(int key) {
int index = customHash(key);
Node* curr = table[index];
while (curr) {
if (curr->key == key)
return curr->value;
curr = curr->next;
return -1;
void remove(int key) {
int index = customHash(key);
Node* curr = table[index];
Node* prev = nullptr;
while (curr) {
if (curr->key == key) {
if (prev)
prev->next = curr->next;
else
table[index] = curr->next;
delete curr;
count--;
return;
prev = curr;
curr = curr->next;
void display() {
cout << "\nHashMap State:\n";
for (int i = 0; i < capacity; i++) {
cout << i << ": ";
Node* curr = table[i];
while (curr) {
cout << "[" << curr->key << ":" << curr->value << "] -> ";
curr = curr->next;
cout << "NULL\n";
};
int main() {
MyHashMap map;
[Link](10, 100);
[Link](20, 200);
[Link](30, 300);
[Link](25, 250);
[Link](35, 350);
cout << "Value at key 20: " << [Link](20) << endl;
[Link](20);
cout << "After removal, key 20: " << [Link](20) << endl;
[Link](40, 400);
[Link](50, 500);
[Link](60, 600);
[Link](70, 700);
[Link](80, 800);
[Link]();
system("pause");
return 0;
}
Task5:
#include <iostream>
using namespace std;
class PhoneCombinations {
private:
string mapping[10];
void backtrack(string digits, int index, string current, string* result, int& resultCount) {
if (index == [Link]()) {
result[resultCount++] = current;
return;
char digit = digits[index];
string letters = mapping[digit - '0'];
for (int i = 0; i < [Link](); i++) {
backtrack(digits, index + 1, current + letters[i], result, resultCount);
public:
PhoneCombinations() {
mapping[2] = "abc";
mapping[3] = "def";
mapping[4] = "ghi";
mapping[5] = "jkl";
mapping[6] = "mno";
mapping[7] = "pqrs";
mapping[8] = "tuv";
mapping[9] = "wxyz";
void getCombinations(string digits) {
if ([Link]()) {
cout << "No digits provided.\n";
return;
}
string result[1000];
int resultCount = 0;
backtrack(digits, 0, "", result, resultCount);
cout << "\nPossible combinations:\n";
for (int i = 0; i < resultCount; i++) {
cout << result[i] << " ";
cout << endl;
};
int main() {
PhoneCombinations pc;
string input;
cout << "Enter digits (2-9): ";
cin >> input;
[Link](input);
system("pause");
return 0;