c++ - 使用静态字符串值访问 std::map 时，访问时间是否仍为 O(log n)？

Question

std::map<string, int> dict;
for(int i = 0; i < 300; ++i)
{
    dict["afsfgsdg"] = i*i;
    dict["5t3rfb"] = i;
    dict["fddss"] = i-1;
    dict["u4ffd"] = i/3;
    dict["vgfd3"] = i%3;
}

由于字符串值在编译时已经知道，编译器会在编译时对它们进行哈希处理，而不是在运行时对这些字符串进行哈希处理吗？

Answer 1

std::map不散列任何东西。它使用比较来查找元素，它的 O(lg n ) 界限是当映射中有n 个键时所需的比较次数。它没有表达任何关于比较本身的成本。

即程序可能会使用一些短路的字符串比较，首先进行指针比较，但比较次数在最坏的情况下将保持对数（当项目位于树中的一个叶子时，对于典型的红色-黑树实现）。

Answer 2

编译器会在编译时散列它们，而不是在运行时散列这些字符串吗？

不，因为std::map不使用散列，它是红黑树或类似的二叉树。

它每次都在树中执行查找。

首先编译器将转换"afsfgsdg"为 a std::string，然后在地图中对字符串进行 O(log n) 搜索。

Answer 3

分析渐近性能的算法正在研究必须执行的操作以及它们添加到等式中的成本。为此，您需要首先知道执行的操作是什么，然后评估其成本。

在平衡二叉树（恰好是映射）中搜索键需要 O(log N) 复杂操作。这些操作中的每一个都意味着比较键是否匹配，如果键不匹配，则遵循适当的指针（子）。这意味着总成本与这两个操作的成本的 log N 倍成正比。跟随指针是一个常数时间操作 O(1)，比较键取决于键。对于整数键，比较快速 O(1)。比较两个字符串是另一回事，它所花费的时间与所涉及的字符串的大小成正比 O(L) （我故意使用 L 作为字符串参数的长度，而不是更常见的 N。

当您将所有成本加起来时，您会得到使用整数作为键的总成本为 O(log N)*(O(1) + O(1))，相当于 O(log N)。（O(1) 隐藏在 O 符号默默隐藏的常数中。

如果使用字符串作为键，总成本为 O( log N )*( O(L) + O(1) )，其中常数时间操作被成本更高的线性操作 O(L) 隐藏，可以转换为O(L * log N)。也就是说，在以字符串为键的映射中定位元素的成本与映射中存储的元素数量的对数乘以用作键的字符串的平均长度成正比。