为什么哈希表是无序的？

一般是指不保证任何特定的枚举顺序，例如（但不限于）枚举顺序与插入顺序无关。

虽然就常见实现而言，如果没有元素增删，大概率每次遍历顺序会一样，但使用者不应该依赖这种假设。Golang 更进一步，直接把枚举顺序搞成了随机的。

印象中有一门语言为了让人记住哈希表是无序的，故意在枚举时打乱顺序，即使元素无变化，每次枚举顺序也不一样。

无序的意思是不保证每次读取顺序相同。
请在编程时当作: 每次遍历它返回的元素顺序不一样.
实际代码中基本不会遍历 unorderd_map, 如果需要遍历(比如保存到文件), 最好是插入 vec 然后排序 最后再遍历.

实际上，对于同一个程序同一次运行, 插入 a, b, c 首次遍历得到 c,a,b , 那么再重复多次也是 c,a,b.
只要编译器从 vc 换到 gcc , 或者 debug 改 release , 或者优化 O2 改 O3 等等, 很可能 插入 a, b, c 遍历得就变成 b,a,c 之类.

不要依赖于于实现，依赖于规范，规范保证的东西不会变化，其它实现的行为具有不确定性。

这个依赖于实现,

map 也是可以实现成有序的, 但在性能上可能就不如无序的??

比如 java 里有 linkedhashMap 可以保证按插入顺序, 但性能并不如 HashMap 好..



key 在数组里下标不确定这个问题, 可以看 python3.5 后的 dict 实现..

https://www.kingname.info/2019/07/13/python-dict/

所以给我的感觉就是目前实现就是这样, 可能是多方取舍后得到的结果..

@jobmailcn 没错你说的就是 golang

因为它规定了 map 是有序的而 unordered_map 是无序的。更深究一点的话，因为散列表的内部元素顺序是高度依赖实现细节的，没必要规定死；对于用户 key 构成的外部顺序来说，你的第二点是对的。相当于 unordered_map 以无法排序为代价获得了更好的性能。

无需的就是在整个生命周期，不保证它的顺序是一直不变的（没有认为改动顺序的情况下）
这样在语言具体实现的时候，就没有额外的负担

https://stackoverflow.com/questions/18301302/is-forauto-i-unordered-map-guaranteed-to-have-the-same-order-every-time

如果没有修改容器导致的 rehash ，那么枚举顺序不变。

正确的理解是枚举顺序和输入顺序没关系，但数次枚举之间不修改容器的话，数次枚举顺序相同。

“key 数组”是不存在的概念。

不是一定不一样，而是不保证一样。（做到一样也行，但是没必要。）
unordered_map 用哈希表实现，map 用红黑树实现，红黑树的性能要差一些。

我是这么理解的，数组一般是顺序存储，哈希表一般是随机存储，所以就认为数组是有序的，哈希表是无序，个人浅见

这把我问到了，就像“为什么球是圆的？”

如果你知道 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

不是无序，是难以预计而当做无序。

没有人反对你实现一个有序哈希表。

哈希表这个名字更像是一个接口定义，本身就不要求具体实现保证有序。所以你问为什么无序，因为“哈希表”不要求具体实现保证有序........

谢谢大家，明白了。