I have been trying to do double hashing however I am confused between what happens upon using the double hashing function h'.
when the first hash function has a collision is it the case that the value of the secondary hash function gets added to the first hash function's value?
I have tried many ways and haven't been able to figure this out, the problem in question is an image at the following link:
http://postimg.org/image/k6ko6e0gp/
how would this be solved with double hashing? where there is 3 elements in the array already and 3 more need to be inserted
Double hashing is a way to resolve the collision (multiple keys hashed to a single index). In double hashing, there will be two hash functions used; In case of collision, second hash function will be used to find the step size with which the table should be searched for an empty cell to place the key. This link gives the overview of possible collision resolution methods. http://www.cs.utexas.edu/users/mitra/csSpring2016/cs313/lectures/hash.html
In your case, after checking the image attached, it is clear that the key 16 would collide with some other key in index 6, so, you will have to apply the second hash function to determine the step size. From the index from first hash, every (step size)th element shall be checked for an empty cell. Once an empty cell is found, the key shall be placed in that cell. For instance, first hash index is 0, and step size is 2, then indices 0, 2, 4 .. should be checked. Please keep in mind, sometimes, probing needs wrapping around to the beginning of table to find the empty cell.
So, according to the image attached, key 16 will get step size of 2. So, from 6, with step size 2, next available slot is index 1, which is free :)
In case no empty cells could be found in this case, the hash table shall be resized with new capacity. This is known as rehashing which is generally a costly operation, as it needs to rehash all the elements in the table. It shall be done, once after the table reached certain size threshold.