java为什么在HashMap操作的复杂性中不考虑哈希函数的复杂性？

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最坏情况时间复杂度的合适方法是什么呢

如果您从哈希冲突的角度有相同的问题，您可以在这里找到答案： Is a Java hashmap really O(1)?

Answer 1

大O表示法正在讨论操作的复杂性。当涉及到更多的元素时，大多数操作会变得更复杂（即需要更多的时间），并且符号描述了复杂性如何随着元素数量的增加而增加

对于O（1），您的意思是操作独立于所涉及的元素数量。由于自身原因，散列操作可能快也可能慢，但无论您使用的是1个元素的散列映射还是它们的googolplex，散列操作的速度都不会改变

应该注意的是，O（1）是摊销平均数，不保证。最坏的情况被认为是O（n），假设是一个每次返回相同哈希值的哈希函数，但是可以想象（如user889742在注释中所建议的）有一个故意错误的哈希代码函数，其性能甚至比这个还要差

Answer 2

你必须知道(1)是用来做什么的。这是数组中元素的数量。插入HashMap的成本不会因映射中的元素数量而改变（假设您已将插入成本分摊到结构的整个生命周期中）

您的更正是，计算String的hashCode是O(n)，其中n是字符串的长度。但是一旦你拥有了它，你就永远拥有它，不管你使用它多少次。所以它的成本被认为是恒定的

Answer 3

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

给定键的hashCode()的时间复杂度不取决于HashMap中的条目数。因此，计算hashCode()需要O(1)时间（假设示例中的String键的长度不是Map大小的函数-我们可以构造一个奇怪的HashMap<String,String>，其中i放入Map的第i个键具有i个字符-在这种情况下，hashCode()计算需要^}时间，因此，所有HashMap操作将需要O(N)时间，而不是O(1)）

一旦您计算了hashCode()，就需要O(1)时间来确定Map中是否已经存在该键（因为HashMap的每个bucket中的平均条目数受一个常量的限制）