|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <list> #include <vector> #include <iterator> #include <algorithm> using namespace std; class HashTable { private: vector<list<int>> table; int size; // Hash function to compute the index for a given key int hashFunction(int key) const { return key % size; } public: HashTable(int s) : size(s) { table.resize(size); } // Insert a key into the hash table void insert(int key) { int index = hashFunction(key); auto& cell = table[index]; // Check if the key already exists if (find(cell.begin(), cell.end(), key) == cell.end()) { cell.push_back(key); } } // Delete a key from the hash table void remove(int key) { int index = hashFunction(key); auto& cell = table[index]; auto it = find(cell.begin(), cell.end(), key); if (it != cell.end()) { cell.erase(it); } } // Search for a key in the hash table bool search(int key) const { int index = hashFunction(key); const auto& cell = table[index]; return find(cell.begin(), cell.end(), key) != cell.end(); } // Display the hash table void display() const { for (int i = 0; i < size; ++i) { cout << "Bucket " << i << ": "; for (const int& key : table[i]) { cout << key << " -> "; } cout << "nullptr" << endl; } } }; int main() { HashTable hashTable(10); hashTable.insert(10); hashTable.insert(20); hashTable.insert(30); hashTable.insert(40); hashTable.insert(50); cout << "Hash Table:" << endl; hashTable.display(); cout << "\nSearching for 20: " << (hashTable.search(20) ? "Found" : "Not Found") << endl; cout << "Searching for 25: " << (hashTable.search(25) ? "Found" : "Not Found") << endl; hashTable.remove(20); cout << "\nHash Table after removing 20:" << endl; hashTable.display(); return 0; } |
Explanation:
- Hash Table Structure:
vector<list<int>> table;: The hash table is implemented as a vector of lists. Each list represents a bucket where keys with the same hash index are stored.int size;: The number of buckets in the hash table.
- Hash Function (
hashFunction):int hashFunction(int key) const: Computes the index for a given key using modulo operation.
- Insertion (
insert):- Computes the index using the hash function.
- Adds the key to the appropriate bucket if it doesn’t already exist.
- Deletion (
remove):- Computes the index and finds the key in the bucket.
- Removes the key from the bucket if it exists.
- Search (
search):- Computes the index and checks if the key exists in the corresponding bucket.
- Display (
display):- Prints the contents of each bucket in the hash table.
- Main Function (
main):- Creates a
HashTableobject with 10 buckets. - Inserts several keys and displays the hash table.
- Searches for specific keys and displays the search results.
- Removes a key and displays the updated hash table.
- Creates a
Possible Enhancements:
- Dynamic Resizing: Implement resizing to handle growth in the number of keys.
- Load Factor: Use a load factor to trigger resizing and rehashing.
- Handling Collisions: Implement other collision resolution techniques like open addressing or double hashing.