Does anybody know an algorithm for linear probing to avoid collision in hash tables in c.
Thanks.
Printable View
Does anybody know an algorithm for linear probing to avoid collision in hash tables in c.
Thanks.
Linear probing? Means O(n) or O(1) or what?
There is "avoiding collisions", which means come up with a hashing algorithm to hash the key in such a way that there's no chance of another key giving the exact same value. This is only really practical if you can afford a long hash-key, which makes it unpractical in many situations.
The second solution is to accept that collisions happen (but hopefully not too often). If a collision happens, then you have to decide what you want to do - as long as you follow the same pattern every time, there are plenty of different things that CAN be done. The simplest one is to just add one to the hash-index, and see if that's "a better" location. Adding, 2, 4, 8, 16, 17 or some other "randomly choosen" number is another option, or perhaps a "rotate". The real problem comes when you have multiple collisions on the same item, or a "collision on teh collision resolution" - you will have to cope with either and both, in that you continue generating a different hash until you find the right (searching)/free(inserting) slot.
A third solution is a "hybrid" hash/linked list, where each hash-entry contains a linked list of items that have that hash-index. As long as the average list is short, this works reasonably well - it's much better than a linked list, but also avoids the problems connected with hash-collisions. Of course, a really bad hash-algorithm can make this almost as bad as a linked-list by inserting all or most entries in one or two hash-entries, so you still need to work on the hash-algorithm to reduce collisions.
All of these methods have their own strong and weak points (at least some are described above). It depends a lot on what problem you are trying to solve, which to choose.
--
Mats
Linear ProbingThe first step would be to write a program that uses hash tables but doesn't have any form of collision handling.Quote:
Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location.
In an array. When we make hash and use it as an index, if value gives a index that is occupied we save the item in the next free location. Is that it?