Re: hash table quadratic probing help please
Totti wrote:
Hi all, i am trying to do a quadratic hashing but i am having some
difficulties probably because i am not in the right logic.using this
code:
public void insert(DataItem item)
{
int key = item.getKey();
int hashVal = hashFunc(key);
int x = 0;
while(arr[hashVal] != null )
This line assumes that 0 <= hashVal < arr.length, which
may in fact be true but suggests an "unhealthy" coupling
between arr and hashFunc.
{
hashVal = hashVal + (int) Math.pow(x,2); // go to next cell
Three points about this line: First, `x * x' would be a
good deal simpler. Second, x is zero on the first trip through
the loop, so hashVal is unchanged and the first two probes will
go to the same spot in the array. Third, if you make so many
probes that x grows to 46341 you'll find that x*x becomes negative
and messes up the hashVal calculation (probably not a problem
unless the hash table gets completely overstuffed).
hashVal %= size; // wraparound if necessary
I guess size is equal to arr.length, or at any rate is no
larger than arr.length? It would be better to use arr.length
directly.
How certain are you that this probe sequence will eventually
visit every array index? For example, if the array size is eleven
and the first hashVal is zero, locations [2], [4], [7], and [9]
are untouched in the first hundred probes (unless I botched my
quick-and-dirty spreadsheet).
x++;
}
arr[hashVal] = item;
}
thi seems working ok untill something has taken the slot meant to be
the item's i am inserting at this moment, [...]
It's unfortunate that you didn't reveal the manner in
which the code fails. You tell us it's "working ok" in some
conditions, and you tell us the condition where it doesn't
work, but you don't tell us what goes wrong or why you think
it is wrong.
--
Eric Sosman
esosman@ieee-dot-org.invalid