Answers:
Answer #1Hashing is the process of mapping strings to integers, usually in a relatively small range. A ``hash function'' maps a string (or some other data structure) to a bounded number (the ``hash bucket'') which can more easily be used as an index in an array, or for performing repeated comparisons. (Obviously, a mapping from a potentially huge set of strings to a small set of integers will not be unique. Any algorithm using hashing therefore has to deal with the possibility of ``collisions.'')
Many hashing functions and related algorithms have been developed; a full treatment is beyond the scope of this list. An extremely simple hash function for strings is simply to add up the values of all the characters:
unsigned hash(char *str)
{
unsigned int h = 0;
while(*str != ' ')
h += *str++;
return h % NBUCKETS;
}
A somewhat better hash function is
unsigned hash(char *str)
{
unsigned int h = 0;
while(*str != ' ')
h = (256 * h + *str++) % NBUCKETS;
return h;
}
Many hashing functions and related algorithms have been developed; a full treatment is beyond the scope of this list. An extremely simple hash function for strings is simply to add up the values of all the characters:
unsigned hash(char *str)
{
unsigned int h = 0;
while(*str != ' ')
h += *str++;
return h % NBUCKETS;
}
A somewhat better hash function is
unsigned hash(char *str)
{
unsigned int h = 0;
while(*str != ' ')
h = (256 * h + *str++) % NBUCKETS;
return h;
}
Answer #2which actually treats the input string as a large binary number (8 * strlen(str) bits long, assuming characters are 8 bits) and computes that number modulo NBUCKETS, by Horner's rule. (Here it is important that NBUCKETS be prime, among other things. To remove the assumption that characters are 8 bits, use UCHAR_MAX+1 instead of 256; the ``large binary number'' will then be CHAR_BIT * strlen(str) bits long. UCHAR_MAX and CHAR_BIT are defined in<limits.h>.)
When the set of strings is known in advance, it is also possible to devise ``perfect'' hashing functions which guarantee a collisionless, dense mapping.
When the set of strings is known in advance, it is also possible to devise ``perfect'' hashing functions which guarantee a collisionless, dense mapping.
Previous Question | Next Question |
How can I find the day of the week given the date? | I need a sort of an approximate strcmp routine ... |