Thread: Hashes in c

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    19

    Hashes in c

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

    Thanks.

  2. #2
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    Linear probing? Means O(n) or O(1) or what?
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Linear Probing
    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.
    The first step would be to write a program that uses hash tables but doesn't have any form of collision handling.
    Callou collei we'll code the way
    Of prime numbers and pings!

  5. #5
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    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?
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Putting several hashes together. Better than md5/sha1?
    By idleman in forum C++ Programming
    Replies: 5
    Last Post: 04-03-2009, 12:42 PM
  2. Pointers and hashes
    By chinook86 in forum C Programming
    Replies: 4
    Last Post: 04-04-2007, 01:01 AM
  3. Hashing, indexing and phonetic normalization for approximate str matching...
    By biterman in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 11-21-2006, 09:42 AM
  4. how to create hashes
    By B-Con in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 02-26-2005, 02:13 AM
  5. Hashes?
    By Munkey01 in forum C++ Programming
    Replies: 7
    Last Post: 01-16-2003, 12:18 PM