为什么可以说hashmap的复杂度是O(1)

Question

我用了很长时间的hashmap，我一直认为它的复杂度是O(1)。

我知道hashmap的key是hash函数，可以将一个key映射到一个value。如果哈希函数设计得好，碰撞可以保持在可接受的水平。

今天看了一个哈希函数，把字符串哈希成哈希码：

unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

显然有一个while循环，所以它的复杂度是O(n)。

现在我很困惑。 hashmap 的复杂度总是 O(1) 吗？或者复杂度取决于我们如何设计哈希函数，也就是说，如果哈希函数不够好，复杂度可能是 O(n) 甚至更糟？

Answer 1

首先，哈希图并不复杂。插入哈希图中确实如此。从哈希图中读取确实如此。操作有时间复杂度，对象没有。对象可能具有内存复杂性，但这不是我们在这里讨论的内容。

其次，哈希图并不总是具有 O(1)，即使对于读取也是如此。它的平均时间为 O(1)。单次读取的实际时间最多为 O(n)，具体取决于您解决冲突的方式。例如，如果您使用链表冲突解决方案，写入总是 O(1)，但如果您的散列函数不好，读取可能高达 O(n)。如果您使用调整大小分辨率，读取始终为 O(1)，但写入可以为 O(n)。其他解决方案获得其他余额。

第三，这不是哈希映射。这是一个哈希函数。它将复数值转换为数字值以进行比较（更正式地说，它将对象从大小为 N 的 space 映射到大小为 M 的 space，其中 N>M）。这并没有成为 O(1) 的任何承诺，它是一个与哈希映射完全不同的概念。散列映射使用散列函数将对象插入到一个非常大的数组中，因此如果散列函数足够好以致于很少发生冲突，则读取和写入的时间为 O(1)。哈希函数本身可以很复杂，具体取决于数据及其工作方式。字符串哈希通常在字符串上为 O(n)，因为您想尝试使其唯一（如果您在说 4 个字符后停止，所有前 4 个字符的字符串都会发生冲突）。

为什么可以说hashmap的复杂度是O(1)

Why can we say the complexity of hashmap is O(1)

c++

algorithm

hashtable

hashmap