0

因此，我使用 Java 中的线性探测从头开始构建哈希表，方法如下：put(int key, String value)、get(int key)、remove(int key) 和 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 方法工作正常，并根据线性探测算法放置键值对。现在我的输出是：

[空, 1=a, 13=e, 3=b, 4=c] 空

所以我的问题是，如果我的“get”方法理论上失败（因为线性探测）来获取键值对 13=e，因为删除方法在索引 0 处放置了一个空值。另外，如果我不使用删除，我已成功获得 13=e 对。

4

1 回答 1

0

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

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

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

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

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

在您的 HashMap 中，保存另一个数组，该数组将在每个索引处包含将值放入映射所需的最大步数（或跳跃），该索引是您第一个到达的位置。每次你在地图中添加一个新值（使用 put 方法）时，你的方法都会记住你跳转到的第一个索引，然后如果你必须经历的总跳转大于你的助手中这个索引处的最大步数数组，你更新它。

现在，在您的 get() 和 contains() 方法中，当您迈出第一步时，您会从辅助数组中读取允许的最大步数，然后您只需跳过这些步数，直到您可以确定你的价值不存在。当你到达一个空键时，这不是停止。

于 2020-04-30T06:33:46.127 回答