[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