Closed Hashing - Scenario when two elements have the same hash value

Asked Apr 22 '17 at 13:31

Active Apr 22 '17 at 13:31

Viewed 159 times

I'm implementing a closed-hashing class.

I'm trying to find a strategy that will solve the scenario when two elements a and b have the same hash value, I want to search a null place for b which is not a. My trivial solution is to try to go over all of the elements next to a till the end of the table and if I get to the end without finding a null place I'll go to the beginning of the table and go over all of the elements till I reach which will indicate that the table is full. This solution has a running time of O(n) and I need to do it by O(1)

Can you help me please find a solution?

Thanks in advance!

asked Apr 22 '17 at 13:31

user21312

That's called a collision. Look up hash collision resolution. – Carcigenicate Apr 22 '17 at 13:32
Looking up at the moment. Thank you! – user21312 Apr 22 '17 at 13:33
Possible duplicate of [How do HashTables deal with collisions?](http://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions) – Carcigenicate Apr 22 '17 at 13:34
Post the code rather than a long paragraph of English. – weston Apr 22 '17 at 13:50
Some other keywords to search for: "linear probing", "quadratic probing", "double hashing". – Henry Apr 22 '17 at 13:51

Closed Hashing - Scenario when two elements have the same hash value

0 Answers0