V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
balabalaXMX
V2EX  ›  C++

为什么哈希表是无序的?

  •  
  •   balabalaXMX · 2023-01-04 20:29:40 +08:00 · 4048 次点击
    这是一个创建于 450 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    这样理解对吗?

    17 条回复    2023-01-06 09:27:10 +08:00
    mind3x
        1
    mind3x  
       2023-01-04 21:04:14 +08:00   ❤️ 2
    一般是指不保证任何特定的枚举顺序,例如(但不限于)枚举顺序与插入顺序无关。

    虽然就常见实现而言,如果没有元素增删,大概率每次遍历顺序会一样,但使用者不应该依赖这种假设。Golang 更进一步,直接把枚举顺序搞成了随机的。
    lovelylain
        2
    lovelylain  
       2023-01-04 21:12:42 +08:00 via Android
    印象中有一门语言为了让人记住哈希表是无序的,故意在枚举时打乱顺序,即使元素无变化,每次枚举顺序也不一样。
    viruscamp
        3
    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
        4
    thinkershare  
       2023-01-04 21:27:38 +08:00   ❤️ 2
    不要依赖于于实现,依赖于规范,规范保证的东西不会变化,其它实现的行为具有不确定性。
    BBCCBB
        5
    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
        6
    maocat  
       2023-01-04 22:42:00 +08:00 via iPhone
    @jobmailcn 没错你说的就是 golang
    agagega
        7
    agagega  
       2023-01-04 22:52:50 +08:00 via iPhone
    因为它规定了 map 是有序的而 unordered_map 是无序的。更深究一点的话,因为散列表的内部元素顺序是高度依赖实现细节的,没必要规定死;对于用户 key 构成的外部顺序来说,你的第二点是对的。相当于 unordered_map 以无法排序为代价获得了更好的性能。
    ksc010
        8
    ksc010  
       2023-01-04 23:32:23 +08:00
    无需的就是在整个生命周期,不保证它的顺序是一直不变的(没有认为改动顺序的情况下)
    这样在语言具体实现的时候,就没有额外的负担
    geelaw
        9
    geelaw  
       2023-01-05 03:55:03 +08:00 via iPhone
    https://stackoverflow.com/questions/18301302/is-forauto-i-unordered-map-guaranteed-to-have-the-same-order-every-time

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

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

    “key 数组”是不存在的概念。
    msg7086
        10
    msg7086  
       2023-01-05 03:57:09 +08:00   ❤️ 1
    不是一定不一样,而是不保证一样。(做到一样也行,但是没必要。)
    unordered_map 用哈希表实现,map 用红黑树实现,红黑树的性能要差一些。
    xqk111
        11
    xqk111  
       2023-01-05 09:13:46 +08:00
    我是这么理解的,数组一般是顺序存储,哈希表一般是随机存储,所以就认为数组是有序的,哈希表是无序,个人浅见
    e7
        12
    e7  
       2023-01-05 09:41:19 +08:00
    这把我问到了,就像“为什么球是圆的?”
    forcecharlie
        13
    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
        14
    cheng6563  
       2023-01-05 10:27:59 +08:00
    不是无序,是难以预计而当做无序。
    dobelee
        15
    dobelee  
       2023-01-05 11:15:06 +08:00
    没有人反对你实现一个有序哈希表。
    Miy4mori
        16
    Miy4mori  
       2023-01-05 21:09:30 +08:00
    哈希表这个名字更像是一个接口定义,本身就不要求具体实现保证有序。所以你问为什么无序,因为“哈希表”不要求具体实现保证有序........
    balabalaXMX
        17
    balabalaXMX  
    OP
       2023-01-06 09:27:10 +08:00
    谢谢大家,明白了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2799 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 13:31 · PVG 21:31 · LAX 06:31 · JFK 09:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.