Does anybody know an algorithm for linear probing to avoid collision in hash tables in c.

Thanks.

Printable View

- 08-08-2007cosmo1996Hashes in c
Does anybody know an algorithm for linear probing to avoid collision in hash tables in c.

Thanks. - 08-08-2007siavoshkc
Linear probing? Means O(n) or O(1) or what?

- 08-08-2007matsp
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 - 08-08-2007QuestionC
Linear Probing

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.

- 08-08-2007siavoshkc
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?