-- A hash table can only associate one value with a given key. If an attempt is made to add a second value for a given key, the second value will replace the first.

本文发表在 rolia.net 枫下论坛say u have 10000 strings in an array.
u need to implement a function to find if a string is in this array.
since this function will be often called, so better implment it to be fast.
how to?
a for loop include strcmp?
right, but slow.
1.create a hash table and a hash function
the hash function calc an integer value from any give string
for example:
int foo(const char* str)
{
int r=0;
while(*str)
r+=*str++;
return r%100;
}

then create a table size equal to your hashfunction's return value's range, in the example above, the range is 100.
struct mytableunit
{
int id; //index into the array
mytableunit* next;
};

mytableunit mytable[100];
in fact we created 100 link list.


then calc the hash value of all the 10000 string,and append them to their corresponding link list(which is index by their hash value)


so how to implement the search function?
bool search(char* s)
{
r=foo(s); //get its hash value
foreach (s1 in myTable[r])
{
strcmp;
}
}
what's the benefit?
if you hash function is good, u need to do 50 strcmp each search(by avarage )
if u don't adopt a hash table, average is 5000
to design ur hash function, try to make a return value scatter averagely in the range,
if your hash function's return value is very close, u get no benefit
eg.
int veryfoo(const char* )
{
return 0;
}

this is a simple example
in fact hash value can be anything suitable no only interger.

for full desctipion of hash table, refer to any data structure book.更多精彩文章及讨论，请光临枫下论坛 rolia.net