Geek asks and answers

Std :: unordered_map: Asymptotic (search, insert, delete) performance in key size and data type

I use std :: unordered_map in C ++ 11. I decide between string keys and a composite data type (for example, two long lines assembled in a structure to store UUIDs).

Is there an easy way to determine the performance characteristics of searches, inserts, deletes, etc. when hashmap uses the std :: string keys as opposed to when hashmap uses some other simple key data type?

Once I have selected the data type: std :: unordered_map search, the delete and insert operations are constant in the number of elements on the map, but if I have a very long key (say 128 bits), I’ll start to wonder about the performance of these operations in the amount of the key.

Is this something bothering, or will the difference be negligible?

+3
source share
1 answer

I think you misunderstood the guarantees of complexity of std::unordered_mapinserting, deleting and searching. In the worst case, O(size())it is only mentioned if you implement a terrible hash function for a type Keythat generates many collisions, but different keys are not compared with equal ones.

Say what you have

struct terrible_hash
{
  std::size_t operator()(int i) const
  { return 42; }
};

std::unordered_map<int, foo, terrible_hash> m;

All inserts of new keys into the above map will be O(m.size()), because the function will be forced to search linearly through each element, since they all have the same value.

Given an acceptable hash function, these operations should be (amortized) constant time.

string 128- (UUID) ; , , , . , :

  • hash<string> . , / , VS2013:

    size_t _Val = 14695981039346656037ULL;
for (size_t _Next = 0; _Next < _Count; ++_Next)
{
  _Val ^= (size_t)_First[_Next];
  _Val *= 1099511628211ULL;
}
return _Val;

  • 128- 64- . , 64- .

    template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

    boost::hash_combine. , MSVC std::hash<uint64_t>, 64- unsigned char * , , , .

, , , .

+4

More articles:


All Articles