CODEWITHSUNDEEP
c++hashhashtableimplementation
Sarp Kaya
Sarp Kaya

Reputation: 3784

Hash table implementation collision avoidance and resolution in C++

I found this simple implementation:

http://www.onextrabit.com/view/502c152965e7d250c5000001

However it did not have any collusion avoidance. So I have modified it like this:

#include <iostream>
#include <sstream>

using namespace std;

template <typename ElemType>
class HashTable {
private:
    // data
    ElemType* hashData;
    // hash table size
    int tableSize;
    // djb2 hash function
    int hashing(string key) {
        int hash = 5381;

        for (int i = 0; i < key.length(); i++)
            hash = ((hash << 5) + hash) + (int)key[i];

        return hash % tableSize;
    }

public:
    HashTable(int size) {
        tableSize = size;

        // init hash table data given table size
        hashData = new ElemType[tableSize];
    }

    ~HashTable() {
        delete[] hashData;
    }

    void set(string key, const ElemType& value) {
        int index = hashing(key);
        int i = 0;
        for (;(hashData[index] != (ElemType)NULL) && (i <= tableSize); i++) {
            index = (index + 1) % tableSize;
        }
        if (i > tableSize) {
            cout << "No empty bucket!" << endl;
            return ;
        }
        hashData[index] = value;
    }

    string get(string key) {
        int index = hashing(key);
        stringstream result;
        result << hashData[index];
        int i = 0;
        for (;(hashData[++index] != (ElemType)NULL) && (i <= tableSize); i++) {
            result << " or " << hashData[index];
            index %= tableSize;
        }
        return result.str();
    }
};

int main() {

    HashTable<int> hash(50);

    hash.set("Hello", 12);
    hash.set("World", 22);
    hash.set("Wofh", 25);
    for (int i = 1; i < 10; i++) {
        hash.set("Wofh", i);
    }

    cout << "Hello " << hash.get("Hello") << endl;
    cout << "World " << hash.get("World") << endl;
    cout << "Wofh " << hash.get("Wofh") << endl;
    return 0;
}

This is my first time implementing a hash table. Now "World" and "Wofh" gets the same result from hashing() function. Obviously this is causing a collusion. However when I want to retrieve "World" it shows all colluded values. My question is is there a way to only show "World" number(which is 22) by using only linear probing?

Upvotes: 0

Views: 3726

Answers (1)

Mike Seymour
Mike Seymour

Reputation: 254461

Each table entry will need to contain the set of key/value pairs that match the hash. You'll then need to search that set for the requested key after looking up the table entry.

If collisions are rare, then a simple vector of pairs is probably good enough. If they are frequent enough that the search is too slow, and you can't reduce the frequency by enlarging the table or using a better has function, then consider sorting the vector and using a binary search, or using std::map, or another hash table (with a different hash function), to store the colliding elements.

Of course, unless this is a learning exercise, you'd usually just use std::unordered_map (or the Boost, TR1 or STL equivalents if you can't use a C++11 library).

Also, always remember the Rule of Three when designing a class that manages memory or other resources. Your class will go horribly wrong if anyone tries to copy it.

Upvotes: 1

Related Questions