Hashing
⭐Hash Functions
A hash function maps input data (key) to a fixed-size numerical value (hash value).
It is used to quickly access data in a hash table.
⭐Hash Table
A hash table is a data structure that stores key-value pairs.
It uses a hash function to calculate the index in an array where the value will be stored.
This allows for fast retrieval.
⭐Closed Hashing
1) Linear Probing:
In linear probing, if a collision occurs, the hash table checks the next index in a linear fashion (e.g., if index i is occupied, check i+1, i+2, etc.) until an empty slot is found.
CODE:
#include <iostream>using namespace std;// Hash function to compute the index based on the key and table sizeint divied(int key, int tablesize){return key % tablesize;}// Function to read the keys from user inputvoid readkeys(int keys[], int numkeys){for(int i=0; i<numkeys; i++){cin >> keys[i];}}// Function to initialize the hash table, setting all slots to -1 (empty)void initilizehashtable(int hastable[], int tablesize){for(int i=0; i<tablesize; i++){hastable[i] = -1;}}// Function to insert keys into the hash table using linear probingvoid insertkeys(int hastable[], int tablesize, int keys[], int numkeys){for(int i=0; i<numkeys; i++){int key = keys[i];int hashindex = divied(keys[i], tablesize);while(hashindex < tablesize){if(hastable[hashindex] == -1){hastable[hashindex] = key;break;}else if(hastable[hashindex] == key){cout << "Key already exists" << endl;break;}else{hashindex = (hashindex + 1) % tablesize;}}}}// Function to print the contents of the hash tablevoid printhashtable(int hashtable[], int tablesize){for(int i=0; i<tablesize; i++){if(hashtable[i] != -1){cout << "Table number " << i << ": Customer ID " << hashtable[i] << endl;}}}int main(){const int tablesize = 10;int numkeys;cin >> numkeys;int keys[numkeys];readkeys(keys, numkeys);int hashtable[tablesize];initilizehashtable(hashtable, tablesize);insertkeys(hashtable, tablesize, keys, numkeys);printhashtable(hashtable, tablesize);return 0;}
INPUT:
5
102 201 210 310 410
OUTPUT:
Table number 0: Customer ID 210
Table number 1: Customer ID 201
Table number 1: Customer ID 102
Table number 1: Customer ID 310
Table number 1: Customer ID 410
2) Quadratic Probing
In quadratic probing, when a collision occurs, the next index to check is determined by a quadratic function (e.g., i+1^2, i+2^2, i+3^2, etc.), reducing clustering and collisions.
CODE:
#include <iostream>using namespace std;// Function to read the keys from inputvoid readkeys(int keys[], int numkeys){for(int i=0; i<numkeys; i++){cin >> keys[i];}}// Function to initialize the hash table with -1 (empty slots)void initilizehashtable(int hashtable[], int tablesize){for(int i=0; i<tablesize; i++){hashtable[i] = -1;}}// Function to insert a key into the hash table using quadratic probingvoid insertkeys(int hashtable[], int tablesize, int key){int hashindex = key % tablesize;int i = 0;while(hashtable[hashindex] != -1){i++;hashindex = (hashindex + i*i) % tablesize;}hashtable[hashindex] = key;}// Function to print the non-empty slots of the hash tablevoid printhashtable(int hashtable[], int tablesize){for(int i=0; i<tablesize; i++){if(hashtable[i] != -1){cout << hashtable[i] << " ";}}}int main(){const int tablesize = 10;int numkeys;cin >> numkeys;// Array to store the keysint keys[numkeys];readkeys(keys, numkeys);// Array representing the hash tableint hashtable[tablesize];initilizehashtable(hashtable, tablesize);// Insert each key into the hash tablefor(int i=0; i<numkeys; i++){insertkeys(hashtable, tablesize, keys[i]);}// Print the resulting hash tableprinthashtable(hashtable, tablesize);return 0;}
INPUT:
5
41 52 63 95 83
OUTPUT:
41 52 63 83 95
⭐Double Hashing
Double hashing is a technique to resolve collisions where a second hash function is used to calculate the step size for probing.
This provides better distribution and reduces clustering compared to linear and quadratic probing.
The new index is calculated using two hash functions, h1(key) and h2(key).
CODE:
#include <iostream>#include <vector>#include <stdexcept>using namespace std;class doublehashing {private:vector<int> table; // The hash table itselfint tablesize; // The size of the hash tableint count; // The current number of elements in the hash table// Primary hash functionint h1(int key) const {return key % tablesize;}// Secondary hash functionint h2(int key) const {return 1 + (key % (tablesize - 1));}public:// Constructor to initialize the hash tabledoublehashing(int size) : tablesize(size), count(0) {table.resize(tablesize, -1); // Initialize all positions with -1 (empty)}// Insert key into the hash tablevoid insert(int key) {if (count >= tablesize) {throw overflow_error("Hash table is full");}int index = h1(key);int stepsize = h2(key);while (table[index] != -1) { // Handle collisions using double hashingindex = (index + stepsize) % tablesize;}table[index] = key; // Place the keycount++;}// Search for a key in the hash tablebool search(int key) const {int index = h1(key);int stepsize = h2(key);int startindex = index;while (table[index] != -1) {if (table[index] == key) {return true; // Found the key}index = (index + stepsize) % tablesize;if (index == startindex) { // We circled back to the startbreak;}}return false; // Key not found}// Remove a key from the hash tablevoid remove(int key) {int index = h1(key);int stepsize = h2(key);int startindex = index;while (table[index] != -1) {if (table[index] == key) {table[index] = -1; // Remove the keycount--;return;}index = (index + stepsize) % tablesize;if (index == startindex) { // We circled back to the startbreak;}}cout << "Key " << key << " not found." << endl; // If the key is not found}// Display the hash table contentsvoid display() const {cout << "Hash Table Contents:" << endl;for (int i = 0; i < tablesize; i++) {if (table[i] != -1) {cout << "Index " << i << ": " << table[i] << endl;} else {cout << "Index " << i << ": empty" << endl;}}}};int main() {// Create a double hashing object with table size 7doublehashing hashTable(7);// Insert some keys into the hash tablehashTable.insert(15);hashTable.insert(10);hashTable.insert(22);hashTable.insert(5);hashTable.insert(20);// Display the hash tablehashTable.display();// Search for keyscout << "Search for 15: " << (hashTable.search(15) ? "Found" : "Not Found") << endl;cout << "Search for 99: " << (hashTable.search(99) ? "Found" : "Not Found") << endl;// Remove a keycout << "Removing 15:" << endl;hashTable.remove(15);// Display the hash table after removalhashTable.display();return 0;}
OUTPUT:
Hash Table Contents:
Index 0: empty
Index 1: 15
Index 2: 20
Index 3: 10
Index 4: empty
Index 5: 5
Index 6: 22
Search for 15: Found
Search for 99: Not Found
Removing 15:
Hash Table Contents:
Index 0: empty
Index 1: empty
Index 2: 20
Index 3: 10
Index 4: empty
Index 5: 5
Index 6: 22
⭐Open hashing:
In open hashing, each index of the hash table stores a linked list (or another collection) of elements.
If multiple keys hash to the same index (collision), they are stored in the same list at that index.
Each index may contain a chain of elements.
CODE:
#include <iostream>#include <list>#include <vector>#include <string>using namespace std;template <typename K, typename V>class hashtable{private:struct Node{K key;V value;Node(K key, V value) : key(key), value(value) {}};vector<list<Node>> table;int size;// Correct the hash function to properly use std::hashint hash(const K& key) const {return std::hash<K>{}(key) % table.size(); // Use std::hash properly}public:hashtable(int capacity) : table(capacity), size(0) {}void put(const K& key, const V& value){int index = hash(key);for(auto& node : table[index]){if(node.key == key){node.value = value;return;}}table[index].emplace_back(key, value);size++;}V get(const K& key) const {int index = hash(key);for(const auto& node : table[index]){if(node.key == key){return node.value;}}throw runtime_error("key not found");}bool remove(const K& key){int index = hash(key);for(auto it = table[index].begin(); it != table[index].end(); ++it){if(it->key == key){table[index].erase(it);size--;return true;}}return false;}bool containskey(const K& key) const {int index = hash(key);for(const auto& node : table[index]){if(node.key == key){return true;}}return false;}int getsize() const {return size;}};int main() {hashtable<string, int> hastable(10); // Corrected the syntax herehastable.put("apple", 1);hastable.put("banana", 2);hastable.put("orange", 3);try {cout << "Value for apple: " << hastable.get("apple") << endl; // Corrected variable name here}catch(const exception& e) {cerr << e.what() << endl;}cout << "Contains banana: " << hastable.containskey("banana") << endl;hastable.remove("banana");cout << "Contains banana after removal: " << hastable.containskey("banana") << endl;return 0;}
OUTPUT:
Value for apple: 1
Contains banana: 1
Contains banana after removal: 0
⭐Mid square hashing
CODE:
#include <iostream>#include <vector>using namespace std;// Function to calculate the hash index using the Mid-Square methodint midSquareHash(int key, int tableSize, int r) {int squared = key * key; // Step 1: Square the keyint middleDigit = (squared / 10) % 10; // Step 2: Extract the middle digit of the squared valueint hashIndex = middleDigit % tableSize; // Step 3: Map the middle digit to the hash table indexreturn hashIndex;}int main() {int tableSize = 100; // Define the hash table sizeint numkeys; // Number of keys to be inserted into the hash tablecin >> numkeys; // Input the number of keysvector<int> keys(numkeys); // Using vector to store the keys// Input the keys from the userfor (int i = 0; i < numkeys; i++) {cin >> keys[i];}vector<int> hashTable(tableSize, -1); // Array representing the hash table, initialized to -1// Insert each key into the hash tablefor (int i = 0; i < numkeys; i++) {int key = keys[i]; // Current key to be hashedint hashIndex = midSquareHash(key, tableSize, 1); // Compute hash Index using Mid-Square method// Handle collisions using linear probingwhile (hashTable[hashIndex] != -1) {hashIndex = (hashIndex + 1) % tableSize; // Move to the next index in a circular manner}hashTable[hashIndex] = key; // Insert the key at the calculated or probed index}// Display the contents of the hash tablefor (int i = 0; i < tableSize; i++) {if (hashTable[i] != -1) { // Print only non-empty slotscout << "Index " << i << ": Key " << hashTable[i] << endl;}}return 0;}
INPUT:
3
13 15 16
OUTPUT:
Index 2: Key 15
Index 5: Key 16
Index 6: Key 13
🚨Thanks for visiting classpdfindia✨
Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.
💗 Bookmark our site to stay connected and never miss an update!
💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍
