V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
DinoStray
V2EX  ›  问与答

使用 uint64 作为 map 的 key, 有哪些优化技巧?

  •  
  •   DinoStray · 2021-04-19 15:41:33 +08:00 · 1467 次点击
    这是一个创建于 1121 天前的主题,其中的信息可能已经有所发展或是发生改变。

    比如, hash 和 红黑树 哪个更合适.
    如果用 hash, 有没有推荐的 hash 算法?

    PS: 这个问题我尽量不关联编程语言提问. 实际上我这边是 C++20, 涉及到 std::map, std::unordered_map

    第 1 条附言  ·  2021-04-19 17:11:25 +08:00
    针对 uint64, 我一直觉得肯定有什么最优的解决方案, 只是我没听过, 不知道
    第 2 条附言  ·  2021-04-19 17:17:39 +08:00
    另外我的 key 有个特点, 是一直自增+1 的
    第 3 条附言  ·  2021-04-19 18:52:57 +08:00
    我的业务场景, key 是一直自增 +1, 然后实际 存储数据 大概只有 2 万左右. 然后频繁的会有 插入 删除 查找操作.
    避免 hash 桶一直增加下去, 导致内存不够用, 基于我的业务场景, 我自己的 hash:
    ```C++
    struct SessionKeyHash {
    std::size_t operator()(const uint64_t &k) const { return (k % HashBucketCount); }
    };
    ```
    第 4 条附言  ·  2021-04-19 18:54:07 +08:00
    其中 HashBucketCount 是 1 百万
    然后调用 std::unordered_map::rehash(HashBucketCount) 做初始化
    第 5 条附言  ·  2021-04-19 19:27:09 +08:00
    The container uses the value of max_load_factor as the threshold that forces an increase in the number of buckets (and thus causing a rehash).
    看起来是我多虑了, 我的场景 2 万数据量的情况下, 虽然 key 会一直自增, 但 unordered_map 会一直自动触发 rehash, 控制桶的数量
    第 6 条附言  ·  2021-04-19 19:41:16 +08:00
    理解错了, max_load_factor 只会增加桶的数量, 不会缩减
    第 7 条附言  ·  2021-04-19 19:50:39 +08:00
    ```C++
    std::unordered_map<int, int> map;
    std::cout << map.bucket_count() << std::endl;
    std::cout << map.load_factor() << std::endl;
    std::cout << map.max_load_factor() << std::endl;
    std::cout << "===========" << std::endl;
    for (int i = 0; i < 59481497; ++i) {
    map[i] = i;
    if (i % 3 == 0) { map.erase(i); }
    }
    std::cout << map.size() << std::endl;
    // 101473717
    std::cout << map.bucket_count() << std::endl;
    std::cout << map.load_factor() << std::endl;
    std::cout << map.max_load_factor() << std::endl;
    ```

    写了个 testcase , 发现 bucket 是可以自动减的, 想弄懂, 还是得研究源码啊
    16 条回复    2021-04-19 20:42:50 +08:00
    3dwelcome
        1
    3dwelcome  
       2021-04-19 15:53:35 +08:00
    红黑树不是挺好的,那么经典。比 hash 好,hash 函数有冲突,红黑树是自平衡,没有潜在问题。
    minami
        2
    minami  
       2021-04-19 16:22:47 +08:00   ❤️ 2
    一般推荐用 xxhash 或 murmurhash ( 2 或 3 版本),前者比较好,但后者实现简单
    geelaw
        3
    geelaw  
       2021-04-19 17:21:04 +08:00 via iPhone
    字典树也可以考虑一下。
    geelaw
        4
    geelaw  
       2021-04-19 17:22:03 +08:00 via iPhone
    🤧 如果 key 是连续范围且该范围内稠密,考虑用 vector 。
    DinoStray
        5
    DinoStray  
    OP
       2021-04-19 17:31:34 +08:00
    @geelaw 因为会频繁的增加删除, 所以长时间运行后是不连续的了
    3dwelcome
        6
    3dwelcome  
       2021-04-19 18:04:44 +08:00   ❤️ 1
    @minami 没有审题啊,楼主 key 是 integer,又不是 string 。你这两个算法都是针对字符串的。

    有专门针对 uint64_t 的 hash 函数,你一个都没提到。
    3dwelcome
        7
    3dwelcome  
       2021-04-19 18:09:37 +08:00
    google 搜“Integer Hash Function", 这才是针对整形 key 的散列函数。
    3dwelcome
        8
    3dwelcome  
       2021-04-19 18:18:31 +08:00
    "第 2 条附言 · 55 分钟前
    另外我的 key 有个特点, 是一直自增+1 的"

    这种特点可以用二分法查找,自己管理一个集合,未必需要依赖于 C++20,只要保持数据始终内存数序排列就可以。
    ysc3839
        9
    ysc3839  
       2021-04-19 18:40:11 +08:00 via Android
    @3dwelcome 这些 hash 函数都是可用于任意二进制数据的,没记错的话 MSVC 的 STL 就是直接用 FNV Hash 去处理整数 key 的。
    DinoStray
        10
    DinoStray  
    OP
       2021-04-19 18:42:39 +08:00
    @3dwelcome 我有个问题, 我看标准库的 hash, 对 int 的处理是直接返回 值, 那么如果我的 uint64 key 一直自增下去, 不是会存在桶一直增加, 内存不够用的情况么? unordered_map 会对桶做收缩么
    minami
        11
    minami  
       2021-04-19 19:01:44 +08:00
    @3dwelcome 你是认真的吗,我特地去我以前代码里翻出了针对 uint64_t 的 MurmerHash3
    struct MurmerHash3
    {
    inline std::size_t operator()(const uint64_t &key) const noexcept
    {
    uint64_t x = (key ^ (key >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
    }
    };
    minami
        12
    minami  
       2021-04-19 19:05:51 +08:00
    @minami 不好意思,代码里写的 MurmerHash3,实际上查了下是 splitmix64,不知道当年怎么命名的,逃(
    DinoStray
        13
    DinoStray  
    OP
       2021-04-19 19:13:31 +08:00
    @minami 辛苦您看下, 基于我的业务场景, 我这样重定义 hash 有问题么? 因为我的 key 只是简单自增, 不关联任何业务逻辑. 我只是基于避免桶数量过多, 内存溢出, 所以取余了一下, 限制桶数量
    iceheart
        14
    iceheart  
       2021-04-19 20:08:57 +08:00 via Android
    多频繁?每秒千万次以内查询建议直接 std::map
    3dwelcome
        15
    3dwelcome  
       2021-04-19 20:39:58 +08:00
    @DinoStray "我有个问题, 我看标准库的 hash, 对 int 的处理是直接返回 值, 那么如果我的 uint64 key 一直自增下去, 不是会存在桶一直增加, 内存不够用的情况么?"

    刚刚我用 VS2017 调试了一下,和 9 楼的 @ysc3839 同学说的一致,内部对于 uint64_t 都用 FNV-1a hash function 算法处理过一次,不是直接返回的。

    既然数列已经打散了,就不用担心 hash 冲突,会内存不够吧。
    DinoStray
        16
    DinoStray  
    OP
       2021-04-19 20:42:50 +08:00
    @3dwelcome g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
    我这边用这个做实验.
    ```
    std::unordered_map<uint64_t, uint64_t> map{};
    std::cout << "1: " << map.hash_function()(1) << std::endl;
    std::cout << "50000: " << map.hash_function()(50000) << std::endl;
    ```
    结果是
    1
    50000

    看来 g++ 的实现, 是直接返回 uint64 值的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1036 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 19:52 · PVG 03:52 · LAX 12:52 · JFK 15:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.