如果你知道 unordered_map 的存储原理,你就知道它为啥是无序的。
unordered_map 使用的是字符串哈希算法去将 Key 转变成一个数字,然后这个数对 bucket 取余,这样实现存储和读取,但是你迭代的时候可不是这么玩的,而是 bucket 一个个遍历。
当然,实际情况比这复杂。
不同的 STL 采用的哈希算法一般是不同的,比如 MSVC STL 使用的是 FNV1a:
```
// These FNV-1a utility functions are extremely performance sensitive,
// check examples like that in VSO-653642 before making changes.
#if defined(_WIN64)
_INLINE_VAR constexpr size_t _FNV_offset_basis = 14695981039346656037ULL;
_INLINE_VAR constexpr size_t _FNV_prime = 1099511628211ULL;
#else // defined(_WIN64)
_INLINE_VAR constexpr size_t _FNV_offset_basis = 2166136261U;
_INLINE_VAR constexpr size_t _FNV_prime = 16777619U;
#endif // defined(_WIN64)
_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;
}
```
https://github.com/microsoft/STL/blob/main/stl/inc/xhash而 libc++ 用的是 murmur2 ( 32bit ) cityhash64 ( 64bit ):
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__functional/hash.h