[JDEV] clarification needed in hashtable implementation

kamesh jayachandran kameshj at myrealbox.com
Wed Nov 27 08:34:15 CST 2002


Hi All,
I am looking at jabberd 1.4.2 sources.
I cannot understand the following section.
In the file jabberd/lib/hashtable.c, 
In this method, 
NAMED lookup(HASH_TABLE *table, KEY name, size_t createSize)
The else portion(if table->size is non zero), 
We try to lookup the name from the bucket index i. 
If we did not locate  one we look it up at bucket index i-1 if i!=0, else we make i = table->size -1 and look up.
This is as per my understanding is linear probing in open addressed hash table.
How the code avoids revisiting the elements already probed?
For example,
I have 64 buckets,
My starting bucket index happened to be 12,
I look up at table->v[12] and then table->v[11] ......... table->v[0] and then table->v[63]...........table->v[0].....and repeatedly.
Can you please explain?
with regards
kamesh jayachandran




More information about the JDev mailing list