Hash table implementation collision avoidance and resolution in C++

Question

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?

Why not just use `unordered_map` from C++11 or boost? – Mark B Jul 15 '13 at 16:14 — Mark B, Jul 15 '13 at 16:14
@Mark It's an implementation question – Sarp Kaya Jul 15 '13 at 16:28 — Sarp Kaya, Jul 15 '13 at 16:28

score 1 · Answer 1 · edited May 23 '17 at 12:28

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.

I did not quite understand this answer. Could you give a bit more algorithmic examples? — Sarp Kaya, Jul 15 '13 at 16:30
@user1292095: I'm not sure how to make my answer clearer, but a [good book](http://www.amazon.com/books/dp/0262033844) (or even [Wikipedia](http://en.wikipedia.org/wiki/Hash_table)) should tell you everything you need to know about hash tables. — Mike Seymour, Jul 15 '13 at 16:34

Hash table implementation collision avoidance and resolution in C++

1 Answers1