使用哈希图的这种方法的复杂性是什么

Question

我知道插入hashmap采用 o（1）时间复杂性，因此，对于插入n元素，复杂性应为 o （n）。我对以下方法有疑问。

代码：

private static Map<Character, Character> mapCharacters(String message) {
    Map<Character, Character> map = new HashMap<>();
    char idx = 'a';
    for (char ch : message.toCharArray()) { // a loop - O(n)
        if (!map.containsKey(ch)) {         // containsKey - take O(n) to check the whole map
            map.put(ch, idx);
            ++idx;
        }
    }
    return map;
}

我正在做的是用顺序“ abcd”映射解密的消息。

因此，我的困惑是上述方法的复杂性是否为 o（n^2）或 o（n）？请帮助我清除我的疑问。

Answer 1

它是摊销的O（n）。 containsKey和put均为amortized o（1）;参见 hashmap.containskey（）的时间复杂性是什么？特别是在Java？。

Answer 2

这两个containskey（）和put（）的时间复杂性将取决于实现equals/hashcode 用于使用的对象的合同作为键。

在引擎盖下，hashmap维护一系列存储桶。每个 bucket 对应于一系列哈希。每个非空键包含 nodes （每个节点都包含与特定映射输入相关的信息），形成a 链接列表或a tree （以来，Java 8 ）。

根据提供的 key 的 hash 确定右 bucket 的过程几乎是即时的，除非计算 hash的过程很重，但无论如何它被认为具有恒定的时间复杂性 o（1）。访问 bucket （即访问数组元素）也是 o（1），但是事情可能会变得棘手。假设 bucket 仅包含很少的元素，则检查它们不会显着增加总成本（同时执行containskey（） and code>和put（）我们应该检查 map 中提供的键），并且总体时间复杂性将为 o（1） 。

但是，在所有出于某种原因出于某种原因最终出现在同一桶中时，然后在链接列表上进行迭代将导致< strong> o（n），如果将节点存储为红黑树，则containskey（） and and put（）的情况下，containskey（）是 o（log n）。

如果字符作为A 键，我们可以正确实现equals/hashcode。适当的哈希功能对于确保对象均匀分布在铲斗之间很重要。但是，如果您使用的是hashcode（）破坏的自定义对象，例如始终返回相同的数字，那么所有条目最终都会在同一存储桶中，并且性能将很差。

碰撞，当不同对象在映射到同一桶的范围内产生哈希时的情况是不可避免的，我们需要一个良好的哈希功能来使碰撞数量尽可能少，这样当非空存量 buckets 的数量超过负载因子时，将“均匀”占用，并扩大地图。

该特定方法的时间复杂性是线性 o（n）。但是，如果您要更改键的类型，可能并非如此。

Answer 3

给定您的原始代码下面：

private static Map<Character,Character> mapCharacters(String message){
    Map<Character, Character> map = new HashMap<>();
    char idx = 'a';
    for (char ch : message.toCharArray()) {
        if (!map.containsKey(ch)) {
            map.put(ch, idx);
            ++idx;
        }
    }
    return map;
}

以下是关于时间复杂性的一些观察：

• 迭代消息中的每个字符将为o（n） - 很明显，如果有10个字符，则需要10个步骤，10,000个字符将采用10,000步。时间复杂性与n直接成比例。
• 在循环内部，您正在检查地图是否已包含该字符 - 使用containskey（），这是一个恒定时间操作，定义为O（1）时间复杂性。这个想法是，评估containskey（）的实际时间是相同的，无论您的地图有10个键还是10,000个键。
• 在>的情况下，您有map.put（）是另一个恒定时间操作，另一个O（1）操作。
• 合并在一起：对于每个nth字符，您将其花费时间在循环中迭代，检查地图是否已经具有并添加；所有这些都是3n（三次n），只是O（n）。

另外，您可以通过更换此块来对代码进行少量改进：

if (!map.containsKey(ch)) {
    map.put(ch, idx);
    ++idx;
}

仅当您放置某些内容时，它保留了运行++ IDX的相同行为，特别是如果是上一件事要么是“不存在”，要么是用“ null”设置的，尽管“ null”不适用于您的代码示例中）：

Character previousValue = map.putIfAbsent(ch, idx);
if (previousValue == null) {
    ++idx;
}

尽管使用containskey（ ）使代码更清晰，还利用了经过良好测试的性能代码，可以免费使用。

在封面下，呼叫 map.putifabsent（） 如下（从OpenJDK 17开始）实现get（），然后是put（）如果不存在键。

default V putIfAbsent(K key, V value) {
    V v = get(key);
    if (v == null) {
        v = put(key, value);
    }

    return v;
}