Hash Table Implementation Gaming Project in C++

Projects Inventory

3 months ago

#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;
}

#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 HashTable object 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.

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.

Explanation:

Possible Enhancements:

Related Posts: