CODEWITHSUNDEEP
c++
user40120
user40120

Reputation: 648

C++ HashTable Object implementation

int hazmat::hashStr(char const * const str)
{  
    int count = 0;
    for ( unsigned i = 0; i < strlen( str ); i++ )
    {
        count += str[i]; // get the ascii sum.
    }
    return count % maxSize;  
}

Upvotes: 0

Views: 950

Answers (3)

gnud
gnud

Reputation: 78628

I don't know what your goal with this question is. If your goal is to find a good c++ hash table, use std::tr1::unordered_map if your compiler supports it, otherwise go for e.g Google sparse-hash.

If your goal is to learn about hash tables, then read on.

In a response to this SO question, I implemented a very simple Hash table in Java in my answer:

First, you have to understand a what a hash function is. A hash function is a function that takes a key (for example, an string of arbritrary length) and returns a number as unique as possible. The same key must always return the same hash. A really simple string hashing function in java might look like

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

You can study a good hash function at http://www.azillionmonkeys.com/qed/hash.html

Now, the hash map uses this hash value to place the value into an array. Simplistic java method:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    e.add(new Entry<String, Object>(key, val));
}

(This map enforces unique keys. Not all maps do.)

It is possible for two different keys to hash to the same value, or two different hashes to map to the same array index. There exists many techniques for dealing with this. The simplest is to use a linked list (or binary tree) for each array index. If the hash function is good enough, you will never need a linear search.

Now to look up a key:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Upvotes: 0

Andre
Andre

Reputation: 94

You are misunderstanding how hash tables work. You need to allocate a fixed-length array (in the simplest case) and then each entry must have a linked list so you can resolve duplicates. That is, two strings may result in the same hash value and you will need to walk the linked list and compare the keys.

And yes, like the other poster said, adding characters is a terrible approach. Think about it - "abc" and "cba" will result in the same hash value.

Upvotes: 5

Lou Franco
Lou Franco

Reputation: 89242

Ascii sum isn't a good hash function. Here are some with explanations:

http://www.cse.yorku.ca/~oz/hash.html

Upvotes: 5

Related Questions