Double Hashing Infinite Loop

This is a discussion on Double Hashing Infinite Loop within the C++ Programming forums, part of the General Programming Boards category; Hey, I have been working on a program that is supposed to implement double hashing, but I have problems falling ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Location
    Knoxville, Tennessee, United States
    Posts
    20

    Double Hashing Infinite Loop

    Hey, I have been working on a program that is supposed to implement double hashing, but I have problems falling into an infinite loop, and Im not sure when to give the program the signal to say "hey, your in an infinite loop, break out of it"

    Right now, I keep exiting way to early. I would really appreciate some help, I have been putting many hours into this program, and im stuck at this part and this was needing to be finished yesterday in all reality.

    Given:
    Primary Hash Function: XOR

    Secondary Hash Function: Last7

    table size = size of table(most likely not prime)

    loop = variable used to see how many times i go through the while loop, I've tried setting it to 1 and 0

    step = It should be the hash2 % table size;

    nkeys = variable used to check the number of successful adds

    My Code:

    Code:
    // XOR and Double
        else    if(Fxn == 2 && Coll == 2){
            i = 1; // should it be 0 or 1?
            index = XOR(key) % table_size;
            if(keys[index] == ""){
                keys[index] = key;
                vals[index] = val;
                nkeys++;
            }
            else{
                step = Last7(key)%table_size;
                if(step == 0){
                    step = 1;
                }
                while(keys[index] != ""){
                    index = (XOR(key) + (i*step)) % table_size;
                    if(keys[index] == ""){
                        keys[index] = key;
                        vals[index] = val;
                        nkeys++;
                    }
                    dbl_test = (XOR(key)+step)%table_size;
                        loop++;
                    if(loop >= table_size){ //not sure if this is right
                        cerr <<"Couldn't put " <<key<<" into the table"<<endl;
                        exit(1);
                    }
                    i++;
                }
            }
    
        }
    Look guys, I really appreciate your help in advance!

  2. #2
    Registered User
    Join Date
    Oct 2010
    Location
    Knoxville, Tennessee, United States
    Posts
    20

    Improved?

    Here is the new and improved code, however I am getting an error about not being able to add a single input into the table.

    Code:
       // XOR and Double
        else    if(Fxn == 2 && Coll == 2){
            i = 1;
            index = XOR(key) % table_size;
            if(keys[index] == ""){
                keys[index] = key;
                vals[index] = val;
                nkeys++;
            }
            else{
                step = Last7(key)%table_size;
                if(step == 0){
                    step = 1;
                }
    
                while(true){
                    index = (XOR(key) + (i*step)) % table_size;
                    if(keys[index] == ""){
                        keys[index] = key;
                        vals[index] = val;
                        nkeys++;
                        break;
                    }
                    if(index == XOR(key)%table_size){
                        cerr <<"Couldn't put " <<key<<" into the table"<<endl;
                        exit(1);
                    }
                    i++;
                }
            }
    
        }

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,663
    How about posting a very small main() to test your code, along with the two hash functions?

    At least then it would be (for those with time + compiler) to copy/paste the code and see what you're seeing in a few seconds.

    Otherwise, it's a case of "that's nice dear", because we can only make blind guesses as to all the possible things you could have got wrong.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    How can we know what does a code, which begins with "else" keyword, do?...
    I never put signature, but I decided to make an exception.

  5. #5
    Registered User
    Join Date
    Oct 2010
    Location
    Knoxville, Tennessee, United States
    Posts
    20
    Well, I was wanting to avoid posting the other 300 lines of code, luckily though, I was able to get the issue resolved, it turned out that I could not possibly test my function without having completed another function, so I was getting many false negatives.

    Thanks for the responses regardless!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Functions, have errors...NEED HELP FAST
    By alkamenes in forum C++ Programming
    Replies: 6
    Last Post: 11-02-2009, 02:00 PM
  2. Cosine fucntion and infinite loop.
    By youareafever in forum C Programming
    Replies: 2
    Last Post: 11-07-2008, 03:45 AM
  3. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 08:13 AM
  4. Replies: 1
    Last Post: 10-27-2006, 01:21 PM
  5. Replies: 6
    Last Post: 10-23-2006, 07:22 PM

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