0
$\begingroup$

I have the following hash table with hashcodes being quadratic numbers.

Table

Why do 0, 16, and 64 have different number of collisions when they map to the same number (line %16). Also how is it possible for 64 to have 6 collisions?

$\endgroup$

1 Answer 1

2
$\begingroup$

Here collisions means the number of (occupied) positions visited before finding a free spot and placing the number.

64 goes to 0(occupied by 0) - 1(by 1) - 2(by 16) - 3(by 49) - 4(by 4) - 5(by 36) - 6(bingo)

The table is consistent with linear hashing and stepsize $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.