CODEWITHSUNDEEP
c++hashtime-complexitystd
Alexander Kraynov
Alexander Kraynov

Reputation: 172

What is the time complexity of std::hash<string>

What is the time complexity of

 std::hash <string>

here?

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

is it O(a.size()) so it hashes every symbol individualy?

Upvotes: 5

Views: 2130

Answers (1)

Kilian
Kilian

Reputation: 543

I could not find any general answer to this, but having a look at the MSVC-implementation from Visual Studio 2017 it looks like that:

_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);
}

which is O(N).

I can't come up with any other options to calculate a meaningful hash than iterating over each char in the string. So my assumption is that it will always be O(N).

Upvotes: 8

Related Questions