Какова временная сложность std :: hash <string> - PullRequest
Новая
       29

Какова временная сложность std :: hash <string>

1 голос
/ 10 марта 2019

Какова временная сложность 

 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 ()), поэтому он хэширует каждый символ индивидуально?

1 Ответ

2 голосов
/ 10 марта 2019

Я не смог найти никакого общего ответа на этот вопрос, но, глядя на MSVC-реализацию из Visual Studio 2017, это выглядит так: 

_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).

...