java - 将随机数插入数组Java

Question

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

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 设置为 key + 1 如果原始 key 中已经有内容感到困惑。感谢您的帮助，如果我需要添加任何内容，请告诉我。

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。