为什么哈希表是无序的?

2023-01-04 20:29:40 +08:00
 balabalaXMX

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

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

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

这样理解对吗?

4104 次点击
所在节点    C++
17 条回复
mind3x
2023-01-04 21:04:14 +08:00
一般是指不保证任何特定的枚举顺序,例如(但不限于)枚举顺序与插入顺序无关。

虽然就常见实现而言,如果没有元素增删,大概率每次遍历顺序会一样,但使用者不应该依赖这种假设。Golang 更进一步,直接把枚举顺序搞成了随机的。
lovelylain
2023-01-04 21:12:42 +08:00
印象中有一门语言为了让人记住哈希表是无序的,故意在枚举时打乱顺序,即使元素无变化,每次枚举顺序也不一样。
viruscamp
2023-01-04 21:21:57 +08:00
无序的意思是不保证每次读取顺序相同。
请在编程时当作: 每次遍历它返回的元素顺序不一样.
实际代码中基本不会遍历 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
2023-01-04 21:27:38 +08:00
不要依赖于于实现,依赖于规范,规范保证的东西不会变化,其它实现的行为具有不确定性。
BBCCBB
2023-01-04 21:56:58 +08:00
这个依赖于实现,

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

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



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

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

所以给我的感觉就是目前实现就是这样, 可能是多方取舍后得到的结果..
maocat
2023-01-04 22:42:00 +08:00
@jobmailcn 没错你说的就是 golang
agagega
2023-01-04 22:52:50 +08:00
因为它规定了 map 是有序的而 unordered_map 是无序的。更深究一点的话,因为散列表的内部元素顺序是高度依赖实现细节的,没必要规定死;对于用户 key 构成的外部顺序来说,你的第二点是对的。相当于 unordered_map 以无法排序为代价获得了更好的性能。
ksc010
2023-01-04 23:32:23 +08:00
无需的就是在整个生命周期,不保证它的顺序是一直不变的(没有认为改动顺序的情况下)
这样在语言具体实现的时候,就没有额外的负担
geelaw
2023-01-05 03:55:03 +08:00
https://stackoverflow.com/questions/18301302/is-forauto-i-unordered-map-guaranteed-to-have-the-same-order-every-time

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

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

“key 数组”是不存在的概念。
msg7086
2023-01-05 03:57:09 +08:00
不是一定不一样,而是不保证一样。(做到一样也行,但是没必要。)
unordered_map 用哈希表实现,map 用红黑树实现,红黑树的性能要差一些。
xqk111
2023-01-05 09:13:46 +08:00
我是这么理解的,数组一般是顺序存储,哈希表一般是随机存储,所以就认为数组是有序的,哈希表是无序,个人浅见
e7
2023-01-05 09:41:19 +08:00
这把我问到了,就像“为什么球是圆的?”
forcecharlie
2023-01-05 10:15:46 +08:00
如果你知道 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
2023-01-05 10:27:59 +08:00
不是无序,是难以预计而当做无序。
dobelee
2023-01-05 11:15:06 +08:00
没有人反对你实现一个有序哈希表。
Miy4mori
2023-01-05 21:09:30 +08:00
哈希表这个名字更像是一个接口定义,本身就不要求具体实现保证有序。所以你问为什么无序,因为“哈希表”不要求具体实现保证有序........
balabalaXMX
2023-01-06 09:27:10 +08:00
谢谢大家,明白了。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/906611

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX