<分区>
对于 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 操作的复杂性基本上就是哈希计算的复杂性。
那么什么才是定义 hashmap 最坏情况下 put/get 操作时间复杂度的合适方法呢？
如果你从哈希冲突的角度有同样的问题，你可以在这里找到答案: Is a Java hashmap really O(1)?
最佳答案
当您将时间复杂度计算为 N 的函数时，您必须首先确定 N 代表什么。当我们谈到 HashMap 操作的复杂性时，N 表示 HashMap 的大小(即 HashMap 中存储的键值对的数量)。
给定键的 hashCode() 的时间复杂度不依赖于 HashMap 中的条目数。因此，计算 O(1) 需要 hashCode() 时间(假设您示例中 String 键的长度不是 Map 大小的函数 - 我们可以构造一个奇怪的 HashMap<String,String>，其中 i th 键放入 Map5 字符 - 679105在这种边缘情况下，i 计算将花费 hashCode() 时间，因此，所有 O(N) 操作将需要 HashMap 时间而不是 O(N) )。
计算 O(1) 后，需要 hashCode() 时间来查明 key 是否已存在于 O(1) 中(因为 Map 的每个桶中的平均条目数受常数限制)。
关于java - 为什么HashMap的运算复杂度没有考虑hash函数的复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48213550/