Java：哈希方法时间复杂度

Question

我无法理解散列 table 的时间复杂度如何假设为常量 O(1)。我理解冲突的复杂性如何可以是 O(n) 但是例如我有哈希方法

public int hash(String key)
{
    int hashVal = 0;

    for (int i = 0; i < key.length(); i++)
        hashVal = 37 * hashVal + key.charAt(i);

    hashVal %= tableSize;

    if (hashVal < 0)
        hashVal += tableSize;

    return hashVal;
}

假设没有碰撞，时间复杂度不应该是 O(n)，因为 hash 方法本身使用 for 循环到 key.length() 进行计算，然后需要调用此方法添加、删除和搜索方法？

Answer 1

当谈到哈希 table 的复杂性时，n 是指您将添加到哈希 table 中的事物的数量.是的，您可以说（假设没有冲突）getting/setting 来自散列table 的项目的时间复杂度是散列函数的时间复杂度（这当然取决于您的散列函数）。在您发布的示例哈希函数中，假设密钥长度的上限常数是合理的，这意味着它实际上是 O(1)。然而，如果你有可变的密钥长度，你应该说它是 O(k)，其中 k 是密钥的长度。

Java：哈希方法时间复杂度

Java: Hash method time complexity

java

hash

big-o

hashtable

time-complexity