Quadratic/Double Hashing

[Eclyps19]

I somewhat understand Chain, Linear, and Quadratic hashing, but I am confused about double hashing.

I'd like to know if any of you could help with a couple questions I'm stuck on.

First question I'm stuck on:
Hash the following numbers into a table of size 23 using double hashing. Use 17 for R. {12, 23, 345, 678, 923, 15, 92, 7, 99}

Could someone at least point me in the right direction on this?


Next question:
How can we guarantee that the quadratic problem will be able to place every data element in the table?
--To my knowledge, and from what I've done, quadratic probing is when you do the hash function, you place the item in the next available space instead of next to another item. If this is the case though, it would seem that you wouldn't ALWAYS be able to place every element on the table. What if the number of elements exceeds the table size?



Thanks guys.

[pm_kirkham]

> Use 17 for R
I think you need to look at your notes for what 'R' is; at a guess it's another parameter to your hash function.
Assuming hash(x) = R.x mod 23 then >>> def hash (x):
... return (17 * x) % 23
>>> map(hash, [12, 23, 345, 678, 923, 15, 92, 7, 99])
[20, 0, 0, 3, 5, 2, 0, 4, 4]
So with that hash function you have some collisions, and need to resolve them.

In double hashing, you resolve the collision by stepping by a number whose value is given by a second hash function.

>What if the number of elements exceeds the table size?

All hash tables require extra storage when the number of elements exceeds a limit; chain whenever there's a collision, and the probe based ones whenever the table is full, or a certain proportion of full in some cases.

So for quadratic probing, you would resize the table at least then, if not before.