java - StackOverFlow错误递归

Question

任务已设置为在自定义哈希表中使用递归方法来查找数组中的下一个可用位置来存储键和值。

从startPos(key的哈希值)开始，每次增加stepNo为了跟踪该位置，如果它被占用，我有一种方法可以根据探测器类型/迄今为止采取的步数找到下一个位置。由于某种原因，我收到了溢出错误。

private int findEmpty(int startPos, String key, int stepNum) {
        if(arr[startPos] == null)
            return startPos;

        int next = getNextLocation(startPos, stepNum++, key);
        findEmpty( next ,key, stepNum);

        return startPos;
    }

下面的方法根据其探测类型查找下一个要检查的位置，它采用 startPos( key 的散列值)、stepNo(用于跟踪散列后放置的步骤)和 key 本身。

private int getNextLocation(int startPos, int stepNum, String key) {
        int step = startPos;
        switch (probeType) {
        case LINEAR_PROBE:
            step++;
            break; 
        case DOUBLE_HASH:
            step += doubleHash(key);
            break;
        case QUADRATIC_PROBE:
            step += stepNum * stepNum;
            break;
        default:
            break;
        }
        return step % max;
    }

谢谢，欢迎任何建议或批评。

Answer 1

如果arr[startPos] != null 对于你的整个数组(即你的数组已满)，递归将永远不会结束。

此外，您对递归 all - findEmpty( next ,key, stepNum) 返回的值不执行任何操作。我假设您想返回它而不是总是返回 startPos .

您可能想要进行此更改:

private int findEmpty(int startPos, String key, int stepNum) 
{
    if(arr[startPos] == null)
        return startPos;

    int next = getNextLocation(startPos, stepNum++, key);
    return findEmpty( next ,key, stepNum);
}

此外，您必须有一种方法来检测数组何时已满，在这种情况下，您应该重新调整其大小或引发异常。