C++ HashTable Object implementation

Question

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

Answer 1

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

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

Answer 2

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.

Answer 3

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