give u a sample how hash table is used

blaise (blaise)
<本文发表于: 相约加拿大:枫下论坛 >
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;
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])
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
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.
<本文发表于: 相约加拿大:枫下论坛 >

2001-7-4 -04:00

回到话题: what's the hash table in the c++ world? thanks !

回到论坛: HOME枫下论坛枫下论坛主坛工作学习IT杂谈