将随机数插入数组 Java

Question

我必须使用开放寻址将 900 个随机整数散列到一个空 table 中，该空 table 的集合大小为 1009。为了确定数字应该放在 table 中的什么位置，我取随机数 mod 1009，然后将数字放在那里（如果它是开放的）。如果不是，我应该在那之后检查下一个密钥，并继续一个接一个地检查，直到找到一个打开的密钥来放置随机数。到目前为止我的代码是这样的：

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;
        }
    }
}

}

我认为到目前为止我所拥有的都很好我只是对如何将密钥设置为 key + 1 如果原始密钥中已经有内容感到困惑。感谢您的帮助，如果我需要添加任何内容，请告诉我。

Answer 1

您的想法似乎是正确的，只是实施方式不正确。如果 table[key] 不为零，则需要递增 key 直到在 table 中找到索引，其中 table[key] 为零。您可以利用 Java 的余数运算符（就像您已经使用的那样）来防止 key 增加超过数组的边界：

int key = num % 1009;

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

因为 table.length 大于您设置的元素数量，所以不需要检查数组是否已满。另外，请记住 num 可以是 0.

将随机数插入数组 Java

inserting random numbers into array Java

java

arrays

hash

hashtable