Some problems with your definition:
"a hash function allows you to convert a string into a unique integer identifier which you can then subsequently use as representation of that string in a much more convenient format: namely the integer."
This is not true. You are not converting to a unique identifier at all. Or, at least, not necessarily. That is the significance of collisions. Collisions are an intrinsic aspect of most hash tables.
"You don't want to do the conversion each time the same strong pops up so you generate a look-up table of these strings to their integer representation, and that is your hash table.
This is somewhat confused. A hash table is not a lookup table in this sense, and you do need to do the string -> key conversion every time. The purpose of the hash table is not to save time looking up an integer key for a word, it is to save time iterating through a corresponding array.
"In many ways it's just an encoding of your set of strings into a set of integers."
No. This implies you could take a key and deduce what the string was just based on the integer. That is possible, it would be a form of encryption, it is not a hash table.
Different words can have the same key, for example:
Code:
#include <stdio.h>
#include <string.h>
#define TABLE_SIZE 12
int getKey (char *word) {
int i, len = strlen(word), total = 0;
for (i=0;i<len;i++) total += word[i];
return total%TABLE_SIZE;
}
int main(int argc, const char *argv[]) {
char *words[] = { "word", "static", "etc" };
int i;
for (i=0;i<3;i++) {
printf("%10s %3d\n",words[i],getKey(words[i]));
}
return 0;
}
"word" and "static" here both have the same key. They both go in the first bucket of the hash table.
You might want to read these:
String hashing
Hash tables - open adressing for collision resolution
With regard to usefulness, yeah, hash tables can be used as/are used in databases. However, they also have a lot of "internal" usefulness too. For example, you have a list of files and sizes, you want to know the size for a particular file without iterating all the way through an array or list.
Originally Posted by stabu
