为什么哈希表是无序的？

[balabalaXMX]

C++ STL 里说 unorderd_map 遍历是无序的，意思是说每次遍历它返回的元素顺序不一样？还是说它返回的顺序和输入顺序不一样？还是两者都有？

第一个问题我的理解是因为 unorderd_map 会随着 map 元素增加或者减少做 rehash ，也就是会调整 mod 的值或者桶的大小，所以元素之间的相对顺序会改变，但是如果不对 map 做增加或者删除操作的话，是不是每次遍历的顺序就是一样了？

第二个问题我的理解是这个遍历可能是按照 key 数组的下标的顺序来返回的，那么原始 key 值经过了 hash 后存入 key 数组的下标是不确定的，所以这个输入顺序和输出顺序完全没有关系。

这样理解对吗？

[mind3x]

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

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

[lovelylain]

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

[viruscamp]

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

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

[thinkershare]

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

[BBCCBB]

这个依赖于实现,

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

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



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

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

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

[maocat]

@jobmailcn 没错你说的就是 golang

[agagega]

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

[ksc010]

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

[geelaw]

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

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

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

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

[msg7086]

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

[xqk111]

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

[e7]

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

[forcecharlie]

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

[cheng6563]

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

[dobelee]

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

[Miy4mori]

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

[balabalaXMX]

谢谢大家，明白了。