C++如何计算普通类型的 Hash 值：基于 gcc/clang 源码分析

发表于 Disqus： # C++ # Hash

当 int/long/float/指针/std::string 作为 std::unordered_map 的 key 时，C++底层是如何计算 hash 值的？

gcc/clang 作为使用最多的两种编译器和标准库，它们在这个问题的实现上略有差异。本文将基于二者的源码进行对比分析。

std::string

在深入讨论其他类型的 hash 实现之前，我们首先分析 std::string 的 hash 逻辑。这是因为其他类型的哈希操作也依赖于对底层字节序列的通用 hash 操作，我们把它统一叫做hash_bytes。

在 gcc 中，无论是 32 位系统还是 64 位系统使用 murmurhash。代码在：libstdc++/hash_bytes.cc#L138

而 clang 在 32 位系统下采用 murmurhash, 64 位系统下采用 cityhash64。代码在：llvm/libcxx/__functional/hash.h#L86

整型

我们需要注意 std::hash 的结果类型是 size_t，而 size_t 在 64 位系统下是 8 字节，在 32 位系统是 4 字节。

因此，在讨论整数如何进行 hash 的时候，需要分两种情况：

  1. sizeof(T) <= sizeof(size_t): 比如 int32_t、64 位系统下的 int64_t。
  2. sizeof(T) > sizeof(size_t): 比如 32 位系统下的 int64_t。

当 sizeof(T) <= sizeof(size_t) 时，这种情况下非常简单，直接将 key 的值本身作为 hash 值，无需进行额外的计算： hash = static_cast<size_t>(key)。这点 gcc 和 clang 的做法都是一致的。

而当 sizeof(T) > sizeof(size_t) 时，比如 32 位系统下的 int64_t。 gcc 和 clang 的做法略有不同。

在 gcc 中：对于这种情况也一样的强转成static_cast<size_t>(key)。但这里就涉及到了精度损失，在小端序下会丢弃高 32 位，保留低 32 位。这种情况下就会有 hash 冲突问题。

而 clang 的做法更加严谨：会将 int64_t 视为长度为 8 字节的 bytes，进行 hash_bytes 计算得到 hash 值。 llvm/libcxx/__functional/hash.h#L281

这个操作涉及底层hash_bytes操作，明显性能略差。但在 64 位系统是主流的今天，sizeof(T) > sizeof(size_t)的场景也非常少，实际上大部分情况下并不会走到这个逻辑分支。

另外 bool、char、short 等这些也统一被视为整型。同样的，值本身会被作为 hash 值。

float/double

在 gcc 中 将 float 和 double 视为底层是 4 字节和 8 字节的 bytes，直接进行 hash_bytes 计算得到 hash 值。代码在 libstdc++/hash_bytes.cc#L258

而在 clang 中进行了更细致的区分处理：

  • 当sizeof(T) > sizeof(size_t)时，比如 32 位机器下的 double。这种情况下会和 gcc 一样，对 double 进行 hash_bytes 操作。

  • 当 sizeof(T) <= sizeof(size_t) 时：比如 64 位机器下的 double 和 float。clang 借助了 union 进行高效的转换处理，但针对 double 和 float 的实现略有不同。

针对 64 位机器下的 float，clang 先将 union 中的 64 位 size_t 初始化为 0，然后将 float 放在低 32 位，高 32 位保持为 0，最后返回这个 size_t 作为哈希结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 假设现在是 64 位机器，我们要处理 32 位 float 的场景
template <class _Tp>
struct __scalar_hash<_Tp, 0> : public __unary_function<_Tp, size_t> {
_LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {
    union {
    _Tp __t;
    size_t __a;
    } __u;
    // 8 字节全部初始化为 0
    __u.__a = 0;
    // 填充低位 4 字节，高位 4 字节保持为 0
    __u.__t = __v;
    return __u.__a;
}
};

而对于 64 位机器下的 double，因为 double 的尺寸和 size_t 一致，因此直接使用 union 进行类型转换就行。

1
2
3
4
5
6
7
8
9
10
11
template <class _Tp>
struct __scalar_hash<_Tp, 1> : public __unary_function<_Tp, size_t> {
_LIBCPP_HIDE_FROM_ABI size_t operator()(_Tp __v) const _NOEXCEPT {
    union {
    _Tp __t;
    size_t __a;
    } __u;
    __u.__t = __v;
    return __u.__a;
}
};

这里之所以不用 static_cast 强制转换为 size_t 类型，是因为 float 转为 size_t 会直接丢掉小数部分。

可以看出当sizeof(T) <= sizeof(size_t)时，clang 的实现更加简洁高效，性能更好，几乎没有什么开销。而这个优化可以命中绝大部分的使用场景。

此外，无论是 clang 还是 gcc，对于 float 值=0 的情况都进行了特殊处理，直接特判并返回 hash 值等于 0。这是因为在浮点数 IEEE 754 规定 +0.0 == -0.0，但它们的二进制表示不同，因此不能直接进行通用的底层二进制的转换。

  • +0.0 的二进制：0x00000000（float32）
  • -0.0 的二进制：0x80000000（float32）

指针

指针类型的长度和 size_t 一样，gcc 利用了这个特性，直接将指针视为 size_t 作为 hash 值，这样做没有任何精度损失和计算开销。代码如下：

1
2
3
4
5
6
7
template<typename _Tp>
struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
{
    size_t
    operator()(_Tp* __p) const noexcept
    { return reinterpret_cast<size_t>(__p); }
};

而 clang 的实现则不同，clang 是对指针进行了 hash_bytes 操作，计算得到一个 hash 值。代码在 llvm/libcxx/__functional/hash.h#L340

为什么 clang 不采用性能更好的 reinterpret_cast 操作呢？
这因为考虑到一些内存地址步长固定的场景，比如对于一个 std::vector<int64_t>，其中每个相邻元素内存地址都固定相差 8 字节。这个时候直接用指针地址作为 hash 值，极易发生 hash 冲突。

总结

我们通过分别 gcc 和 clang 的源码，了解到了普通类型 hash 值计算策略 以及二者的不同。在一些高性能场景下，我们针对性的进行优化，比如：

  • 可以根据业务场景，选择更高效的 hash 计算方式，而非默认的 murmurhash/cityhash64
  • 整型作为 hash key 可以绕过 hash 计算。我们在某些场景下提前计算好 hash 值 替代 std::string 作为 key，避免每次 find 和 insert 操作时的 hash 计算开销。