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

Question

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

我知道hashmap的关键是哈希函数，它可以将一个键映射到一个值。如果哈希函数设计得好，冲突可以保持在可接受的水平。

今天我读了一个哈希函数，如下所示，它将字符串哈希为哈希码：

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 的空间映射到大小为 M 的空间，其中 N>M）。这并不保证 O(1)，它是与哈希映射完全不同的概念。哈希映射使用哈希函数将对象插入到非常大的数组中，因此如果哈希函数足够好以至于很少发生冲突，则读取和写入的时间为 O(1)。哈希函数本身可以是任何复杂性，具体取决于数据及其工作方式。字符串哈希值通常是 O(n)，因为您想尝试使其唯一（如果您在 4 个字符后停止，则具有前 4 个字符的所有字符串都会发生冲突）。