std::hash<string> 的时间复杂度是多少

Question

时间复杂度是多少

 std::hash <string>

这里？

#include <iostream>
int main(){
std::string a = "abc";
std::hash<std::string> hsh;
std::cout<<hsh(a);
return 0;}

它是 O(a.size()) 所以它会单独散列每个符号吗？

Answer 1

我找不到对此的任何一般答案，但查看 Visual Studio 2017 中的 MSVC 实现，它看起来像这样：

_NODISCARD inline size_t _Fnv1a_append_bytes(size_t _Val,
const unsigned char * const _First, const size_t _Count) noexcept
{   // accumulate range [_First, _First + _Count) into partial FNV-1a hash _Val
for (size_t _Idx = 0; _Idx < _Count; ++_Idx)
    {
    _Val ^= static_cast<size_t>(_First[_Idx]);
    _Val *= _FNV_prime;
    }

return (_Val);
}

这是 O(N)。

除了迭代字符串中的每个字符之外，我无法想出任何其他选项来计算有意义的哈希值。所以我的假设是它总是 O(N)。