为什么HashMap的运算复杂度没有考虑hash函数的复杂度？

Question

对于HashMap<String, String> map每次键-值对被插入到散列计算地图-

java.lang.String#hashCode

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

由于不言自明，put 操作的复杂性基本上就是哈希计算的复杂性。

那么，为 put/get 操作定义 hashmap 最坏情况时间复杂度的适当方法应该是什么？

如果您从哈希冲突的角度有同样的问题，在这里您可以找到答案： Java 哈希映射真的是 O(1) 吗？

Answer 1

当您将时间复杂度计算为 的函数时N，您必须首先确定N代表什么。当我们谈到HashMap操作的复杂性时，N代表了 的大小HashMap（即存储在 中的键值对的数量HashMap）。

hashCode()给定键的时间复杂度不依赖于HashMap. 因此需要O(1)时间来计算hashCode()（假设String您示例中的键的长度不是大小的函数Map- 我们可以构造一个奇怪的HashMap<String,String>地方，其中i放置在Maphasi字符中的th 键- 在这种边缘情况下，hashCode()计算将需要O(N)时间，因此，所有HashMap操作都需要O(N)时间而不是O(1))。

一旦计算了hashCode()，就需要O(1)时间来确定键是否已经存在于 中Map（因为 的每个存储桶中的平均条目数HashMap受常数约束）。

Answer 2

大O表示法谈论的是操作的复杂性。当涉及更多元素时，大多数操作会变得更加复杂（即花费更多时间），并且符号描述了复杂性如何相对于元素数量增长。

对于 O(1)，您是说该操作与所涉及的元素数量无关。哈希操作可能因其自身原因而快或慢，但无论您有 1 个元素的 HashMap 还是包含 1 个元素的 googolplex，该速度都不会改变。

应该注意的是，O(1) 是摊余平均值，并不是保证的。最坏的情况被认为是 O(n)，假设是一个每次返回相同哈希值的哈希函数，但可以想象（正如 user889742 在评论中提出的那样）有一个故意不好的哈希码函数，其性能甚至比那。