C++中无序映射的关键搜索时间是多少？

Question

我有一些二维数组，每个二维数组都有一些相应值。我将这些2D数组转换成字符串，然后这些字符串被用作“键”，2D数组的相应值被用作无序映射中的“值”。

二维数组到字符串的转换过程(带示例)：

A3 = {(1,2,3)，(4,5,6)，(7,8,9)}

对应的字符串为: 1+2+3 * 4+5+6 * 7+8+9

那么，无序映射在内部使用的哈希表中的键搜索时间是多少？

Answer 1

如果您的密钥是一个std::string，那么对字符串进行散列会有一定的时间复杂性。微软的Visual C++标准库在散列方面做得非常糟糕，但它的散列时间为O(1) (仅将沿字符串均匀分布的10个字符合并到散列值中)。GNU是另一个极端，它使用了一个非常好的散列函数，它的密钥长度是O(K)。

那么您所说的散列表“键搜索时间”将相对于表中元素的数量摊销为O(1)，但是如果其他字符串已经散列到相同的存储桶中，则需要对它们进行比较:如果长度不同，则每个比较将为O(1)，或者如果找到键或与现有键的初始子字符串匹配，则为O(K)。

这真的是常识-人们困惑的地方是试图为整个操作赋予一个大O值:在这种情况下，它是O(K)，因为这是所有涉及到的操作中最复杂的。