Thread: hashing help

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    19

    hashing help

    Can somebody help me find the problem with my hash tables program. I have to produce the following output:

    % full = 5, % clashes = 5
    % full = 10, % clashes = 2
    % full = 15, % clashes = 6
    % full = 20, % clashes = 7
    % full = 25, % clashes = 10
    % full = 30, % clashes = 14
    % full = 35, % clashes = 17
    % full = 40, % clashes = 19
    % full = 45, % clashes = 21
    % full = 50, % clashes = 27
    % full = 55, % clashes = 29
    % full = 60, % clashes = 33
    % full = 65, % clashes = 34
    % full = 70, % clashes = 36
    % full = 75, % clashes = 38
    % full = 80, % clashes = 42
    % full = 85, % clashes = 44
    % full = 90, % clashes = 45
    % full = 95, % clashes = 48
    % full = 100, % clashes = 50

    but my program gives the following:

    full = 5, clashes = 15
    full = 10, clashes = 7
    full = 15, clashes = 10
    full = 20, clashes = 10
    full = 25, clashes = 12
    full = 30, clashes = 15
    full = 35, clashes = 19
    full = 40, clashes = 20
    full = 45, clashes = 22
    full = 50, clashes = 28
    full = 55, clashes = 30
    full = 60, clashes = 34
    full = 65, clashes = 35
    full = 70, clashes = 37
    full = 75, clashes = 39
    full = 80, clashes = 42
    full = 85, clashes = 44
    full = 90, clashes = 45
    full = 95, clashes = 48
    full = 100, clashes = 51

    Can somebody help me spot the problem with my code?Please

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* Small program to explore using hash tables.
    
       1. The hash table takes up to 400 items
       2. The program generates 400 six digit numbers.
       3. It uses a hashing routine to place them in the hash table
       4. The program prints a report on the percantage of clashes that 
          occur for every 20 numbers placed in the table
     */
    
    #define EMPTY -1
    
    int main()
    {
       int count, hash, number;
       int clashes, hashTable[400];
    
       /* initialise the random number generator */
       srand(1);
    
       /* initialise hash table */
       for (count=0; count<400; count++) hashTable[count] = EMPTY;
    
       /* generate 400 six digit numbers and put in hash table */
       for (count=0; count<400; count++)
       {
          number = rand() % 1000000;     /* create 6 digit number */
          hash = number % 400;           /* get a hash value of number */
    
          /* determine if we have a clash */
          if (hashTable[hash] != EMPTY)  
          {
             clashes++;
    
             /* Find next empty slot in hashTable */
             while (hashTable[hash] != EMPTY)
             {
                hash = (hash + 1) % 400;
             }
          }
          hashTable[hash] = number;
    
          if ((count+1) % 20 == 0)
          {
             printf(" full  = %d,  clashes = %d\n", 
                     (count+1)*100/400, (clashes)*100/count);
          }
       }
    
       return 0;
    }

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I'm not quite sure what you're asking. Since you're using random inputs, there is little chance that you will get an exact same result as what you've typed. Plus, it isn't even random numbers since you seed it with 1, instead of time(NULL) or something.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>it isn't even random numbers since you seed it with 1, instead of time(NULL) or something.
    True, but for debugging purposes, seeding srand() with a static number is the way to go.

    But of course, your random number list is not the same as mine, so I get different results, hence the test is really invalid across compilers.

    To do a proper test, you'll need a list of static input numbers.

    >>number = rand() % 1000000;
    The 1000000 is probably larger than RAND_MAX anyway, so there's little point in doing the mod.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    19
    I wanted to know why my numbrer of clashes differ.
    My lecturer has an executable that produces the same results every time.
    The only difference with my one is the number of clashes and i can figure out why they differ with the lecturers

  5. #5
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Originally posted by alokin
    I wanted to know why my numbrer of clashes differ.
    My lecturer has an executable that produces the same results every time.
    The only difference with my one is the number of clashes and i can figure out why they differ with the lecturers
    See my previous post.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: hashing help

    Code:
       /* generate 400 six digit numbers and put in hash table */
       for (count=0; count<400; count++)
       {
          number = rand() % 1000000;     /* create 6 digit number */
    This doesn't generate a six digit number. It creates a number that MAY BE six digits.

    Code:
    for( count = 0; count < 400; count++ )
    {
        number = 100000 + (rand( ) % 900000);
    That generates a six digit number.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    They mean binary digits. What else could they mean?
    Usually when someone says a 6 digit number they mean
    has you have coded it so I think you are correct.

    I suspect that you have to set clashes to 0 in the 2nd loop. Can
    you give a proper definition of clashes?

    Coding it like that might give you an infinite loop if the table is full.
    You also shouldn't use so many magic numbers such has 400.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Nick
    They mean binary digits. What else could they mean?
    I just showed you what else it could mean. I'm assuming this is homework. Here, let's assume I'm the teacher, and I say: "Using six digit numbers, populate a hash table until it's full and print the number of clashes."

    Now you may assume that I meant "Don't go over 6 digits", when in fact I meant "Use only six digit numbers. Don't use one, two, three, four, five, or seven digit numbers, use ONLY six digit numbers."

    Besides, "six binary digits" mean that the number is only a range of zero to 63. Count'm: 000000 to 111111 ... Six binary digits, for a decimal value of 0 to 63.

    This is the reason you need to be specific in your requirements.

    As for what a clash is, it's obvious if you look at their code:

    If the hash bucket isn't empty, that's a clash. IE: Trying to use a bucket that's being used.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    000001 could be a 6 digit number. It depends on your interpretation, I suppose.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Hammer
    000001 could be a 6 digit number. It depends on your interpretation, I suppose.
    In mathmatics, you NEVER include preceding zeros before the decimal point. Likewise, you never include extra zeros after the decimal point. 1 is not a six digit number. Period. Anyway, it's like I said: they need to be speficic. But again, if I ask you:

    True or false: This always produces three digit numbers:

    x = rand() % 1000;

    false

    If you answer true, your teacher would fail you. 000001 is not a six digit number.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    thats like saying a six digit number wheras preceeding digits of a digit > 0 are all > 0 or null. in mathematics, your right, but for program purposes, i would say 000001 is a six digit number IMO

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Cgawd
    thats like saying a six digit number wheras preceeding digits of a digit > 0 are all > 0 or null. in mathematics, your right, but for program purposes, i would say 000001 is a six digit number IMO
    Well you'd be wrong. If you are given a number and it is converted to a decimal form, which is what is happening here, then it is a single digit number.

    x = rand() % 1000000;

    Assuming the result of rand is 1, x will store a single digit, decimal value.

    If you print this, using standard printing methodology, you will get a single digit number. You can force it to display more, but this is atypicial.

    One is not a six digit number. I refuse to argue this point with you because you are flat out wrong.

    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    1 is not a 'Significant' 6 digit figure, but could be a 6 figure digit ::shrugs:: IMO(opinions are never wrong!)

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Cgawd
    1 is not a 'Significant' 6 digit figure, but could be a 6 figure digit ::shrugs:: IMO(opinions are never wrong!)
    Of course opinions are wrong. It was the world's opinion that it was flat, until it was proven otherwise. That's like saying "I believe this is the way it is... Beliefs are never wrong." But now we're off topic.

    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    One is not a six digit number. I refuse to argue this point with you because you are flat out wrong.
    Like I said in the first place, "It depends on your interpretation". My original thoughts were probably outside of the rand() example seen here.

    For maths purposes, you are correct, 1 is 1, and is 1 digit long. But for other purposes, 000001 can sometimes be viewed as 6 digits.

    Assuming the result of rand is 1, x will store a single digit, decimal value.
    Technically not correct, imho. It will store a binary representation of a decimal 1 in an int variable, which will require lots of preceding binary 0's to pad the int. Therefore, we are storing is as 0000000....1 And how many digits is that?!

    Anyway, pointless argument really We're both right, in our own way.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

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. 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
  3. Replies: 8
    Last Post: 09-11-2006, 11:26 AM
  4. Doubt about Hashing
    By louis_mine in forum C Programming
    Replies: 1
    Last Post: 11-11-2005, 12:00 AM
  5. Double Hashing
    By carrja99 in forum C++ Programming
    Replies: 1
    Last Post: 03-28-2003, 08:36 AM