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;
}
-
All of that code and background, and your best question is "is there anything that I can do better?"? That ain't much of a question there, lampshade.abelenky– abelenky2009-09-29 20:33:57 +00:00Commented Sep 29, 2009 at 20:33
-
Im still very much of a beginner. I dont understand how to do this..I've read up on linear probing. Do i need to test for the address? Each time the references are the same.user40120– user401202009-09-29 20:36:36 +00:00Commented Sep 29, 2009 at 20:36
-
Never do this [i < strlen( str );] in a loop. strlen calculates the length of the string by enumerating through the whole string looking for the terminator. You are doing that on each iteration of the loop.Lou Franco– Lou Franco2009-09-29 20:38:00 +00:00Commented Sep 29, 2009 at 20:38
Add a comment
|
3 Answers
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.
4 Comments
Pete Kirkham
-1 for the "must" on chained hash implementation. Linear probing as suggested in the OP is fine, and often easier.
Andre
May I suggest that you provide a better answer next time and move ahead by gathering more votes instead of shooting other answers.
TheFuzz
@Pete Kirkham. I wouldn't say that linear probing is easer. If you already have a link list wrote why not just make your hash table chain linked. Besides the link list will already have the find() and remove() functions ready to be called. +1 @Andre
Pete Kirkham
Normally for minor errors people correct their posts when downvoted. All you need is to change 'some hashtables work' rather than "hashtables work"
Ascii sum isn't a good hash function. Here are some with explanations:
Comments
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;
}
