保存多层地图最快的方法是什么？

Question

我想构建一个键值容器来保存数据。

我可以建一个三层的unordered_map来映射，关键是<int, <int, <int>>>，但是我觉得比较慢

所以，我想将 <int, int, int> 映射到唯一的 int。然后我可以将它保存在一级 unordered_map

例如：

假设三个key叫a, b, c，a的范围是[0, 1e4]，b[0, 1e6] c[0, 1e5]

我想写一个这样的函数：

int encode(int a, int b, int c) {
  // return a unique int
}

我对时间很敏感，我认为按位可能是最快的方法，但我不知道如何实现它。你能帮忙吗？

你认为这会更快吗？还有，有没有比这更好的方法？

Answer 1

unordered_map 需要返回 size_t 的哈希函数，因此如果您正在编译 64 位应用程序（除了某些嵌入式环境外，大多数人都这样做），您可以简单地组合整数:

size_t encode(int a, int b, int c) {
    return a + (b * 10'000) + (c * 10'000 * 1'000'000);
}

如果您的散列 table 使用质数桶（例如 GCC、clang），您可以考虑将上述数字四舍五入为最接近的 2 的幂，因为名义上乘以 2 的幂是CPU 可以更快地完成一个简单的左位移位操作。如果您的实现使用 2 的幂桶计数（例如 Visual C++），那么您应该不惜一切代价避免这种情况：因为当将数字修改为 2 的幂桶计数时，高阶位将被丢弃。例如，如果您有 256 个桶，则 8 个最低有效位确定桶，丢弃更高位。

或者，您可以使用 boost::hash_combine 采用的算法，该算法通常适用于散列多部分密钥：

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

你可以这样使用它：

size_t encode(int a, int b, int c) {
    size_t seed = 0;
    hash_combine(seed, a);
    hash_combine(seed, b);
    hash_combine(seed, c);
    return seed;
}

另一种选择是在内存中并排排列字节（例如将它们复制到变量中 - int x[3]{ a, b, c};），并应用任何写入的哈希函数来哈希任意内存块，即size_t (const std::byte* p, size_t n) - 谷歌搜索会出现很多。

保存多层地图最快的方法是什么？

what the the fastest way to save multi-layer map?

c++

stl

unordered-map

bit-manipulation