0

The unordered map of the C++ standard std::unordered_map is a hashtable data structure, which means it has a constant access time complexity O(1).

But how is the hashcode calculated to give a unique key index to access a member of the table (moreover given an entry that can be of any type) ? I guess the calculation itself might be complex (like MD5) to avoid collisions ?

In that case, is the algorithm still fast enough to consider it negligible while manipulating std::unordered_map ?

EDIT: I wrote std::map instead of std::unordered_map, this is fixed now

Pierre Nicolas
  • 65
  • 2
  • 10
  • 1
    `std::map` does _not_ have O(1) lookup: it's O(log n). `std::unordered_map` does, and the standard likely won't specify which hashing function to use. – erip Feb 01 '18 at 19:36
  • 1
    http://en.cppreference.com/w/cpp/container/map says that `std::map` is usually implemented using Red-Black Trees, not hash tables. – Barmar Feb 01 '18 at 19:38
  • @PierrotNicoldoche O(1) lookup times are amortized with worst-case O(n). This is sometimes worse than average case O(log n) times in tree-based `std::map`. Further, hashing can be expensive in its own right. Uniqueness has a cost. – erip Feb 01 '18 at 19:42
  • 1
    @PierrotNicoldoche Because hashing also causes performance impact. For complex objects it may a significant one. Also, for collections containings thousands of objects there may be still the possibility of collision, which brings another matter - chosing the best hashing algorithm. Also, RB-trees provide decent performance with average `O(log n)`.. – Mateusz Grzejek Feb 01 '18 at 19:43
  • 1
    In general, when talking about the performance of hash tables, we usually assume that the hash function itself is O(1), and expect hash function designers to attempt that. For data types with unbounded size, this usually means that the hash function limits itself to a subset of the input. – Barmar Feb 01 '18 at 19:43

4 Answers4

3

std::map is not a hashmap.

It's implemented using self-balancing trees; therefore, std::map has O(log n) lookup times.

std::unordered_map is a hashmap.

std::unordered_map has (amortized) O(1) lookup times, and it's parameterized by std::hash, which is implementation dependent.

Therefore, there's no one hashing function that is used across implementations.

You're free to provide your own hashing functor granted it implements std::hash, but beware: there lie dragons. A lot of research went into making different C++ implementations fast.

erip
  • 16,374
  • 11
  • 66
  • 121
2

The hashing algorithm for unordered maps is not specified by the standard. It is up to library implementors to decide on that. It might be MurmurHashUnaligned2, Fowler–Noll–Vo or something else. It's implementation defined.

Ron
  • 14,674
  • 4
  • 34
  • 47
2

The unordered map of the C++ standard std::map is a hashtable data structure, which means it has a constant access time complexity O(1).

You confuse the things. Hash table in C++ is std::unordered_map which guarantees a constant search/insert/remove complexity.

The hash algorithm is implementation defined, by you can provide your own hash via std::hash specialization.

Edgar Rokjān
  • 17,245
  • 4
  • 40
  • 67
1

The default hashing algorithm is not specified per se, only that it has a few requirements (Refer to [hash.requirements] and [unord.hash] for specificity toward unordered associative containers like unordered_map):

  • if key1 == key2, then hash(key1) == hash(key2)
  • hash(key) shall not throw an exception
  • it must be implemented as a function object type
  • It must be DefaultConstructible (unordered associative containers) CopyConstructible and Destructible
  • must be swappable (unordered associative containers)
  • hash(key) shall depend entirely on key (therefore the hash always returns the same value for the same key)
  • hash(key) shall not modify the key
AndyG
  • 39,700
  • 8
  • 109
  • 143