simple hashing algorithm??

This is a discussion on simple hashing algorithm?? within the C Programming forums, part of the General Programming Boards category; what would be the simplest easy-to-calculate non-collision hash function for mapping the following between 0-10 inclusive: 224562,137456,214562 140145,214576,162145 144467,199645,234534 i ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    8

    simple hashing algorithm??

    what would be the simplest easy-to-calculate non-collision hash function for mapping the following between 0-10 inclusive:
    224562,137456,214562
    140145,214576,162145
    144467,199645,234534

    i tried digit-extraction method for 2,4,5,6 position but i get collision. I am workin gon other methods, meanwhile if someone finds out please let me know asap...

    thanks

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,643
    You will always have collision. You want to pick a hash function that will give a reasonable distributsion of keys. For integers, the most common is "key % <prime #>" - this implies that the size of your hash table will be a prime #.

    You will have collisions so you must choose a collision resolution technique. The most common is seperate chaining - using this technique, each entry in the hash table is a linked list - when there is a collision, the key is simply added to the list.

    key % 11 does well will your set of data - but there is still one collision.

    gg
    Last edited by Codeplug; 04-02-2003 at 08:32 AM.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    8
    yes, i am getting collision with other digits too when using digit-extration , but i was told that there is a non-collision solution. I am working on the folding method to see if it works.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,643
    Well, if your homework is to find a hash function for the given data, then thats different - it's also your homework.

    The solution will most likely be a hashing technique discussed in class or in your book. Nothing wrong with getting creative though

    gg

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    8
    hey Codeplug, i was not saying that you were wrong. I was just letting you know that i am working on the same thing and still not getting non-collision answer. I appreciate you replying thanks

  6. #6
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    I may be pointing out something obvious, but since your data set is from 0-10 then why not just create a table large enough to hold them and just use each number as the index? Am I missing something? Also, how do you handle duplicate values?

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,643
    It's an asignment to come up with a hash function that results in no collisions with the given the set of keys.

    iori, I didn't think you were saying I was wrong - btw
    Post the solution when you find it - I'm curious.

    If you've exhausted all the hashing techniques you know of, I think your best bet is to look for something in this form:

    h(key) = f(key) % 11

    You just have to find a "f(key)" that result in h(key) having no collisions.

    gg

  8. #8
    Registered User
    Join Date
    Apr 2003
    Posts
    8
    hey guys,
    to the ones curious for the solutions i saw in the class:

    one of the solutions to this is using this formula:
    y=(3x-1) mod 11 where x is the given number

    the second solution one was a lil longer:
    say for the number 224562

    we divide the number into 3 parts like this 22,45,62
    now we swap the posiition of the 3 parts : 22,54,26
    we add the numbers: 22+54+26 giving 102
    answer in step#4 mod 21 : 102 mod 21=18
    answer in step#5 mod 12: 18 mod 12=6




    hmmmmmm.......

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating Linked List Using Hashing and Stack
    By m0ntana in forum C Programming
    Replies: 2
    Last Post: 04-07-2007, 07:11 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  3. Simple simple graphics
    By triplem in forum C Programming
    Replies: 2
    Last Post: 05-19-2003, 02:52 AM
  4. a simple algorithm and questions
    By ustuzou in forum C++ Programming
    Replies: 0
    Last Post: 02-18-2002, 10:12 AM
  5. Simple File Creation Algorithm
    By muffin in forum C Programming
    Replies: 13
    Last Post: 08-24-2001, 03:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21