如果中间有一个null，则'get'方法在线性探测中应该失败。如果没有，我该如何实现get方法？

Question

因此，我正在Java中使用线性探测通过以下方法从头开始构建哈希表：put（int键，字符串值），get（int键），remove（int键）和size（）。因此，我成功地实现了这些方法，但是我有一个理论上的问题。假设我执行以下操作：

    var map = new HashMap(5);
    map.put(1, "a");
    map.put(3, "b");
    map.put(4, "c");
    map.put(8, "d");
    map.put(13, "e");
    map.remove(8);
    System.out.println(map);
    System.out.println(map.get(13));

我的put方法运行正常，并且根据线性探测算法放置了键值对。现在我的输出是：

[null，1 = a，13 = e，3 = b，4 = c]null

所以我的问题是，我的“ get”方法理论上是否应该由于线性方法而失败（由于线性探测），因为存在remove方法将索引为0的值设为null。同样，如果我没有使用删除，我成功获得了13 = e对。

Answer 1

您的问题非常合理，是线性探测中的众所周知的问题之一。

问题是，如果地图中的一项被删除，那么当您尝试搜索一个值时，在搜索过程中您必须通过被删除的项，您将无法找到它。

您也可以不同地询问，如果知道某个值中的某些值可能为空（已删除的项目），那么什么是搜索值的正确方法？

一种解决方案是进行搜索，直到遍历整个地图为止；如果找不到，则返回null。但这是一个非常糟糕的解决方案，因为每次您对地图中不存在的值使用get（或contains）方法时，都必须遍历整个地图（O（n）的复杂度），即不可接受，因为HashMaps应该至少以平均恒定的复杂度（* O（1））实现这些方法。

因此有多种解决方案，您可以研究和阅读它们。我给你一个我知道的解决方案：

在HashMap中，保存另一个数组，该数组将在每个索引处包含在地图中放置值所需的最大步数（或跃点），该索引是您首次获取的位置。每当您在地图中使用put方法将新值放入时，您的方法都会记住您跳到的第一个索引，然后如果您必须经过的总跳数大于助手中该索引处的最大步数数组，请对其进行更新。

现在，在您的get（）和contains（）方法中，当您迈出第一步时，您将读取帮助器数组中允许的最大步骤，然后您只需要跳过此步数，直到可以确保您的价值不存在。这不是在您按下null键时就停止。