inserting random numbers into array Java

Question

I have to hash 900 random integers into an empty table that has a set size of 1009 using open addressing. To determine where the number should go in the table I take the random number mod 1009 and then place the number there if it is open. If not I should check the next key after that and keep checking one by one until I find an open one to place the random number. The code I have so far is this:

import java.util.*;

public class openAdd{
public static void main(String[] args) {
    //set table length
    int[] table = new int[1009];

    //insert 900 random integers into the table using open addressing
    //random number % table size = the key the number should be placed
    //if the key is already taken go to the next key until you find an open one
    Random randomGenerator = new Random();

    for (int i = 0; i < 900; i++) {
        int num = randomGenerator.nextInt(99999);
        int key = num % 1009;
        if (table[key] == 0) {
            table[key] = num;
        }
    }
}

}

I think what I have so far is good I am just confused on how to go about setting the key to key + 1 if there is already something in the original key. Thank you for your help, and just let me know if I need to add anything.

kind of, Im thinking I should include an else statement after the if and then have a for loop inside that and then once I find a key that == 0 I should place the number there. — justinbg10
– justinbg10, Commented Oct 19, 2018 at 0:35
I am just not sure what to put into the for loop, and then once I reach the end of the array and its still all full how do I go back to the beginning of it to continue the check — justinbg10
– justinbg10, Commented Oct 19, 2018 at 0:40

Jacob G. · Accepted Answer · 2018-10-19 00:46:15Z

1

You seem to have the right idea, just not the right implementation. If table[key] is nonzero, then you need to increment key until you find an index in table where table[key] is zero. You can utilize Java's remainder operator (like you already are) to prevent key from increasing over the bound of the array:

int key = num % 1009;

if (table[key] == 0) {
    table[key] = num;
} else {
    while (table[key = (key + 1) % table.length] != 0);
    table[key] = num;
}

Because table.length is greater than the amount of elements you're setting, there's no need to check if the array is full. Also, keep in mind that num can be 0.

answered Oct 19, 2018 at 0:46

Jacob G.

29.8k7 gold badges70 silver badges122 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

justinbg10 Over a year ago

thank you, this answers my original question perfectly! If the key + 1 does go all the way to the end of the table, because it could start almost at the end, does the key +1 go back to 0 after it reaches the end?

Jacob G. Over a year ago

If you use (key + 1) % table.length, then it will go back to 0 after reaching the end.

Jim Mischel Over a year ago

Although it's true that you don't need to check if the array is full in this case, the reality is that somebody is likely to use this code in some other situation. And it will go into an infinite loop when the table is full. You should add the full check to "future proof" your code.

Collectives™ on Stack Overflow

inserting random numbers into array Java

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related